3
$\begingroup$

I need to make in FPGA (using Verilog) an FFT. Input data is N=8192 points at 1 GSPS. However, the FPGA operates at 125 MHz, therefore the data is split into 8 channels (each one at 125 MHz). This splitting of data and computing the N/8 FFT is not problematic for me, it is already done.

What I don't understand is how to combine the outputs of the N/8 FFTs to create one N FFT. I have created a schematic showing the flow of data, where blue blocks represent what is done and green blocks represent what I don't understand.

I understand generally the Cooley-Tukey FFT algorithm and Butterfly diagrams as they relate to 8 point or 16 point data, but I don't understand how these can be expanded to a 8192 input sequence.

Any help regarding the theory, math, or FPGA implementation behind how the green blocks are implemented is greatly appreciated!

Signal Flow Schematic

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

After giving it some thought I think I've come up with the answer. I was confused since most butterfly diagrams begin with 4 separate n/4 DFT's, like in the image below (annotations added).

Whereas in my problem I begin with 8 separate N/8 DFTs. I was confused about how to connect the outputs of each of the N/8 DFTs to recreate an N DFT.

Now, however, I believe that nothing really changes between the butterfly diagram attached and my problem. I think that each output of my N/8 FFTs is directly fed into each input of on the diagram attached. And then the twiddle factors increase by a factor of 8 after each iteration.

Does that sound correct?enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ This was an old question so not sure if you are still confused but yes you do have this correct. The key is that the inputs to the first FFT's are decimated in time (note if you reverse the bit sequence for each input in binary it reveals how it should be decimated: x[0]=000, reversed is 0000, x[1]=001, reversed = 100 = 4 . etc. To do your case you would continue this pattern with another block just like the one you show next to it (so that you have 8 FFT blocks on the input side and 16 outputs on the right, and follow the pattern to implement one more combining stage : $\endgroup$
    – Dan Boschen
    Aug 18, 2018 at 1:19
  • $\begingroup$ ...so X[0] adds with X[8]$W^0_{16}$, X[1] adds with X[9]$W^1_{16}$, etc $\endgroup$
    – Dan Boschen
    Aug 18, 2018 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.