DFTs

The discrete Fourier transform (DFT) is a fundamental tool in digital signal processing that converts a finite sequence of samples into its frequency components. Given a sequence of N complex samples x0, x1, ..., xN−1, the DFT outputs a sequence X0, X1, ..., XN−1 that represents the amplitudes and phases of sinusoids at discrete frequencies. The transform assumes the input sequence is one period of a periodic sequence and is commonly used to analyze or manipulate the spectrum of signals such as audio, images, and sensor data.

The forward DFT is defined by Xk = sum from n=0 to N−1 of x_n · exp(−2π i k n / N) for k = 0, 1, ..., N−1. The inverse DFT reconstructs the original sequence (up to a normalization convention) via x_n = (1/N) sum from k=0 to N−1 of X_k · exp(2π i k n / N). Different conventions place the 1/N factor on the forward or the inverse transform; some use 1/N on both or neither, depending on the application.

Key properties include linearity, time-shifting, and frequency-domain relationships such as the convolution theorem. The DFT reveals the frequency content of a real-valued sequence through a spectrum where X_k and X_{N−k} are complex conjugates. Circular convolution in the time domain corresponds to multiplication in the DFT domain, while linear convolution requires padding to avoid wraparound. The DFT is also basis for many practical analyses, including spectral magnitude and phase estimation.

Computationally, a direct implementation requires O(N^2) operations. The Fast Fourier Transform (FFT) reduces this to O(N log N) and is the standard method for large N. Variants of the FFT (radix-2, mixed-radix, Bluestein) enable efficient computation for a wide range of N. Extensions include the two-dimensional DFT for images and other multi-dimensional data, typically computed via separable 1D transforms.