What Is the FFT?

The fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a finite sequence of numbers with far fewer arithmetic operations than a direct implementation of the DFT definition requires. The DFT decomposes a time-domain sequence of N samples into N complex-valued frequency components, but naive computation costs O(N²) multiplications. The FFT reduces this to O(N log N) by exploiting the periodicity and symmetry properties of the complex exponential basis functions. For sequences of length 1024, this represents roughly a 100-fold reduction in computation, and the speedup grows with sequence length.

The algorithm's modern form was published by James Cooley and John Tukey in 1965, though equivalent ideas appeared in earlier work by Carl Friedrich Gauss. The Cooley-Tukey radix-2 decimation-in-time algorithm, which requires N to be a power of two, remains the most widely implemented variant.

Algorithmic Structure

The Cooley-Tukey FFT factorizes a length-N DFT into two interleaved DFTs of length N/2, applied recursively until the base case of a length-1 DFT is reached. At each stage, pairs of complex values are combined using butterfly operations involving twiddle factors, which are precomputed complex exponentials. The bit-reversal permutation rearranges the input sequence into the order required by the recursive structure. Variants including the split-radix algorithm, mixed-radix algorithms for non-power-of-two lengths, and the Winograd FFT have been developed to reduce the operation count further or to fit the algorithm to specific hardware constraints. Analog Devices' DSP reference guide provides a detailed treatment of butterfly diagrams and computational flow graphs for the radix-2 case.

Spectral Analysis and Signal Processing

The FFT's primary application is spectral analysis: transforming a digitized waveform from the time domain to the frequency domain to reveal which frequency components are present and at what amplitudes. A spectrum analyzer computes FFTs on successive windowed segments of an incoming signal, applying window functions such as Hann or Blackman-Harris to reduce spectral leakage at segment boundaries. Frequency-domain filtering replaces convolution in the time domain, because convolution becomes multiplication after transformation, a far cheaper operation for long filters. MATLAB's FFT documentation illustrates these applications with concrete examples drawn from audio and communications signal processing. The short-time Fourier transform, a sequence of overlapping FFTs computed on sliding windows, produces a spectrogram that shows how spectral content changes over time, widely used in speech processing and vibration monitoring.

Hardware Implementation

Modern digital signal processors and field-programmable gate arrays implement the FFT in dedicated pipelined architectures that sustain one butterfly operation per clock cycle. The availability of hardware FFT cores made real-time frequency-domain processing practical for applications demanding high throughput, including orthogonal frequency-division multiplexing (OFDM) in 4G and 5G communications, radar pulse compression, and sonar beamforming. General-purpose GPUs accelerate large FFTs for scientific computing through libraries such as cuFFT, which exploit the parallelism of thousands of shader cores. Keysight's oscilloscope FFT reference describes how benchtop instruments apply the algorithm in real-time to display signal spectra during measurements.

Applications

The FFT has applications across a broad range of technical disciplines, including:

• OFDM modulation and demodulation in wireless and wireline broadband communications
• Radar and sonar signal processing for range and velocity estimation
• Audio compression algorithms including MP3 and AAC
• Vibration analysis and structural health monitoring in mechanical systems
• Medical imaging, particularly MRI reconstruction from k-space data
• Astronomical radio telescope data processing for source detection