Discrete Fourier transform ($X_k={\sum }_{n=0}^{N-1}{x}_n{e}^{-2\pi ink/N}$)

The discrete Fourier transform turns a finite list of samples into the weights of its discrete Fourier modes. The goal is to reveal a simple oscillatory recipe hidden in complicated-looking data, while retaining enough information to reconstruct every sample exactly. In signal processing, those weights identify sampled frequencies and wave phases; in numerical analysis, they simplify circular convolution and the discrete sine transform Poisson solver.

Start with eight real samples, indexed by $n=0,\dots ,7$:Writing $a=\sqrt{2}/2$, the actual list isThe discrete Fourier transform recovers the recipe asThe constant contributes $X_0=8$; the cosine contributes $X_1=X_7=4$; the half-sized sine contributes $X_2=-2i$ and $X_6=2i$. All other coefficients vanish exactly. The imaginary coefficients carry the sine's wave phase, which a plot of absolute values alone would hide.

Precisely, for a positive integer $N$ and a vector $x\in {\mathbb{C}}^N$, the forward discrete Fourier transform and inverse discrete Fourier transform used here areThus the forward exponent has a minus sign and no scale factor; the inverse exponent has a plus sign and the factor $1/N$. The coefficients in the reconstruction are $X_k/N$, rather than $X_k$. In the example, $X_0/8=1$, the pair $4/8$ reconstructs the cosine, and the pair $-2i/8,2i/8$ reconstructs the half-sized sine. These conventions agree with the scaled Fourier coefficients in MIT's authored notes.^[ref]

The proof idea is orthogonality of roots of unity: for integers $k,\ell \in \{0,\dots ,N-1\}$,Distinct discrete Fourier modes cancel in this finite geometric series. Substituting the forward formula into the inverse discrete Fourier transform leaves only the desired sample. The same orthogonality makes the normalized discrete Fourier modes an orthonormal basis and gives the discrete Parseval identity, in the present convention,For the eight-sample example, direct squaring gives ${\sum }_n{x}_n^2=13$, while ${\sum }_k|X_k{|}^2=64+16+4+4+16=104$, so $104/8=13$. This identity preserves the squared L2 norm after accounting for normalization. The existing discrete Parseval identity instead scales the forward discrete Fourier transform by $N^{-1/2}$, producing a unitary matrix and equal squared L2 norms without the factor $1/N$.

For real input, discrete Fourier conjugate symmetry pairs positive and negative frequencies. The label $k$ is a residue modulo $N$: $k=7$ when $N=8$ represents the same discrete Fourier mode as $k=-1$, since $e^{2\pi i7n/8}=e^{-2\pi in/8}$. It therefore represents negative frequency $-1/8$ cycles per sample. If samples are $\Delta t$ seconds apart, the corresponding signed frequency is $-1/(8\Delta t)$ cycles per second. Similarly, index $6$ represents $-2$, while index $4$ is its own negative modulo $8$.

The discrete Fourier transform is an invertible map between two finite vectors. The continuous Fourier transform instead describes a function on the real line by an integral over a continuous frequency variable. A finite list of samples does not determine the full continuous frequency spectrum: aliasing of discrete Fourier modes already supplies distinct waveforms with identical observations. Applying the inverse formula at arbitrary integer indices gives the periodic extension of a finite sequence, repeating the recorded block every $N$ samples. This is a property of that representation, rather than evidence that the physical signal repeats beyond the recording. Laurent Demanet's MIT notes place the discrete Fourier transform alongside the continuous Fourier transform and Fourier series to explain the role of sampling and repetition.^[ref]

The beauty is that a change of basis exposes cancellation and structure without losing data. Direct evaluation needs $N$ sums of $N$ terms; a Fast Fourier transform computes the same discrete Fourier transform with far less work. Computational speed and the mathematical meaning of the coefficients are separate questions.

A number-theoretic transform is a discrete Fourier transform computed in modular arithmetic. In a finite field with $p$ elements, choose a primitive root of unity $\omega$ of order $L$ dividing $p-1$. The transform above is inverted using ${\omega }^{-1}$ and $L^{-1}$. With sufficient zero padding, it computes polynomial products exactly modulo $p$, avoiding floating-point arithmetic rounding.

For $N$ equally spaced samples at sampling rate $f_s$, the discrete Fourier transform has frequency bins spaced by $f_s/N=1/T_{\mathrm{obs}}$. A rectangular observation window broadens a sinusoid into a sinc function profile whose nearest zeros are $1/T_{\mathrm{obs}}$ from its central frequency. This sets a conventional scale for distinguishing nearby spectral components. It is not a universal lower bound on the uncertainty of frequency estimation for an isolated tone: a specified signal model and noise level can allow precision finer than the bin spacing. Padding with zeros interpolates the spectral display without increasing the observation duration.

