I'm dinking with the DFT 128 (sort of FFT) verilog code from open cores. I've used the 256 point version before. It has some bugs in it but sort of works out of the box. With cleanup and pipe-lining the enables it is nice and small.
The 128 point version doesn't work as. The output isn't right. It uses a radix 8 followed by a radix 16 stage. Both designs are nice in that most of the multiplies are fixed and just 4 in the middle are real hardware multipliers.
I want this code so I'm modeling it in Matlab. I have the two stages, "fft8" and "fft16" working as .m files and they match the Matlab fft.
So next I want to fill a 128 point buffer, operate on it with the fft8 stage, multiply by the twiddle factors, and then operate on that result with the fft16 stage. There is enough documentation in the core (plus the code) to figure that much out.
However, the twiddle factors in the middle of this I don't know. The algorithm is called WFTA, or Winograd Fourier transform algorithm. Anyone familiar enough with this to point me at code or a reference?
Thank you much,
Mark Napier
Found it in a book I already had, "Fast Fourier Transform and Convolution Algorithms" by H.J.Nussbaumer
Page 85, Section on the Fast Fourier Transform (isn't the whole dang book on this?)
He considers the DFT of N terms where N = N1 * N2. Called a 2 factor DFT. The formula is set up as two summations with the twiddle factors in the middle.
Too long to type up. I'll post some Matlab code when I have it.
Had a lot of trouble getting it to work. Finally I pulled out an old Mathcad image and tried the formula directly. That works. So it just needs some fingering on my part.
The 2 factor FFT is interesting in that any two radix DFTs can be used, say a 13 x 16. These can be implemented using the Rader short DFT blocks. Also, the 2 Factor formula can be used recursively to define longer odd FFTs similar to the power of 2 even/odd expansion. Anyway I've attached my Mathcad printout.
Mark Napier
