# Discrete Fourier transform The **discrete Fourier transform** (DFT) is the version of the [[Fourier_transform]] that acts on a finite [[Sequence|sequence]] of N numbers and returns another sequence of N complex numbers, `X_k = Σ_{n=0}^{N−1} x_n exp(−j 2π k n / N)`, each of which gives the amplitude and phase of one frequency bin. It is the only Fourier transform a computer can evaluate directly: a [[Signal|signal]] sampled at fs for T seconds gives N = fs T samples, and its DFT is the spectrum at the N frequencies k/T, spaced 1/T apart and repeating every fs. The inverse DFT recovers the samples exactly, so the two sequences are the same information in the [[Time_domain|time]] and [[Frequency_domain|frequency]] domains. Because the DFT is a finite sum it inherits its properties from the [[Fourier_series]], of which it is a sampled version, and from the [[Discrete-time_Fourier_transform|discrete-time Fourier transform]], which it samples in frequency. Both the samples and the bins are implicitly periodic, which is why its convolution theorem is circular and why a tone that does not complete a whole number of cycles in the record leaks into every bin. In practice the DFT is evaluated by a [[Fast_Fourier_transform|fast Fourier transform]], which computes the same numbers in a fraction of the operations. The primary microsim on this page, *Discrete Fourier transform*, lets the reader build a signal from three sine harmonics, change the record length N from 8 to 128, and pick a bin k to see its basis sinusoid drawn against the samples with the products shaded, while the magnitude and phase of every bin are plotted beside them. ## Definition For a sequence x_0, …, x_{N−1} the transform is `X_k = Σ_{n=0}^{N−1} x_n exp(−j 2π k n / N)` for k = 0, …, N − 1, and the inverse is `x_n = (1/N) Σ_{k=0}^{N−1} X_k exp(+j 2π k n / N)`. The kernel exp(−j2πkn/N) is the N-th root of unity raised to the power kn, so the transform is a multiplication of the sample vector by an N × N matrix of powers of one complex number. Bin k is a sinusoid completing exactly k cycles in the record; the bins from N/2 upward are the negative frequencies, and bin N/2 is the [[Nyquist_frequency|Nyquist]] bin.[^tm134] This unscaled form is the one the microsim computes: with the default signal and N = 32, the sketch reports |X[1]| = 12.80, |X[3]| = 6.40 and |X[5]| = 3.20, each equal to N times half the harmonic's amplitude. ### DFT including sampling interval When the samples come from a continuous signal at spacing Δt, the sum approximates the Fourier integral and carries the factor Δt: `X_k = Δt Σ_n x_n exp(−j 2π k n / N)`, with the inverse `x_n = Δf Σ_k X_k exp(+j 2π k n / N)` and Δf = 1/T = fs/N.[^tm129] In this convention a cosine of amplitude A on bin ℓ gives `X_k = (Δt N/2)(δ_{k−ℓ} + δ_{k−(N−ℓ)})`, two bins of height AT/2, and X_0 is T times the average of the record.[^tm139][^tm134] Most software omits the Δt and returns the bare sum, so a unit cosine on a bin reads N/2 rather than T/2, and the convention has to be stated before a magnitude is quoted.[^tm129] ### Interpretations The transform can be read three ways. As a correlation, X_k is the inner product of the samples with a complex sinusoid of k cycles, which is what the microsim's basis panel shows: the cosine cos(2πkn/N) drawn over the samples, the products as shaded bars, and their sum as the real part of X_k. As a [[Fourier_series]], the N samples define one period of a periodic sequence whose coefficients are X_k/N. As a sampling of the [[Discrete-time_Fourier_transform|discrete-time Fourier transform]] of the record, the bins are values of a continuous spectrum at spacing 1/T, and the spectrum between them is what leakage and zero-padding reveal.[^tm122] ## Example The textbook's worked case is a 3 Hz cosine sampled at 10 Hz for 2 s, so N = 20 and Δf = 0.5 Hz; the tone falls on bin ℓ = 6, and the transform is X_6 = X_14 = 1 with every other bin zero, the imaginary parts computing to about 10⁻¹⁶ from round-off alone.[^tm139] Sampled at 20 Hz for 2 s or at 10 Hz for 4 s the tone gives N = 40 either way, but with bin spacings of 0.5 Hz and 0.25 Hz: the record length, not the sample count, sets the resolution.[^tm139] A 4 Hz cosine observed for 1 s at 64 samples per second gives a single bin |X_4| = 0.5 in the Δt convention, while a 4.5 Hz cosine, which completes four and a half cycles, leaks across many bins.[^tm143] The microsim's example is the sum of sines at 1, 3 and 5 cycles per record with amplitudes 0.8, 0.4 and 0.2. At N = 32 the magnitude panel shows bars at bins 1, 3 and 5 and their mirror images at 31, 29 and 27, with phases of −90° and +90° because a sine is odd; doubling N to 64 doubles every bar to 25.60, 12.80 and 6.40, because the unscaled sum grows with the number of samples while the amplitude does not. At N = 8 the fifth harmonic lies above the Nyquist bin, N/2 = 4, and [[Aliasing|aliases]] onto bin 3 with reversed sign, so the sketch shows |X[3]| = 0.80 instead of the 1.60 the third harmonic alone would give. ## Properties ### Linearity The DFT of a x + b y is a X + b Y for any constants, since it is a matrix multiplication. In the microsim the three harmonic sliders add independently, each contributing its own pair of bins; only the rescaling applied when the sum exceeds unit amplitude couples them. ### Time and frequency reversal Reversing the samples, x_{(−n) mod N}, reverses the bins to X_{(−k) mod N}; the transform commutes with reversal, so an even sequence has an even transform. ### Conjugation in time Conjugating the samples conjugates and reverses the transform: x_n* ↔ X*_{(−k) mod N}. Combined with linearity this gives the symmetries of real and imaginary signals below. ### Real and imaginary part The real part of x transforms to the conjugate-symmetric part of X, (X_k + X*_{−k})/2, and the imaginary part to the conjugate-antisymmetric part. A real even sequence therefore has a real transform and a real odd sequence a purely imaginary one, which is why the microsim's sine harmonics land on bins with phase exactly ±90°. ### Orthogonality The N sinusoids exp(j2πkn/N) are [[Orthogonality|orthogonal]] over the record: the sum over n of exp(j2π(k − l)n/N) is N when k = l and zero otherwise, since the roots of unity of any non-trivial order sum to zero. This is what makes the inverse formula work and each bin independent of the others when every component completes a whole number of cycles. ### The Plancherel theorem and Parseval's theorem Energy is preserved up to the factor N: `Σ_n |x_n|² = (1/N) Σ_k |X_k|²`, and inner products likewise. With the Δt convention the factor becomes Δt against Δf, the discrete form of the continuous energy theorem. ### Periodicity Both sequences are periodic with period N: X_{k+N} = X_k because the kernel repeats, and the inverse formula returns a periodic extension of the samples. Bin N − k is bin −k, so for a real signal X_{N−k} = X_k* and only the bins up to N/2 carry information.[^tm134] The same fact governs sampled sinusoids: a discrete-time frequency is unique only within half a cycle per sample, and a 0.8 Hz cosine sampled at 8 Hz repeats every 10 samples, while a √2 Hz cosine never repeats at all.[^j25][^tm130] ### Shift theorem A circular shift of the samples by m multiplies bin k by exp(−j2πkm/N), leaving every magnitude unchanged; a multiplication by exp(j2πln/N) shifts the bins by l. Both are the periodic versions of the continuous shift rules. ### Circular convolution theorem and cross-correlation theorem The product X_k Y_k transforms back to the circular convolution of x and y, in which indices wrap around modulo N; the product X_k Y_k* gives the circular cross-correlation. Linear [[Convolution|convolution]] of two sequences of lengths L and M is obtained by zero-padding both to at least L + M − 1 so that the wrap-around never overlaps, which is how a [[Fast_Fourier_transform|fast Fourier transform]] filters long records. ### Uniqueness of the Discrete Fourier Transform The DFT matrix is invertible, so two different sequences of length N cannot have the same transform and a sequence is fixed by its N bins, the discrete counterpart of the inversion theorem. ### Convolution theorem duality Multiplying two sequences sample by sample transforms to the circular convolution of their transforms divided by N. Multiplying a record by a [[Window_function|window]] therefore convolves its spectrum with the window's transform, the mechanism of leakage.[^tm96] ### Trigonometric interpolation polynomial The inverse formula, read for non-integer n, is a trigonometric polynomial that passes through every sample, and with the bins above N/2 assigned to negative frequencies it is the smoothest such interpolant; its coefficients X_k/N are the sense in which the DFT converts sample values into the coefficients of an interpolating sum of sinusoids. ### The unitary DFT Dividing the matrix by √N makes it unitary: its inverse is its conjugate transpose, and it then preserves norms exactly. The unscaled matrix, the 1/N-scaled inverse and the unitary pair are three normalisations of one transform, and software libraries differ on which they use.[^tm129] ### Expressing the inverse DFT in terms of the DFT Because the inverse differs from the forward transform only in the sign of the exponent and the factor 1/N, it can be computed with a forward routine: conjugate the bins, transform, conjugate the result and divide by N, or equivalently swap real and imaginary parts before and after. ### Eigenvalues and eigenvectors The unitary DFT applied four times is the identity, so its eigenvalues are ±1 and ±j, each with multiplicity close to N/4. Its eigenvectors are not unique, but a sampled Gaussian is close to one, as the continuous Gaussian is for the integral transform. ### Uncertainty principles A sequence and its transform cannot both be concentrated on few indices: the number of non-zero samples times the number of non-zero bins is at least N, with equality for impulse trains, and the entropies of |x|² and |X|², normalised as [[Probability|probability]] distributions, are bounded below in sum. A single impulse has a flat spectrum, and a single bin is a sinusoid filling the whole record. ### DFT of real and purely imaginary signals For a real signal the bins are conjugate-symmetric, so bins 1 to N/2 − 1 pair with N − 1 down to N/2 + 1 and the transform of N real samples carries N independent real numbers, as it must. Two real signals can be transformed at once by placing one in the real part and one in the imaginary part of a complex record and separating the spectra by symmetry afterwards. ## Generalized DFT (shifted and non-linear phase) Shifting the indices in the kernel by fractions, `X_k = Σ_n x_n exp(−j 2π (k + b)(n + a)/N)`, gives a family of transforms with the same structure; the half-sample shifts a = 1/2 or b = 1/2 produce the odd-time and odd-frequency transforms from which the [[Discrete_cosine_transform|discrete cosine transform]] and its sine counterpart are built. Replacing the linear phase 2πkn/N by a quadratic one gives a chirp transform that evaluates the spectrum along a spiral in the [[Z-transform|z-plane]] rather than on the unit circle. ## Multidimensional DFT For an array x with indices n_1, …, n_d the transform is the same sum over every index with a kernel that is a product of one-dimensional kernels, so it is separable: transforming each row, then each column, of an image gives its two-dimensional spectrum. The result is the tool of frequency-domain [[Digital_image_processing|digital image processing]], where a spatial-frequency bin corresponds to a [[Plane_wave|plane wave]] across the picture. ### The real-input multidimensional DFT A real array has a conjugate-symmetric spectrum in every index at once, X_{k_1, …, k_d} = X*_{−k_1, …, −k_d}, so only half the output need be computed or stored, the same saving as in one dimension. ## Applications ### Spectral analysis The DFT of a sampled record is the basic spectrum analyser of [[Digital_signal_processing|digital signal processing]]. Three limits govern it. The bin spacing is 1/T, so a 441-sample segment of audio at 44.1 kHz resolves frequencies only to 100 Hz.[^d70] Tones that do not complete whole cycles leak: multiplying a signal by the rectangular observation window convolves its spectrum with `T sinc(T f)`, whose main lobe is 2/T wide, so two tones closer than about 1/T merge, and a weak tone of a quarter the amplitude of a stronger neighbour is masked at a separation of 1/T, visible but biased at 2/T and clear at 5/(2T).[^tm96] Zero-padding the record to a length T_x shrinks the bin spacing to 1/T_x and draws the spectrum more finely, but adds no resolution, since the observation is unchanged.[^tm143] A smoother window such as the Hann trades a main lobe twice as wide for much lower side lobes.[^tm96] [[Spectral_leakage|Leakage]] has its own page, and a sequence of short DFTs along a signal gives a [[Spectrogram|spectrogram]]. ### Optics, diffraction, and tomography The far-field diffraction pattern of an aperture is the Fourier transform of its transmission, so a sampled aperture and a two-dimensional DFT predict the pattern, and the relation read backwards recovers structure from diffraction intensities in [[X-ray_crystallography|crystallography]]. In [[CT_scan|computed tomography]] each projection's transform is a slice of the object's two-dimensional transform, and the image is rebuilt by assembling the slices and inverting. ### Filter bank The DFT is a bank of N narrow band-pass filters, each bin the output of a filter centred on k/T with the window's transform as its shape, sampled once per record. A [[Filter_bank|filter bank]] built from overlapping windowed DFTs is the analysis stage of a [[Short-time_Fourier_transform|short-time Fourier transform]] and of most audio coders. ### Data compression Because natural signals concentrate their energy in few bins, a transform followed by [[Quantization_(signal_processing)|quantization]] of the small coefficients is the basis of transform coding. The [[Discrete_cosine_transform|discrete cosine transform]], a real-valued relative of the DFT, is preferred in [[Image_compression|image compression]] and audio [[Data_compression|data compression]] because it avoids the discontinuity that periodic extension introduces at the record's ends. ### Partial differential equations For a linear [[Partial_differential_equation|partial differential equation]] with periodic boundary conditions, the DFT turns spatial derivatives into multiplications by j2πk/L, so a spectral method advances each bin independently and differentiates with an accuracy limited only by the smoothness of the solution. The heat equation on a ring, solved this way, damps bin k at a rate proportional to k², the discrete form of Fourier's own calculation. ### Polynomial multiplication The product of two polynomials has coefficients equal to the linear convolution of their coefficient sequences, so two polynomials of degree less than N/2 can be multiplied by transforming both with an N-point DFT, multiplying bin by bin and transforming back. Because a long integer is a polynomial evaluated at its base, the same procedure multiplies large integers, with carries propagated afterwards, in about N log N operations rather than N², and the convolution of any two finite sequences, including the filtering of a long record by a finite impulse response, is done the same way. ## Some discrete Fourier transform pairs The table uses the unscaled sum and index arithmetic modulo N; δ is the unit impulse and ℓ, m are integers. | x_n | X_k | |---|---| | `δ_n` | `1` | | `1` | `N δ_k` | | `δ_{n−m}` | `exp(−j 2π k m/N)` | | `exp(j 2π ℓ n/N)` | `N δ_{k−ℓ}` | | `cos(2π ℓ n/N)` | `(N/2)(δ_{k−ℓ} + δ_{k−(N−ℓ)})` | | `sin(2π ℓ n/N)` | `(N/2j)(δ_{k−ℓ} − δ_{k−(N−ℓ)})` | | rectangle, 1 for n < M | `exp(−jπk(M−1)/N) sin(πkM/N)/sin(πk/N)` | | `x_n y_n` | `(1/N) Σ_m X_m Y_{k−m}` | The cosine and sine rows are the microsim's default signal, bin by bin: the sine's factor 1/j is the −90° phase the sketch shows at bins 1, 3 and 5. The rectangle's transform is the Dirichlet kernel, the discrete sinc whose sampled values at the bins are all zero except at k = 0 when M = N, and whose off-bin values are the leakage of a truncated tone. ## Generalizations ### Representation theory The kernel sequences exp(j2πkn/N) are the characters of the cyclic [[Group_theory|group]] of integers modulo N, and the DFT is the Fourier transform on that group: the decomposition of the group algebra into its N one-dimensional representations, with the convolution theorem as the statement that convolution is the algebra's product. ### Other fields The construction needs only an element of order N in a [[Field_(mathematics)|field]], so a DFT exists over finite fields whenever such a root of unity does. This number-theoretic transform has exact integer arithmetic, no round-off, and the same convolution theorem, which makes it the tool of choice for the large-integer multiplication above and for parts of [[Cryptography|cryptography]]. ### Other finite groups On any finite group the characters of an abelian group give way to matrix-valued irreducible representations, and the transform of a function on the group is a set of matrices, one per representation, whose total size is the order of the group; a fast transform exists for many such groups. ## Alternatives The [[Discrete-time_Fourier_transform|discrete-time Fourier transform]] gives the continuous spectrum of an infinite sequence and the [[Z-transform]] adds a radial variable; the DFT samples both on the unit circle. The [[Discrete_cosine_transform|discrete cosine transform]] is real and better suited to compression; the [[Discrete_wavelet_transform|discrete wavelet transform]] trades a single frequency axis for a time–scale plane; [[Least-squares_spectral_analysis|least-squares spectral analysis]] fits sinusoids to samples that are not equally spaced; and where only a few bins are wanted, direct evaluation of those bins costs less than a full [[Fast_Fourier_transform|fast Fourier transform]]. ## Microsims The *Discrete Fourier transform* sketch shows a DFT in four panels. The top panel plots the input x[n], a sum of sines at 1, 3 and 5 cycles per record with amplitudes set by the sliders *Harmonic 1 (k=1)*, *Harmonic 2 (k=3)* and *Harmonic 3 (k=5)*, each 0–100 read as hundredths of unit amplitude, defaults 80, 40 and 20, the sum being rescaled to unit peak if it exceeds one. The second panel draws the basis cosine cos(2πkn/N) for the bin chosen with the slider *Highlighted bin* (0 to N − 1, default 3) over the samples, shades each product as a bar and prints |X[k]|; the bars are the real part of the correlation only, so for these sine inputs they cancel even at a bin where |X[k]| peaks, the magnitude coming from the imaginary part. The lower panels plot the magnitude and the phase in radians of all N bins with bin k highlighted, and the slider *DFT length (N)* sets N as a power of two from 8 to 128, default 32; nothing is divided by N, so the bars scale with the record length. A three.js companion on this page renders the leakage picture in depth, opening on a bin-centred tone and moving it half a bin off. *Try:* With the defaults, read |X[3]| = 6.40 at N = 32, then slide the DFT length to 64 and to 128 and watch it double to 12.80 and 25.60 while the waveform does not change. Then set N to 8: the fifth harmonic now lies above the Nyquist bin and folds onto bin 3, and |X[3]| drops to 0.80. ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Discrete_Fourier_transform) : [Wikitube](https://en.wikitube.io/wiki/Discrete_Fourier_transform) Skeleton mirrored at revision 1372584078. Prose, emphasis and the microsims are Wikitube's own. ## See also - [[Fast_Fourier_transform]] - [[Spectral_leakage]] - [[Discrete_cosine_transform]] - [[Discrete-time_Fourier_transform]] - [[Fourier_transform]] - [[Fourier_series]] - [[Window_function]] - [[Sampling_(signal_processing)]] - [[PORTAL_Signal_Processing]] ## Notes The sketch is ILLUSTRATIVE in one respect: its basis panel draws only the cosine, the real part of the kernel, so the shaded products show the real part of the correlation and not the magnitude printed beside them. Its transform is the unscaled sum, without the Δt factor of the textbook convention. Page numbers in the references are PDF pages of the open editions. ## References [^tm129]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 129–133 (PDF pages): windowing of the sampled record, the bin spacing fs/N = 1/T, the DFT pair with the Δt factor, its omission in software, and the N² against N log₂ N operation counts. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm130]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 130–131 (PDF pages): a 0.8 Hz cosine sampled at 8 Hz repeating every 10 samples, a √2 Hz cosine that never repeats, and 1.12 Hz repeating after 50 samples. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm134]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 134–138 (PDF pages): the layout of the coefficients, X_{N−k} = X_k*, X_0 as T times the average, and the Nyquist bin. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm139]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 139–142 (PDF pages): the 3 Hz cosine at 10 Hz for 2 s with X_6 = X_14 = 1, the two 40-sample records with different bin spacings, and the transform of a cosine on bin ℓ. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm143]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 143–146 (PDF pages): the 4 Hz and 4.5 Hz cosines at 64 samples per second, and zero-padding from T = 4 s to T_x = 10 s. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm96]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 96–103 (PDF pages): the rectangular window transform T sinc(T f), two-tone resolution at separations of 1/T to 5/(2T), the masking of a weak tone of relative amplitude 0.25, and the Hann window. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm122]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 122–123 (PDF pages): the discrete-time Fourier transform. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^j25]: Johnson, D. *Fundamentals of Electrical Engineering I*. 2014, pp. 25–26 (PDF pages): discrete-time frequency is unique only for f between −1/2 and 1/2 cycle per sample. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/fundamentals-of-electrical-engineering-1 . CC BY. [^d70]: Downey, A. *Think DSP: Digital Signal Processing in Python*. 2012, pp. 70–71 (PDF pages): a 0.01 s segment at 44.1 kHz is 441 samples and resolves frequency to 100 Hz. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/think-dsp-digital-signal-processing-in-python . CC BY-NC. ## Further reading - Christian Tiberius; Max Mulder. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026. CC BY. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory - Don Johnson. *Fundamentals of Electrical Engineering I*. 2014. CC BY. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/fundamentals-of-electrical-engineering-1 - Allen Downey. *Think DSP: Digital Signal Processing in Python*. 2012. CC BY-NC. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/think-dsp-digital-signal-processing-in-python - Michael Stiber; Bilin Stiber; Eric Larson. *Signal Computing: Digital Signals in the Software Domain*. 2020. CC BY-SA. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/signal-computing-digital-signals-in-the-software-domain ## External links - Discrete Fourier transform, live p5.js sketch: https://editor.p5js.org/sciencenibber/full/ZPo-gIcTl - Discrete Fourier transform, fork the sketch in the p5.js editor: https://editor.p5js.org/sciencenibber/sketches/ZPo-gIcTl <!-- Hubs: Signal_processing. Portals: PORTAL_Signal_Processing. Signal Processing portal wave 1 · 2026-09-17 · drafted. -->