Discrete Fourier transform and FFT

The formula

The discrete Fourier transform of an N-point record:

X[k] = Σₙ x[n] · e^(−j·2π·k·n/N),    n = 0 … N−1,  k = 0 … N−1

Reading: correlate the record against a complex sinusoid that completes exactly k cycles in the record; the result is the amplitude and phase of that frequency component.

The inverse, which rebuilds the record exactly:

x[n] = (1/N) · Σₖ X[k] · e^(+j·2π·k·n/N)

Reading: the N samples are perfectly reconstructed as a sum of N spinning phasors — the DFT loses nothing.

What frequency each bin means, for sample rate fs:

f_k = k · fs / N        Δf = fs / N = 1 / T

Reading: bin spacing is set by one thing only — the length of the record in seconds. Ten seconds of data buys you 0.1 Hz bins, no matter the sample rate.

The DTFT, the continuous-frequency parent:

X(e^(jω)) = Σₙ x[n] · e^(−j·ω·n)     (n over all integers, ω continuous)

Reading: the DFT is just the DTFT of your finite, windowed record sampled at N evenly spaced frequencies — every leakage headache traces back to that word "windowed."

The cost, and the reason the FFT matters:

direct DFT:   N² complex multiplies
radix-2 FFT:  (N/2) · log₂N

Reading: at N = 1024 that is 1,048,576 multiplies versus 5,120 — a factor of about 205, and the gap widens as N grows.

Where you meet it

Behind every spectrum analyzer button you press. A modern signal analyzer digitizes, windows, and FFTs. The "RBW" knob is really choosing a window and a record length; the noise floor you read moves with both. When the analyzer says the spur is at −72 dBc, an FFT said it first.
On the vibration test stand. Random vibe control to a MIL-STD-810 profile is a closed loop around the FFT: the controller measures the accelerometer PSD by averaging windowed FFTs, compares it to the reference spectrum, and reshapes the drive every few hundred milliseconds. The g²/Hz on the test report is FFT output divided by the equivalent noise bandwidth of the window.
In telemetry and RF processing. OFDM waveforms are literally an inverse FFT at the transmitter and an FFT at the receiver; channelizers, digital downconverters, and pulse-Doppler radar range-Doppler maps are FFTs in the data path, not post-processing.
At the data review board. Two bearing tones 3 Hz apart in a 0.4-second record cannot be separated, because Δf = 1/0.4 s = 2.5 Hz and the window mainlobe is wider than one bin. The reviewer who asks "how long was the record?" before "what's the resolution?" has been through this before.

How it works

The DFT treats your N-sample record as one period of a signal that repeats forever. That single assumption explains most of what goes right and wrong. If a tone completes a whole number of cycles in the record, the periodic extension is seamless and all its energy lands in one bin. If it doesn't, the extension has a jump at the seam, and that jump smears energy across the whole spectrum. That smear is spectral leakage.

The numbers, checked numerically:

A tone landing exactly halfway between bins, unwindowed, reads 3.92 dB low at the peak (the value is 20·log10(2/π)), and only about 81 % of its energy stays in the nearest two bins — the rest leaks everywhere, riding sidelobes that start at −13.3 dB.
A Hann window trades resolution for containment: first sidelobe drops to −31.5 dB, worst-case amplitude error shrinks to 1.42 dB, the noise bandwidth becomes 1.5 bins, and the window throws away half your signal (coherent gain 0.5 — which is why analyzers multiply by 2 behind your back).

Behavior worth having in your head:

