Discrete Fourier transform

The discrete Fourier transform (DFT) maps a finite sequence of complex-valued samples to an equally sized set of complex frequency coefficients. Each coefficient measures the sequence’s contribution at one frequency in a fixed set of evenly spaced frequencies.

Discrete Fourier transform matrix: A matrix whose multiplication by a sample vector computes its discrete Fourier transform. Its roots-of-unity entries encode every frequency coefficient in one linear operation.
Complex exponential: A complex-valued exponential whose magnitude and phase encode oscillatory behavior. The DFT compares samples with complex exponentials at its candidate frequencies.
Short-time Fourier transform: A Fourier analysis that computes spectra over successive, often overlapping, windows of a signal. Each window’s spectrum is commonly computed with a DFT to track changing frequencies.
Discrete-time Fourier transform: A Fourier transform that represents an infinite discrete-time sequence as a continuous, periodic function of frequency. Unlike the DFT’s finite set of coefficients, it describes a continuous spectrum for a discrete sequence.
Roots of unity: Complex numbers whose integer powers equal one. Powers of a primitive root of unity supply the DFT’s evenly spaced frequency phases.
Sampling (signal processing): The process of converting a continuous signal into discrete values at selected times or positions. A DFT operates on the finite samples produced by sampling.
Digital filter: A system that modifies a discrete-time signal through operations on its samples. Frequency-domain filtering can multiply DFT coefficients by a chosen response.
Discrete cosine transform: A transform that represents finite data using cosine functions at discrete frequencies. It uses a real cosine basis and boundary conventions rather than the DFT’s complex exponential basis.
Fast Fourier transform: A family of algorithms that computes a discrete Fourier transform using fewer operations than direct evaluation. It exploits symmetries in the DFT to reduce computation from quadratic to roughly n log n.
Frequency: The rate at which a periodic event or oscillation repeats per unit time or distance. Each DFT coefficient corresponds to a discrete frequency among the transform’s bins.

Linked from 18 pages