Fast Fourier Transform

What Is the Fast Fourier Transform?

The Fast Fourier Transform (FFT) is an algorithm that computes the Discrete Fourier Transform (DFT) of a sequence in O(N log N) time, compared to the O(N²) time required by direct evaluation. The DFT maps a finite-length sequence of N complex values from the time or space domain into an equivalent sequence of N complex values in the frequency domain, revealing the spectral content of a signal. The FFT achieves the same result by exploiting mathematical symmetries to factorize the DFT computation into a cascade of smaller transforms rather than evaluating all N² products.

The algorithm's origins reach back to 1805, when Carl Friedrich Gauss developed an equivalent procedure for interpolating asteroid orbits. The modern form, commonly called the Cooley-Tukey algorithm after the 1965 paper by J.W. Cooley and J.W. Tukey, provided a systematic divide-and-conquer formulation that triggered broad adoption in digital signal processing. A Stanford CCRMA treatment of FFT algorithms covers the range of variants, from the standard radix-2 Cooley-Tukey through the Prime Factor Algorithm and Bluestein's method for arbitrary lengths.

The Cooley-Tukey Algorithm

The radix-2 Cooley-Tukey FFT applies when N is a power of 2. It splits a length-N DFT into two length-N/2 DFTs, one over even-indexed samples and one over odd-indexed samples, then combines the results using N/2 complex multiplications called twiddle factors. Applying the same decomposition recursively reduces the total number of operations to (N/2) log₂(N) complex multiplications and N log₂(N) additions. The computational kernel of each stage is a butterfly: a two-point operation that combines a pair of values with a twiddle factor in one addition and one multiplication.

For N = 1024, direct DFT evaluation requires roughly 1 million complex multiplications, while the radix-2 FFT requires approximately 5,000, a reduction of two orders of magnitude. This efficiency gain is what made real-time spectrum analysis, radar processing, and digital communications feasible on the hardware available in the 1960s and 1970s.

Variants and Extensions

When N is not a power of 2, several alternative factorizations are available. The Prime Factor Algorithm exploits coprime factors of N to achieve a similar reduction. Bluestein's chirp-Z transform algorithm converts a DFT of any length N into a convolution, which can itself be computed by power-of-2 FFTs, making arbitrary-length transforms efficient. Mixed-radix variants use factorizations involving radices of 2, 3, 4, and 5, and are implemented in widely used libraries such as FFTW (Fastest Fourier Transform in the West), described in detail in Cooley-Tukey FFT Algorithms from Springer, which selects the optimal factorization automatically at runtime. Multidimensional FFTs extend the one-dimensional algorithm to two-dimensional arrays, processing each row and then each column independently.

Applications in Signal Processing

The FFT's ability to transform a time-domain signal into its frequency-domain representation in microseconds makes it central to digital signal processing across a wide range of disciplines. In audio engineering and communications, real-time spectrum analysis relies on the FFT for equalization, noise suppression, and channel estimation. Convolution, which in the time domain requires O(N²) multiplications, can be implemented using two FFTs and one element-wise multiplication in the frequency domain, reducing complexity to O(N log N). The MIT OpenCourseWare lecture on FFT in numerical methods treats these applications alongside the algorithm's convergence and accuracy properties. Imaging modalities including MRI and synthetic aperture radar use two-dimensional FFTs as a core reconstruction step.

Applications

The Fast Fourier Transform has applications in a range of fields, including: