2 Theory

  The standard definition of the discrete Fourier transform of an input sequence x[n] of length N is [2, (9.38)]:

 

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{2 \pi i / N}$$ (1)

It requires O(N²) operations to calculate, as the summation from to N-1 needs to be completed for each index k, of which there are N indices. By way of example, given a 2¹⁸ = 262144 point sequence and a instruction time of $1\mu s$ the DFT would require $(262144^2)(1\mu s) \simeq 68719 seconds = 19 hours$ to calculate. As early as 1942, Danielson and Lanczos (as reported in [3, p.408]) proved that a DFT of an N-point sequence could be shown to equal the sum of two N/2 point sequences. This result enabled James Cooley and John Tukey to develop their formulation of the DFT (2), writing $W_N \equiv e^{-j(2 \pi / N)}$:

 

$$X[k_1 + N_1 k_2] = \sum_{n_2 = 0}^{N_2 -1} [(\sum_{n_1=0}^{N... ... n_1 + n_2] W_{N_1}^{k_1 n_1}) W_N^{k_1 n_2}] W_{N_2}^{k_2 n_2}$$ (2)

Given the ranges in (3):

For the radix-2 case, N₁ = 2 and N₂ = N / N₁ = N/2 and the resultant two point summation in the center expands easily (4:

 

$$X[k_1 + 2 k_2] = \sum_{n_2 = 0}^{N/2 -1} [( x[n_2] + (-1)^{k_1} x[N/2 + n_2]) W_N^{k_1 n_2}] W_{N/2}^{k_2 n_2}$$ (3)

Likewise, for the radix-4 algorithm N₁ = 4 and N₂ = N / 4. The center summation expands to four terms, resulting in (5):

 

$$X[k_1 + 4 k_2] = \sum_{n_2 = 0}^{N/4 - 1} [( x[n_2] + (-j)^{... ...j)^{k_1}x[\frac{3}{4}N + n_2]) W_N^{k_1 n_2}] W_{N/4}^{k_2 n_2}$$ (4)