The discrete Fourier transform (DFT) is an invertible mathematical transformation that represents a finite sequence of numbers as a sum of discrete oscillations. It takes input values and produces complex coefficients, each describing the amplitude and phase of a particular frequency component. Unlike the continuous Fourier transform, which generally acts on functions defined over a continuous domain, the DFT operates on finite-dimensional data and can therefore be evaluated directly by a computer.
The DFT is fundamental to digital signal processing, image analysis, scientific computing, and communications. Its importance derives both from its interpretation as a frequency decomposition and from its algebraic properties: it preserves information, converts circular convolution into multiplication, and diagonalizes systems whose behavior is invariant under cyclic shifts. The fast Fourier transform (FFT) is not a different transform but a family of efficient algorithms for computing the DFT. Understanding the distinction between the transform, its algorithms, and the assumptions involved in interpreting sampled measurements is essential to its use.
Definition, inversion, and frequency coordinates
For a sequence , whose entries may be complex numbers, the DFT is conventionally defined by
where . The inverse transformation is
Each inverse-transform term is a complex sinusoid, and the original sequence is recovered by adding these components. The coefficient is the sum of the samples, so is their arithmetic mean. This zero-frequency component is often called the DC component, borrowing terminology from direct-current electrical signals.
The normalization and sign convention are not universal. Some treatments place in the forward transform rather than the inverse; others place in both directions. A positive exponential may also define the forward transform. These choices do not alter the underlying decomposition, but they change formulas for amplitudes, convolution, and energy. With the convention above, a sampled complex exponential
has , with all other coefficients zero, provided is interpreted modulo . For example, the four-point transform of is .
The integer labels a frequency bin rather than a frequency in physical units. If adjacent measurements are separated by , the sampling frequency is , and the bin spacing is
Bins at the start of the output represent zero and positive frequencies. Bins near the end represent negative frequencies: index can be interpreted as . The equivalence follows because adding an integer multiple of to a frequency leaves its values at the sampling times unchanged.
For even , the bin corresponds to the alternating sequence . Its frequency may be labeled or ; these labels describe the same sampled oscillation. For odd , no bin lies exactly at half the sampling frequency. Software frequently provides a frequency-shifting operation that places zero frequency in the center of an array, but this is only a rearrangement of coefficients. The mathematical DFT itself does not require centered coordinates or even a time interpretation: the sample index may describe position, angle, or any other uniformly spaced coordinate.
Orthogonality, symmetry, and linear algebra
The DFT is a linear map on the vector space . Writing , its matrix entries are
The key identity is the orthogonality of roots of unity:
For unequal frequency indices, the sum is a finite geometric series whose terms cancel. Consequently,
where denotes the conjugate transpose. Thus , proving the inversion formula without any limiting argument.
After scaling by , the DFT matrix is a unitary matrix. Its columns form an orthonormal basis under the usual complex inner product. The DFT can therefore be understood as a change of coordinates from individual sample values to oscillatory basis vectors. This interpretation explains why the transformation loses no information: it changes the description of a vector rather than reducing its dimension. It also connects the DFT to harmonic analysis on a finite cyclic group, whose characters are precisely the discrete complex exponentials.
Orthogonality gives Parseval’s identity,
More generally, if is the DFT of ,
Thus energy and inner products can be calculated in either representation, with the appropriate normalization. For the unitary convention, the factor disappears. These identities underlie spectral energy accounting, least-squares approximation by selected frequency components, and the analysis of numerical errors.
Several symmetries follow directly from the exponential kernel. If is real, then
so approximately half the output coefficients determine the rest. A circular shift gives
changing phase but not magnitude. Conversely, multiplication by shifts the spectrum by bins. Applying the unnormalized forward transform twice gives
Accordingly, four applications yield . These identities are exact finite-dimensional statements, not approximations inherited from continuous Fourier analysis.
Sampling, periodic extension, and continuous transforms
The DFT has several related interpretations that should be kept distinct. As a finite-dimensional transformation, it needs no assumptions about samples outside the given array. As a Fourier-series representation, however, its inverse defines an -periodic sequence:
The coefficients are the Fourier-series coefficients of this periodic discrete sequence. Periodicity is therefore built into the oscillatory representation, even when the original measurements came from a nonperiodic phenomenon. The transform can represent every finite input exactly; questions about periodicity arise when that representation is extended beyond the measured interval.
A different connection is provided by the discrete-time Fourier transform (DTFT). Extend the finite record by zeros and define
This function is continuous in and periodic with period . The DFT consists of its equally spaced samples:
The DTFT therefore has a continuous frequency argument despite its discrete-time input. The DFT has both a discrete input index and a discrete output index. Confusing these two transforms can obscure what zero-padding and frequency interpolation actually accomplish.
For a continuous signal sampled at frequency , frequencies separated by an integer multiple of produce identical sample sequences. This ambiguity is aliasing. For example, cosine waves at Hz and Hz give identical samples at a sampling rate of Hz when their phases are aligned appropriately. The sampling theorem states, under suitable hypotheses, that a signal band-limited to frequencies strictly below can be reconstructed from uniformly spaced samples. The DFT does not itself enforce band limitation, prevent aliasing, or reconstruct information already lost during sampling.
The relationship to a continuous Fourier transform also involves scaling and truncation. If , then
is a Riemann sum for a Fourier integral over the observation interval. Its accuracy depends on the sampling interval, the interval length, and the behavior of . A nonzero starting time introduces an additional phase factor. Consequently, an exact DFT of an array may still be only an approximation to the Fourier transform of an underlying continuous signal. Sampling error, finite-record effects, and numerical roundoff are separate issues with different causes.
Finite records, spectral leakage, and windowing
A finite observation record acts as multiplication by a rectangular observation window. If a sinusoid completes an integer number of cycles within the record, its frequency coincides with a DFT bin and its complex representation occupies a single bin. Otherwise, its contribution generally spreads across many coefficients, a phenomenon called spectral leakage. This spreading is not a failure of the DFT. It is the exact frequency representation of a finite segment whose periodically repeated continuation does not match the original sinusoid.
For the complex sinusoid
where need not be an integer, direct summation gives
with values at removable singularities defined by continuity. This Dirichlet-kernel shape has a central peak and sidelobes. When is an integer, the zeros coincide with the other DFT bins. When it is not, those bins sample nonzero sidelobes. Real sinusoids contribute positive- and negative-frequency components whose leakage patterns may overlap.
A window function replaces the raw record by , usually tapering its ends. Common choices include Hann, Hamming, and Blackman windows. One periodic Hann convention is
A symmetric convention instead uses in the denominator. Windowing can reduce sidelobes and make a weak component more visible beside a strong one, but it generally broadens the main lobe. It also changes amplitude and noise scaling. For a bin-centered complex sinusoid, the coefficient at its own frequency is , rather than . This distinction motivates coherent-gain corrections in amplitude measurements.
Zero-padding appends zeros before taking a longer DFT. If measured values are padded to length , the resulting transform samples the same finite-record DTFT at rather than frequencies. It gives a denser plot and may improve numerical localization of a spectral peak, but it adds no measurements and does not narrow the window’s main lobe. The ability to distinguish nearby components depends on observation duration, window choice, signal-to-noise ratio, and the estimation method—not simply on the displayed frequency spacing. Similarly, the word “resolution” may refer either to bin spacing or to the ability to separate two sources; these are related but not identical quantities.
Circular convolution and shift-invariant systems
For two length- sequences, circular convolution is defined by
If and are their DFTs, then
The inverse transform of the pointwise product therefore computes circular convolution. Conversely, multiplication in the sample domain gives circular convolution in the frequency domain, accompanied by a factor under the standard convention. These statements follow by interchanging finite sums and changing indices modulo .
Circular convolution differs from ordinary linear convolution because contributions that extend beyond index wrap around to the beginning. For example, the linear convolution of with itself is . A length-two circular convolution instead yields , because the final coefficient wraps onto the first. To recover the linear convolution of sequences of lengths and , both can be zero-padded to a transform length
The resulting circular convolution then contains the linear convolution without overlap between its wrapped copies. Here zero-padding serves an algebraic purpose distinct from interpolating a spectrum.
The matrix of circular convolution is a circulant matrix, whose rows or columns are cyclic shifts of one another. Every discrete complex exponential is an eigenvector of this matrix. If denotes convolution by , then
Thus the DFT simultaneously diagonalizes all circulant operators. The frequency response is their collection of eigenvalues. This explains why frequency-domain filtering reduces a coupled operation on samples to independent multiplication at each frequency.
The same principle supports correlation and deconvolution. With the circular cross-correlation convention
its DFT is . Correlation therefore provides a computationally efficient way to compare shifted signals. For deconvolution, a formal solution divides an observed spectrum by , but zeros prevent uniqueness and small values amplify noise. This is an inverse problem rather than merely a transform calculation. Regularization changes the inversion to control sensitivity, for example by replacing division by with multiplication by , where .
Fast algorithms and historical development
Direct evaluation of all DFT coefficients requires a number of arithmetic operations proportional to . Fast algorithms exploit structure in the exponential factors to reduce this cost, commonly to in asymptotic notation. The difference is substantial: for , the direct sum contains roughly sample–exponential products, whereas a radix-two factorization has only 20 stages, each with a number of elementary operations proportional to . Exact operation counts depend on the algorithm, data type, and treatment of multiplications by simple constants.
For even , split the input into even- and odd-indexed samples. Let and be their length- DFTs, and write . Then
The paired operations form a butterfly. Recursively applying this decomposition yields the radix-two Cooley–Tukey FFT. The factors are called twiddle factors. Other decompositions split the output frequencies rather than the input samples, or combine several factors at a time.
The historical development predates electronic computing. Around 1805, Carl Friedrich Gauss developed a related method for harmonic interpolation; the work was published posthumously in 1866. James W. Cooley and John W. Tukey’s 1965 paper made a general factorization widely known in modern computation. Earlier twentieth-century work, including Danielson and Lanczos’s 1942 contribution, also contained important fast-transform ideas. These episodes concern efficient evaluation of finite harmonic sums, rather than the invention of the Fourier viewpoint itself, which developed through the study of trigonometric series and mathematical physics.
The Cooley–Tukey approach extends beyond powers of two whenever factors into smaller integers. Mixed-radix implementations combine transforms of several sizes. Good–Thomas algorithms exploit relatively prime factors through the Chinese remainder theorem. For prime lengths, Rader’s algorithm converts the nontrivial part of the DFT into a cyclic convolution. Bluestein’s algorithm rewrites the kernel using
turning an arbitrary-length DFT into a chirp-based convolution. That convolution can itself be evaluated using a convenient FFT length.
Practical speed is not determined by arithmetic counts alone. Memory access, cache behavior, vector instructions, parallel communication, and data layout may dominate execution time. Modern libraries commonly select or plan among multiple factorizations. For a small number of desired frequency bins, direct evaluation or specialized recurrences may be preferable to calculating a full FFT. The DFT remains the same mathematical object across all these implementations; changing the algorithm does not change the ideal coefficients.
Multidimensional transforms and related finite transforms
The DFT extends naturally to arrays. For a two-dimensional array of size ,
The inverse has the opposite exponential sign and normalization . Each coordinate is periodic independently. In an image, the output indices describe horizontal and vertical spatial frequencies; in a three-dimensional volume, they describe three components of a spatial frequency vector.
The multidimensional kernel separates into a product of one-dimensional kernels. A two-dimensional DFT can therefore be computed by transforming every row and then every column, or in the reverse order. In tensor-product language, the full transformation is built from one-dimensional Fourier matrices. For an array with entries, separable FFT implementations require approximately arithmetic operations. Data rearrangement can nevertheless be expensive, especially when different dimensions reside on different processors.
Real-valued arrays retain conjugate symmetry, but the symmetry reverses all frequency coordinates together:
It does not generally imply separate symmetry under reversal of only one coordinate. Real-input FFT routines exploit this redundancy and store only an independent portion of the spectrum, often reducing the last transformed dimension to complex entries. Interpreting such packed arrays requires attention to which axis has been shortened and where the zero- and half-sampling-frequency components are stored.
The discrete cosine transform and discrete sine transforms are related but distinct transformations. They arise from particular even or odd extensions and from different placements of sample points relative to boundaries. Their boundary symmetries make them useful when straightforward periodic continuation is inappropriate. The number-theoretic transform instead replaces complex roots of unity with suitable roots in modular arithmetic. For a prime modulus , a transform length dividing can use an element of that order in the multiplicative group of nonzero residues. Such transforms support exact modular convolution and large-integer multiplication. They share the DFT’s algebraic pattern but do not directly express physical sinusoidal frequency amplitudes.
Numerical accuracy and spectral scaling
As a linear transformation, the unitary DFT has condition number 1 in the Euclidean norm. Consequently, small relative perturbations in the input do not become larger relative perturbations in the entire output vector merely because the transform is applied. This favorable conditioning should be distinguished from the relative accuracy of an individual coefficient. A coefficient that is theoretically zero or extremely small can have a large relative error even when the overall transform error is tiny. Cancellation in a particular frequency bin does not imply that the full transformation is ill-conditioned.
Actual implementations use floating-point arithmetic, so exponential factors and intermediate sums are rounded. Well-designed FFT algorithms generally have good numerical stability, with normwise error estimates often growing roughly with machine precision times , subject to implementation-dependent assumptions. Inaccurately generated twiddle factors, overflow, or poor scaling can degrade results. Fixed-point implementations must also account for growth in intermediate magnitudes and often distribute scale factors through the transform stages. An FFT may consequently differ slightly from a directly evaluated DFT, even though both target the same exact transformation.
Amplitude interpretation requires normalization appropriate to the signal. For a real, bin-centered cosine
with neither zero nor, for even , the half-sampling-frequency bin, the two corresponding coefficients have magnitudes . A one-sided amplitude spectrum therefore uses for these interior frequencies. The DC and half-sampling-frequency bins are not doubled because each is its own conjugate partner. Windowing changes these relations through the window’s gain, and nearby components or non-bin-centered frequencies complicate amplitude recovery.
Power spectra require a different scaling from amplitude spectra. For windowed data, a common two-sided power spectral density estimate is
Its units are squared signal units per hertz. Multiplying by and summing the bins gives the corresponding normalized windowed mean square. A one-sided version doubles interior positive-frequency contributions for real data. The squared magnitudes of DFT coefficients alone are therefore not automatically a correctly normalized density. In statistical analysis, a single-record periodogram can also have substantial variance; averaging spectra from segments reduces variability but changes effective frequency resolution.
Applications in measurement, communication, and scientific computing
Spectral analysis uses the DFT to identify oscillations, harmonics, and broad frequency bands in sampled measurements. Applications include vibration monitoring, acoustics, spectroscopy, and the analysis of time series. A rotating machine may produce a fundamental frequency associated with its rotation rate and additional harmonics associated with periodic forces. The DFT separates these contributions when the record length and signal quality permit. For nonstationary signals, the short-time Fourier transform computes transforms of overlapping windowed segments, producing a time–frequency representation. Its window duration determines a trade-off between temporal localization and frequency discrimination.
Digital filtering uses the convolution theorem to implement long filters efficiently. Processing a very long stream as a single transform is often impractical, so overlap-add and overlap-save methods divide the task into blocks. Overlap-add zero-pads blocks, computes their linear convolutions, and adds overlapping output portions. Overlap-save supplies overlapping input blocks and discards outputs contaminated by circular wraparound. Both methods preserve the desired linear convolution while exploiting FFT multiplication. Related techniques accelerate polynomial products and correlations used in synchronization, pattern matching, and displacement estimation.
In orthogonal frequency-division multiplexing (OFDM), an inverse DFT combines complex data symbols into a sampled waveform carried by many orthogonal subcarriers. A receiver applies a DFT to recover their coefficients. A cyclic prefix copies the end of a transmitted block to its beginning. If the prefix covers the relevant channel delay spread and synchronization assumptions are met, the retained receiver block behaves as a circular convolution with the channel. The DFT then reduces channel equalization to multiplication or division independently at each subcarrier. This is an engineering use of circulant diagonalization, rather than simply a display of a signal’s spectrum.
In scientific computing, spectral methods represent spatial fields through Fourier coefficients. For a periodic domain of length , differentiation of a mode with angular wavenumber multiplies its coefficient by ; a second derivative multiplies it by . This converts many differential operations into diagonal calculations. For example, a periodic Poisson equation becomes
at nonzero wavenumbers. The zero mode requires a compatibility condition and a choice of the solution’s mean. Nonlinear products generate higher frequencies that can alias onto represented modes, so padding or spectral truncation is often used to control this effect. In magnetic resonance imaging, inverse discrete Fourier methods also reconstruct images from appropriately sampled spatial-frequency data; sampling geometry and incomplete measurements determine whether further reconstruction methods are needed.