23-08-2017, 11:41 AM
The following figure shows the FFT implementation using the radix 2 algorithm.
This is an 8 point FFT implementation using the butterfly unit, The butterfly unit is the heart of the FFT algorithm. From the figure u can see that if we are done with the butterfly unit we are 70% done with the FFT coding.
Okie now allows you to start coding the butterfly unit. The butterfly backbox model will have 2 complex inputs and 2 complex outputs
The second input is multiplied by the twiddle factor, ie wr + j wi) first. So before you start coding you should have the code written for the multiplication of complex numbers. Once you are done with multiplication, the next step is to do the addition. You can do this for simple CLA (bring add analyzers). Output Z1 is obtained by summing the result of the multiplication i.e (b1 + jb2) * (Wr + jWi) to the first number, ie, a1 + ja2. And output Z2 is obtained by subtracting the product multiplied with the first number. To put it in mathematical form;
Z1r + jZ1i = (b1 + jb1) * (Wr + jWi) + (a1 + ja2)
Z2r + jZ2i = (b1 + jb1) * (Wr + jWi) - (a1 + ja2)
Z2r + jZ2i = (b1 + jb1) * (Wr + jWi) - (a1 + ja2)
If the result is analyzed proerly or you will find that we need a complex multiplier (which has 4 normal multipliers) and 4 CLA units. To put the process in an orderly fashion we have to proceed in steps like this
1> read 2 complex numbers and the twiddle factor
2> multiply the second number with the twiddle factor
3> add the product to the first number to get the first o / p
4> Subtract the product to the first number to get the first o / p