Discrete Fourier Transform

Sixty-four samples of a tone, and their discrete Fourier transform. Move the tone off a whole number of cycles and one clean bar turns into a smear across the spectrum. Pick a bin to see it built from 64 arrows laid head to tail, and switch on a window to see what it buys and what it costs.

Worked example — Discrete Fourier Transform

Tone 1, played at 8,000 samples a second	1,250.0 Hz
Tallest bar (bin 10), share of the tone	100.00%
Tallest bar in decibels	0.00 dB
Energy in the bin(s) nearest tone 1	100.00%
Bin 10: the arrows' sum, as an amplitude	100.00%
Bin 10, below the tallest bar	0.0 dB

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Discrete Fourier Transform

The discrete Fourier transform of N samples x₀ … x_N−1 is N numbers X_k = Σ_n x_n e^−2πikn/N, one per bin k, each measuring how much of a wave completing k cycles in the N samples the signal holds. It treats the samples as one period of a signal that repeats, so it is exact for tones that complete whole cycles and spreads every other tone across the bins: spectral leakage. A window w_n multiplies the samples first to soften the seam.

What each symbol means

A_k: the amplitude bin k implies, what the bars show: 2|X_k|/(N·G) for 0 < k < N/2, and |X_k|/(N·G) at k = 0 and k = N/2, which have no mirror bin to share with. A tone of amplitude 1 on a bin reads 1
G: the window's coherent gain, the mean of w_n: 1 with no window, ½ for Hann

Assumes: Each tone starts at its peak, as a cosine. The far-skirt figures move with the starting phase: bin 31 of the 10.5-cycle tone is 26.3 dB below the tallest bar for a cosine and 31.2 dB below for a sine, while the 81% in the two nearest bins hardly moves. The Hann window is the periodic form, ½ − ½cos(2πn/N), whose transform is exactly three bins.

Half a bin off, a pure tone spills into every bin 🖖

Press On a bin: 64 samples of a tone that completes exactly 10 cycles. All of its energy sits in bin 10 and every other bar is zero. Now press Halfway between. The tone is the same except that it completes 10.5 cycles, and the spectrum is now in decibels. Bins 10 and 11 hold 81.10% of the energy between them and the rest has gone everywhere: bin 31, more than twenty bins away, is only 26.3 dB below the tallest bar, about a twentieth of its height, and no bar anywhere is zero. Look at the seam in the top panel. The transform treats the 64 samples as one turn of a loop that repeats for ever, and 10.5 cycles do not join up, so the loop jumps at every seam. A jump cannot be built from a few frequencies; it takes all of them. Press Play the loop on each preset and you will hear it: a clean whistle on a bin, a rasp at 125 Hz, the rate the seam comes round, halfway between.

Move a tone half a bin and its tallest bar reads a third low 🖖

Press The arrows bend. Every bar is a sum of 64 arrows, one per sample: arrow n is w_nx_n turned clockwise by k·n/64 of a turn, so a negative sample points it the opposite way, and the bar is how far the chain ends from where it began. A cosine is two halves spinning opposite ways. When the tone completes exactly k cycles, one half of every arrow is turned back to face the same direction, the halves line up in a straight row 32 long, and the bar reads 100%. Half a bin off, that row bends through half a circle over the 64 samples, and the ends of a semicircle are only 2/π of its length apart, 63.7%: the 3.92 dB “scalloping loss” in Fredric Harris's 1978 table of windows. The other half of each arrow spins 21.5 times round and nearly cancels, which nudges the reading to the 64.61% the page prints. The tone is as loud as ever; the tallest bar under-reads it by a third, −3.79 dB, purely because of where its frequency falls. Move it a whole bin off and the row bends into a full circle and closes, and the fast half closes with it: that is why a tone on a bin leaves every other bar at exactly zero.

Fading the ends out uncovers a tone 316 times quieter 🖖

Press A quiet neighbour: a second tone 50 dB down, 316 times smaller in amplitude, completing exactly 20 cycles. Bin 20 reads 22.7 dB below the tallest bar, but that is the first tone's leakage, and bin 20 does not even stand above bin 19 beside it. Switch the window to Hann, which fades the samples in from zero and out again so the loop has no jump. The leakage collapses, bin 31 from 26.3 dB below the peak to 98.9 dB below, and bin 20 stands up as a peak of its own, reading 0.32% of tone 1's amplitude, which is what 50 dB down means. The window charges for it in width. A tone on a bin now covers three, so a tone exactly on bin 10 keeps only 66.67% of its energy in its own bin: press On a bin and the table under the results shows it beside the rectangular window's 100%. Press Two tones, Hann: two equal tones two bins apart, and bin 11 between them reads 100.00%, as tall as either. Without the window that bin is empty. Hann trades a peak three bins wide for clean skirts, which is the right trade when the thing you are looking for is faint and the wrong one when it sits close.

Problem solved in full

Correct a reading, then remove the need to 4 steps
An analyser samples 8,000 times a second and transforms 64 samples at a time, with no window. You feed it a 1,312.5 Hz test tone and the tallest bar reads 0.32. What is the tone's true amplitude, and how many samples per block would put the tone exactly on a bin? Press The arrows bend: the page plays a tone at that frequency.

Open this problem in the tool
1. Bins are 8,000/64 apart, so the tone completes 10.5 cycles per block: halfway between bins 10 and 11.
  
  $Δ f = \frac{8 , 000 Hz}{64} = 125 Hz, c = \frac{1 , 312 . 5 Hz}{125 Hz} = 10.5$
2. Halfway, the page's tallest bar reads 64.61% of the tone. Divide it out:
  
  $A = \frac{0 . 32}{0 . 6461} = 0.4953$
3. The tone lands on a bin when a block holds a whole number of its cycles. With 128 samples the bins are 62.5 Hz apart:
  
  $Δ f = \frac{8 , 000 Hz}{128} = 62.5 Hz, c = \frac{1 , 312 . 5 Hz}{62 . 5 Hz} = 21$
4. Had the analyser used a Hann window on the 64 samples, the tallest bar would have read 84.89% of the tone, so the same tone would show:
  
  $0.4953 \times 0.8489 = 0.4205$
Answer

About 0.495, and 128 samples a block. Any multiple of 128 also works, since 1,312.5 Hz needs 128 samples to complete a whole number of cycles (21). The page is fixed at 64, so the 128-sample case is past what it can show; at 128 the bar reads the full 0.495, and the window would no longer be needed to read the amplitude, only to keep a strong tone's skirt off a faint one.

$A \approx 0.495; N = 128$

Learning path

The Fourier transform in practice

References (2)

The standard reference on windows. Leakage defined as the page shows it: of all frequencies “only those which coincide with the basis will project onto a single basis vector; all other frequencies will exhibit non zero projections on the entire basis set”, because “the periodic extension of a signal not commensurate with its natural period exhibits discontinuities at the boundaries of the observation” (p. 52). Table I (p. 55) gives coherent gain 1.00 and 0.50 and scalloping loss 3.92 dB and 1.42 dB for the rectangle and Hann windows: F. J. Harris, “On the use of windows for harmonic analysis with the discrete Fourier transform”, Proceedings of the IEEE, vol. 66, no. 1, pp. 51–83 (1978).
The DFT's definition, and what happens to a frequency that is not a bin: the sum “is N if ωₖ = ωₓ and zero at ωₗ, for l ≠ k. However, the sum is nonzero at all other frequencies”: J. O. Smith III, Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications, 2nd ed., W3K Publishing (2007), “DFT Definition” and “Frequencies in the ‘Cracks’”.

By the 42Math team · Reviewed against published sources. Corrections welcome.