0.8 The cooley-tukey fast fourier transform algorithm  (Page 9/8)

The publication by Cooley and Tukey [link] in 1965 of an efficient algorithm for the calculation of the DFT was a majorturning point in the development of digital signal processing. During the five or so years that followed, various extensions andmodifications were made to the original algorithm [link] . By the early 1970's the practical programs were basically in the form used today.The standard development presented in [link] , [link] , [link] shows how the DFT of a length-N sequence can be simply calculated from thetwo length-N/2 DFT's of the even index terms and the odd index terms. This is then applied to the two half-length DFT's to givefour quarter-length DFT's, and repeated until N scalars are left which are the DFT values. Because of alternately taking the even andodd index terms, two forms of the resulting programs are called decimation-in-time and decimation-in-frequency. For a length of $2^M$ , the dividing process is repeated $M={log}_{2}N$ times and requires $N$ multiplications each time. This gives the famous formula for the computational complexity of the FFT of $N{log}_{2}N$ which was derived in Multidimensional Index Mapping: Equation 34 .

Although the decimation methods are straightforward and easy to understand, they do not generalize well. For that reason it willbe assumed that the reader is familiar with that description and this chapter will develop the FFT using the index map from Multidimensional Index Mapping .

The Cooley-Tukey FFT always uses the Type 2 index map from Multidimensional Index Mapping: Equation 11 . This is necessary for the most popular forms that have $N=R^M$ , but is also used even when the factors are relatively prime and a Type 1 map could be used. The time andfrequency maps from Multidimensional Index Mapping: Equation 6 and Multidimensional Index Mapping: Equation 12 are

Type-2 conditions Multidimensional Index Mapping: Equation 8 and Multidimensional Index Mapping: Equation 11 become

and

The row and column calculations in Multidimensional Index Mapping: Equation 15 are uncoupled by Multidimensional Index Mapping: Equation 16 which for this case are

To make each short sum a DFT, the $K_i$ must satisfy

In order to have the smallest values for $K_i$ the constants in [link] are chosen to be

which makes the index maps of [link] become

These index maps are all evaluated modulo $N$ , but in [link] , explicit reduction is not necessary since $n$ never exceeds $N$ . The reduction notation will be omitted for clarity. From Multidimensional Index Mapping: Equation 15 and example Multidimensional Index Mapping: Equation 19 , the DFT is

This map of [link] and the form of the DFT in [link] are the fundamentals of the Cooley-Tukey FFT.

The order of the summations using the Type 2 map in [link] cannot be reversed as it can with the Type-1 map. This is because of the $W_N$ terms, the twiddle factors.

Turning [link] into an efficient program requires some care. From Multidimensional Index Mapping: Efficiencies Resulting from Index Mapping with the DFT we know that all the factors should be equal. If $N=R^M$ , with R called the radix, $N_1$ is first setequal to $R$ and $N_2$ is then necessarily $R^{M-1}$ . Consider $n_1$ to be the index along the rows and $n_2$ along the columns. The inner sum of [link] over $n_1$ represents a length- $N_1$ DFT for each value of $n_2$ . These $N_2$ length- $N_1$ DFT's are the DFT's of the rows of the $x(n_1,n_2)$ array. The resulting array of row DFT's is multiplied by an array of twiddle factors which are the $W_N$ terms in [link] . The twiddle-factor array for a length-8 radix-2 FFT is