For real samples, taking the complex conjugate of the forward discrete Fourier transform changes the exponent's sign and proves the displayed symmetry. Hence $X_0$ is real; for even $N$, $X_{N/2}$ is also real. In the eight-sample example, $X_7=\overline{X_1}=4$ and $X_6=\overline{X_2}=2i$. This is the finite counterpart of conjugate symmetry of trigonometric polynomial coefficients. It reduces storage for real signals and provides a quick consistency check on a computed discrete Fourier transform.

A block $x_0,\dots ,x_{N-1}$ determines a repeating sequence by setting $x_n=x_{n\mathrm{mod}N}$ for every integer $n$. The inverse discrete Fourier transform gives this extension because each discrete Fourier mode satisfies $e^{2\pi ik(n+N)/N}=e^{2\pi ikn/N}$. The extension explains why circular convolution wraps indices around the block. It specifies values at discrete indices; a continuous curve between samples requires an additional choice of interpolation.

For integers $m,q,n$, adding $qN$ to a frequency index changes the complex exponential by $e^{2\pi iqn}=1$. Thus different continuous Fourier modes become identical discrete Fourier modes on the sampling grid. This is aliasing, caused by sampling before any discrete Fourier transform is computed.

For $N=8$, compare the continuous functions $\cos (2\pi mt)$ and $\sin (2\pi mt)$ with $m=1$ and $m=9$, sampled at $t=n/8$, $n=0,\dots ,7$. With $a=\sqrt{2}/2$, both cosines give exactly the first row and both sines give exactly the second:The nine-cycle sine agrees in sign as well as magnitude with the one-cycle sine: the frequency indices differ by $8$, rather than by a sign reversal. Consequently, either cosine produces the same discrete Fourier transform, $X_1=X_7=4$ with all other coefficients zero; either sine produces $X_1=-4i$, $X_7=4i$, with all other coefficients zero.

An observed low frequency therefore does not establish that physical high frequencies are absent. To exclude such alternatives, the Nyquist–Shannon sampling theorem requires a specified class of bandlimited functions. For arbitrary pure sinusoids with frequencies at most $B$, choose sampling rate $f_s>2B$; equality needs care because $\sin (2\pi (f_s/2)t)$ vanishes at every $t=n/f_s$. The finite-energy L2 space version of the Nyquist–Shannon sampling theorem permits equality under its own hypotheses. In either case, exact continuous reconstruction generally requires the entire infinite sample sequence; eight observed samples alone do not supply it. Demanet derives the grid aliasing condition as a difference by an integer multiple of the sampling angular frequency.^[ref]

At uniform sampling times $t_n=n/f_s$, adding an integer multiple of the sampling rate to a sinusoid's frequency changes its complex phase by an integer multiple of $2\pi n$. The samples therefore agree. Real cosines also identify the two signs of frequency, giving the displayed representative below the Nyquist frequency. A chosen nonzero sampling-time origin changes the equivalent phase, rather than the alias frequency.

For a prime $p$, distinct row and column residues and $\zeta =e^{2\pi i/p}$, every square discrete Fourier transform submatrix is nonsingular. Sort the selected column exponents decreasingly as $b_i$ and write $b_i={\lambda }_i+N-i$. Its determinant factors by the bialternant formula into a nonzero Vandermonde determinant and $s_{\lambda }({\zeta }^{r_1},\dots ,{\zeta }^{r_N})$. Modulo $1-\zeta$, this Schur factor is $s_{\lambda }(1^N)$ in ${\mathbb{F}}_p$. The Schur evaluation at all ones product has numerator and denominator differences strictly between zero and $p$, so its residue is nonzero. The Schur factor, and hence the minor, cannot vanish.

If $\omega$ is a primitive $n$th root in a finite field and the field characteristic does not divide $n$, the inverse transform is $c_j=n^{-1}{\sum }_{\ell =0}^{n-1}{\hat{c}}_{\ell }{\omega }^{-j\ell }$. The identity ${\sum }_{j=0}^{n-1}{\omega }^{jm}=0$ unless $n\mid m$, when the sum is $n$, proves inversion. For a primitive cyclic Reed-Solomon code, encoding assigns the $k$ unconstrained transform values and makes the remaining values zero; received transform values at those zeros are syndromes.

With normalization ${\hat{U}}_k=N^{-1/2}{\sum }_m{U}_m{e}^{-2\pi imk/N}$, the discrete Fourier transform is a unitary matrix. Orthogonality of the roots-of-unity vectors gives the displayed identity. Multiplying both sides by the grid spacing gives the corresponding discrete L2 norm. Modal contraction therefore proves grid-norm contraction without a mesh-dependent change-of-basis constant.