Record length buys resolution; sample rate buys bandwidth. They are independent purchases. fs sets the highest frequency you can see (fs/2, Nyquist); T sets how finely you can see it.
Zero-padding interpolates, it does not resolve. Padding a 1,024-point record to 8,192 draws a smoother curve through the same DTFT — the mainlobe width, set by the original T, does not change. Two tones unresolved before padding are unresolved after.
Averaging trades time for a steady floor. A single FFT of random data has a standard deviation as large as its mean. Welch averaging of 50 windowed segments steadies the PSD estimate to roughly ±14 % — that is why vibe controllers quote "degrees of freedom."
For real inputs, half the output is redundant. X[N−k] is the complex conjugate of X[k], so a real 1,024-point record yields 513 independent bins. Single-sided displays fold and double the interior bins — and mixing up the 1/N, 2/N, and √(1/N) scaling conventions between tools is the most common way two labs report different amplitudes for the same tone.
Multiplying two FFTs convolves circularly. The fast-convolution trick wraps the tail of the result onto its head unless you zero-pad both sequences to at least N + M − 1 first.

The mistakes people actually make:

Reading leakage as sidebands. A strong tone that isn't bin-centered, taken with no window, dresses itself in skirts that look like modulation. Window it, or re-run with a record length that makes the tone coherent, before telling the program there's a stability problem.
Trusting FFT amplitude without knowing the window. Peak amplitude of a windowed tone depends on where it falls in the bin (up to 1.4 dB off even with Hann) and on the window's coherent gain. For broadband levels, divide by the window's noise bandwidth; for tones, use the coherent gain; never both at once.
Assuming more points means more resolution. More points at the same sample rate means a longer record — that helps. More points by zero-padding or by raising fs over the same duration does not.
Forgetting the anti-alias filter. The FFT will cheerfully report a 9 kHz alias of a 15 kHz tone sampled at 24 kHz. Nothing in the math flags it; only the analog filter in front of the ADC can.

History

The FFT was discovered before the Fourier transform had a name. Around 1805, Carl Friedrich Gauss — interpolating asteroid orbit measurements of Pallas and Juno — worked out a way to compute trigonometric series coefficients by splitting the problem into smaller pieces, essentially the same divide-and-conquer scheme rediscovered 160 years later. He never published it; the treatise appeared posthumously in his collected works in 1866. The 1805 derivation predates even Fourier's 1807 memoir — Gauss had a fast Fourier algorithm two years before Fourier analysis existed to speed up ^[1]^[2]^[3]. Gauss never analyzed the operation count, so nobody noticed what he had.

Pieces resurfaced for over a century. In 1942, Danielson and Lanczos published the doubling trick — an N-point transform from two N/2-point transforms — for X-ray scattering work, again without the N·log N punchline ^[1]^[3].

The modern story starts in 1963, in a meeting of the President's Science Advisory Committee about detecting Soviet underground nuclear tests with seismometer arrays in surrounding countries. John Tukey of Princeton sketched a fast way to compute the Fourier transforms the analysis needed. Richard Garwin of IBM saw the sketch, understood what it was worth, and got IBM to pair Tukey with James Cooley at the Watson Research Center ^[2]^[4]^[5]. Cooley later wrote that Garwin, keeping the real application quiet, told him the transform was needed to study spin orientations in crystals of helium-3 ^[2]^[7]. The algorithm ran at Watson in 1964 and the five-page paper — "An algorithm for the machine calculation of complex Fourier series" — appeared in Mathematics of Computation in 1965 ^[4]^[5]^[6]. Because Tukey wasn't an IBM employee, the algorithm was not patented, and it spread through the signal-processing world essentially overnight ^[1]^[2]. IEEE designated the 1964 demonstration an Engineering Milestone in 2025 ^[4]^[8]. A calculation Gauss did by hand for two asteroids now runs a few billion times a day in phones, radars, and every shaker controller on Redstone.

Related tools

/tools/adc-resolution — the quantization floor underneath every FFT noise measurement
/tools/frequency-period — bin frequency, record length, and resolution are all this conversion
/tools/rc-filter — the anti-alias filter the FFT depends on and cannot check for itself
/tools/db-voltage-ratio — sidelobe levels, scalloping loss, and dBc spur readings
/tools/thermal-noise-floor — what the averaged FFT floor should converge to on a quiet front end
/tools/q-factor-bandwidth — resonance widths you need enough bins to resolve

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →