<< Chapter < Page | Chapter >> Page > |
The twiddle factor array will always have unity in the first row and first column.
To complete [link] at this point, after the row DFT's are multiplied by the TF array, the ${N}_{1}$ length- ${N}_{2}$ DFT's of the columns are calculated. However, since the columns DFT's are oflength ${R}^{M-1}$ , they can be posed as a ${R}^{M-2}$ by $R$ array and the process repeated, again using length- $R$ DFT's. After $M$ stages of length- $R$ DFT's with TF multiplications interleaved, the DFT is complete. The flow graph of a length-2 DFT is given in Figure 1 and is called a butterfly because of its shape. The flow graph of thecomplete length-8 radix-2 FFT is shown in Figure 2 .
This flow-graph, the twiddle factor map of [link] , and the basic equation [link] should be completely understood before going further.
A very efficient indexing scheme has evolved over the years that results in a compact and efficient computer program. A FORTRANprogram is given below that implements the radix-2 FFT. It should be studied [link] to see how it implements [link] and the flow-graph representation.
N2 = N
DO 10 K = 1, MN1 = N2
N2 = N2/2E = 6.28318/N1
A = 0DO 20 J = 1, N2
C = COS (A)S =-SIN (A)
A = J*EDO 30 I = J, N, N1
L = I + N2XT = X(I) - X(L)
X(I) = X(I) + X(L)YT = Y(I) - Y(L)
Y(I) = Y(I) + Y(L)X(L) = XT*C - YT*S
Y(L) = XT*S + YT*C30 CONTINUE
20 CONTINUE10 CONTINUE
A Radix-2 Cooley-Tukey FFT Program
This discussion, the flow graph of Winograd’s Short DFT Algorithms: Figure 2 and the program of [link] are all based on the input index map of Multidimensional Index Mapping: Equation 6 and [link] and the calculations are performed in-place. According to Multidimensional Index Mapping: In-Place Calculation of the DFT and Scrambling , this means the output is scrambled in bit-reversed order and should be followed by anunscrambler to give the DFT in proper order. This formulation is called a decimation-in-frequency FFT [link] , [link] , [link] . A very similar algorithm based on the output index map can be derived whichis called a decimation-in-time FFT. Examples of FFT programs are found in [link] and in the Appendix of this book.
Soon after the paper by Cooley and Tukey, there were improvements and extensions made. One very important discovery wasthe improvement in efficiency by using a larger radix of 4, 8 or even 16. For example, just as for the radix-2 butterfly, there areno multiplications required for a length-4 DFT, and therefore, a radix-4 FFT would have only twiddle factor multiplications. Becausethere are half as many stages in a radix-4 FFT, there would be half as many multiplications as in a radix-2 FFT. In practice, becausesome of the multiplications are by unity, the improvement is not by a factor of two, but it is significant. A radix-4 FFT is easilydeveloped from the basic radix-2 structure by replacing the length-2 butterfly by a length-4 butterfly and making a few othermodifications. Programs can be found in [link] and operation counts will be given in "Evaluation of the Cooley-Tukey FFT Algorithms" .
Notification Switch
Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?