Orthogonality of integer-frequency Fourier modes gives this identity: the integral is one for $n=m$ and zero otherwise. It converts integer step-count constraints into products of generating functions, as in the dilute-hopping lattice propagator.

${\lambda }_j=2\pi j/T$ is a frequency of the length-$T$ discrete Fourier transform. Distinct interior frequencies give orthogonal sine and cosine vectors; for a Gaussian white noise record this makes the corresponding Fourier components independent.

The inverse discrete Fourier transform reconstructs samples from their discrete Fourier transform. Under one common normalization,moving the factor $1/n$ between the forward and inverse transforms gives other standard conventions.

On a cyclic index set of length $n$, the $k$th discrete Fourier mode is the vector with $j$th coordinate $e^{2\pi ikj/n}$. Its real and imaginary parts are the corresponding cosine and sine modes.

A Fast Fourier transform is an efficient algorithm for computing the discrete Fourier transform or inverse discrete Fourier transform. The discrete Fourier transform specifies the mathematical result; a Fast Fourier transform specifies how to compute it. Different Fast Fourier transform algorithms reorganize the same finite sums, with the selected sign and normalization. The Cooley-Tukey FFT algorithm is one important family of Fast Fourier transforms, using factorization of the record length.^[ref]

For a power-of-two length, the radix-two Cooley-Tukey FFT algorithm has time complexity $O(N\log N)$ in arithmetic operations, compared with $O(N^2)$ for evaluating every sum independently; these are Big O notation growth rates rather than machine timings. It returns the same eight coefficients $(8,4,-2i,0,0,0,2i,4)$ in the example. In exact arithmetic this reorganization introduces no approximation; actual implementations still incur roundoff error.

The radix-two Cooley--Tukey algorithm recursively splits a discrete Fourier transform into transforms of the even-indexed and odd-indexed samples. For a power-of-two length this evaluates the transform in $O(m\log m)$ arithmetic operations.

The saving comes from reusing the two shorter discrete Fourier transforms for both halves of the output, through an FFT butterfly. For $N=2^p$, each level of the even--odd fast Fourier transform recursion needs work proportional to $N$, and there are $p={\log }_{2}N$ levels. This gives the $O(N\log N)$ time complexity without changing the discrete Fourier transform being computed.

James W. Cooley and John W. Tukey published An Algorithm for the Machine Calculation of Complex Fourier Series in Mathematics of Computation 19 (1965), pp. 297–301. Their original paper factors a composite length as $N=r_1\cdots r_p$, derives an operation count $N(r_1+\cdots +r_p)$, and discusses powers of two and in-place storage. Its opening explicitly builds on earlier algorithms by I. J. Good; the 1965 paper is a landmark computational formulation, rather than the invention of the underlying Fourier analysis. Its positive-exponent convention also illustrates why a Fast Fourier transform's exponent sign must be specified.^[ref]

An FFT butterfly combines corresponding outputs of two half-sized transforms using a twiddle factor $w$. Sharing the product $wb$ costs one complex multiplication and two additions. For the unnormalized positive-exponent inverse discrete Fourier transform of length $2m$, use $w=e^{2\pi i\ell /(2m)}$ at index $\ell$.

For ${\omega }_m=e^{-2\pi i/m}$ and length-$m/2$ transforms $E_k,O_k$ of the even and odd samples,

The type-II discrete cosine transform of $x_0,\dots ,x_{N-1}$ is

Reflect $x$ evenly to length $2N$ by $y_n=x_n$ and $y_{2N-1-n}=x_n$. If $Y$ is the discrete Fourier transform of $y$, thenThis reduction computes the cosine transform with one fast Fourier transform and $O(N)$ additional work.

One half-grid sine-transform convention is

For $-\Delta u=f$ on a square with homogeneous Dirichlet boundary conditions, the five-point finite difference operator on a mesh $h=1/N$ is diagonalized by $\sin (\pi ki/N)\sin (\pi \ell j/N)$. Its eigenvalues are ${\lambda }_{k\ell }=4h^{-2}[{\sin }^2(\pi k/(2N))+{\sin }^2(\pi \ell /(2N))]$. A two-dimensional discrete sine transform, division by these nonzero eigenvalues and the inverse transform give the solution. Odd extension realizes each one-dimensional transform by a Fast Fourier transform of length $2N$, making the total cost $O(N^2\log N)$ and storage $O(N^2)$. These finite-difference eigenvalues should not be confused with the continuous spectral eigenvalues ${\pi }^2(k^2+{\ell }^2)$.

If ${\xi }_n=(-1{)}^n{x}_n$ and $C_j(\xi )$ is its type-II cosine transform, thenThus a sign modulation, one fast cosine transform, and output reversal give an $O(N\log N)$ sine-transform algorithm.