5.8 Fast fourier transform (fft)

One wonders if the DFT can be computed faster: Does another computational procedure -- an algorithm -- exist that can compute the same quantity, but more efficiently. Wecould seek methods that reduce the constant of proportionality, but do not change the DFT's complexity $O(N^2)$ .Here, we have something more dramatic in mind: Can the computations be restructuredso that a smaller complexity results?

In 1965, IBM researcher Jim Cooley and Princeton faculty member John Tukey developed what is now known as the Fast FourierTransform (FFT). It is an algorithm for computing that DFT that has order $O(N\lg N)$ for certain length inputs . Now when the length of data doubles, the spectral computational time will not quadruple aswith the DFT algorithm; instead, it approximately doubles. Later research showed that no algorithm for computing the DFT could have asmaller complexity than the FFT. Surprisingly, historical work has shown that Gauss in the early nineteenth century developed the samealgorithm, but did not publish it! After the FFT's rediscovery, not only was the computation of a signal's spectrum greatlyspeeded, but also the added feature of algorithm meant that computations had flexibility not available to analog implementations.

To derive the FFT, we assume that the signal's duration is a power of two: $N=2^L$ . Consider what happens to the even-numbered and odd-numberedelements of the sequence in the DFT calculation.

Each term in square brackets has the form of a $\frac{N}{2}$ -length DFT. The first one is a DFT of the even-numbered elements, and the second of the odd-numberedelements. The first DFT is combined with the second multiplied by the complex exponential $e^{-\left(\frac{i\times 2\pi k}{N}\right)}$ . The half-length transforms are each evaluated at frequency indices $k=0$ , $\dots$ , $N-1$ . Normally, the number of frequency indices in a DFT calculationrange between zero and the transform length minus one. The computational advantage of the FFT comes from recognizing the periodic nature of the discrete Fouriertransform. The FFT simply reuses the computations made in the half-length transforms and combines them through additions andthe multiplication by $e^{-\left(\frac{i\times 2\pi k}{N}\right)}$ , which is not periodic over $\frac{N}{2}$ . [link] illustrates this decomposition. As it stands, we now compute two length- $\frac{N}{2}$ transforms (complexity $2O(\frac{N^2}{4})$ ), multiply one of them by the complex exponential (complexity $O(N)$ ), and add the results (complexity $O(N)$ ). At this point, the total complexity is still dominated by the half-length DFT calculations, but theproportionality coefficient has been reduced.