Discrete Fourier transform

The DFT of a sequence x₀, x₁, ..., x_N−1 is defined as X_k = Σ_n=0^N−1 x_n e^{−2πi nk/N} for k = 0, ..., N−1.¹ The inverse DFT reconstructs the original sequence from the frequency components. Key properties include linearity, the shift theorem (a cyclic shift in time corresponds to a phase shift in frequency), and the convolution theorem, which states that the DFT of a cyclic convolution equals the pointwise product of the DFTs.² The DFT is periodic in both domains, and for real-valued inputs, the spectrum exhibits conjugate symmetry, meaning only about half of the coefficients are independent.

The naive computation of the DFT requires O(N²) operations, which is impractical for large N. The fast Fourier transform (FFT), popularized by Cooley and Tukey in 1965, computes the DFT in O(N log N) time by recursively decomposing the transform into smaller transforms.³ However, the FFT's origins trace back to Carl Friedrich Gauss, who used a similar method in 1805 to interpolate asteroid orbits.⁴ Other algorithms include the Bluestein's algorithm for arbitrary N and the Rader's algorithm for prime N. For real-valued data, specialized FFT variants exploit symmetry to halve the computation time.

The DFT is fundamental in digital signal processing, enabling spectral analysis, filtering, and modulation. In telecommunications, it is used in OFDM (orthogonal frequency-division multiplexing) for high-speed data transmission, as in Wi-Fi and 4G/5G networks.⁵ In image processing, the 2D DFT is used for image compression (e.g., JPEG) and filtering. The DFT also underpins the fast convolution of large data sets, and it is used in solving partial differential equations via spectral methods. In audio processing, it is the basis for MP3 compression and speech recognition.

Beyond the standard definition, the DFT has several subtle aspects. The DFT assumes the input is periodic, which can cause spectral leakage when analyzing non-periodic signals; windowing functions mitigate this. The DFT is also related to the discrete cosine transform (DCT), which is used in JPEG because it has better energy compaction for typical images. The number-theoretic transform (NTT) is a variant over finite fields, used in cryptography and polynomial multiplication. The DFT can be computed using the chirp z-transform, which evaluates the transform on a spiral contour. Historically, the DFT was used by Gauss for celestial mechanics, and later by others for crystallography, before the FFT made it ubiquitous.⁶

Fast Fourier transform (FFT)

An algorithm to compute the DFT efficiently in O(N log N) time.

Spectral leakage

The spreading of energy from one frequency bin to adjacent bins due to non-periodic sampling.

Windowing

Multiplying the input sequence by a window function to reduce spectral leakage.

Number-theoretic transform (NTT)

A DFT-like transform over finite fields, used in cryptography.