The DFT
seeing a spectrum
Every flower, every spectrum bar you've watched so far was secretly built by one machine you never saw. This is that machine — the Discrete Fourier Transform — and by the end you'll have built it yourself, and it will feel obvious.
From a wall of numbers, hear the chords.
In How Synths Make Sound you went one way: a recipe → a wave. You chose harmonic amplitudes and additive synthesis summed them into sound. That direction is easy — you're just adding sines.
Now the hard, magical direction. A microphone hands a computer a long list of numbers — air pressure, sampled tens of thousands of times a second. No labels, no notes, just x[0], x[1], x[2], …. Buried in that wall of numbers are the pitches, the harmonics, the chords. How do you get them back out?
That reverse trip — wave → recipe — is the Discrete Fourier Transform. It is the single most used algorithm in all of audio, and the engine behind every spectrum and bloom you've already played with. Let's build it from one honest question.
The one idea behind the DFT (correlation), why it needs complex numbers, the formula derived term by term, a complete 4-point transform worked by hand, the code in JavaScript and Python, and a capstone where the math recovers the very chord you play it.
The whole idea, in one gesture.
Here is the entire secret of the Fourier transform, and you can feel it with your hand. To ask "is frequency f hiding in this signal?", do one thing: multiply the signal by a test sine of frequency f, and add up the result.
Why does that work? If the signal really wobbles at f, then it and the test sine rise and fall together — their product is mostly positive, and the sum grows large. If f is not present, the product is as often negative as positive, and the sum cancels to nearly zero. Summation is a lie detector for frequencies.
Build a signal from the hidden tones below, then drag the probe across the spectrum. Watch the middle row — the product — and its running sum Σ. It stays near zero everywhere… until you land exactly on a frequency that's really there, and it snaps tall.
The amount of frequency k in a signal is the sum of the signal times a test wave of frequency k. Do that for every k and you have the whole spectrum. Everything else is bookkeeping.
One test wave isn't enough.
There's a hole in our lie detector. What if the signal's wobble is a cosine — shifted a quarter-cycle from our test sine? Then where the sine is biggest, the signal is zero; the product cancels and our sum reads zero even though the frequency is present. We got fooled by phase.
The fix: test with both a sine and a cosine. Whatever the phase, the energy shows up in one, the other, or split between them. And the clean way to carry a sine and a cosine together is a single complex exponential — which, as you saw with the circle that sings, is just a point going around a circle:
So our test wave for bin k over N samples is e−i·2πkn/N — a point circling k times as n walks the N samples. Multiply, sum, and you get a complex number X[k]. Its two pieces answer two questions at once:
The magnitude is what every spectrum bar and bloom petal has been showing you. Put the test wave and the sum together and you have the definition itself:
x[n] — your signal, N samples of it.k — the bin (the frequency we're testing). It runs 0 … N−1.e−i·2πkn/N — the test wave, circling k times across the window.Σ — add it all up: the correlation, exactly the spike you dragged out in Chapter 1.A 4-point DFT you can check on paper.
Formulas hide until you grind one out. Take the smallest interesting case: N = 4 samples of a pure sine, one cycle over the window — x = [0, 1, 0, −1]. With N=4, the test wave's step is e−i·2π/4 = e−iπ/2 = −i, so e−i·2πkn/4 = (−i)kn. Only x[1]=1 and x[3]=−1 are nonzero, so every bin is just X[k] = (−i)k − (−i)3k:
|X[1]| = 2. There's our frequency.|X[3]| = 2.The magnitudes are [0, 2, 0, 2]. Two facts fall straight out, and both are general:
1. A pure sine is purely imaginary (−2i) — because a sine is the imaginary part of the exponential. A pure cosine would have come out purely real. The complex number remembers the phase. 2. The spectrum mirrors: X[3] = X[1]* (its conjugate). For real signals the top half of the bins is always the mirror image of the bottom — bin k and bin N−k are the "same" frequency. That's why we only ever draw the first half.
Last piece: which real frequency is bin k? It's spaced by the sample rate over the window length:
At CD rate fs = 44100 with N = 1024, each bin is 44100/1024 ≈ 43 Hz wide. Want to tell 440 Hz from 443 Hz? You need a longer window. Hold that thought — it's the whole tension of the next module.
The DFT is two loops.
The definition translates to code with zero cleverness: for every bin k, walk every sample n, accumulate the real and imaginary parts. This is the whole transform — the thing that drew every flower in this course:
function dft(x) { const N = x.length, X = []; for (let k = 0; k < N; k++) { let re = 0, im = 0; for (let n = 0; n < N; n++) { const a = -2 * Math.PI * k * n / N; // the circling test wave re += x[n] * Math.cos(a); im += x[n] * Math.sin(a); } X.push({ re, im, mag: Math.hypot(re, im) }); // magnitude = how much of bin k } return X; }
import numpy as np def dft(x): N = len(x); n = np.arange(N) return np.array([np.sum(x * np.exp(-2j * np.pi * k * n / N)) for k in range(N)]) # identical output, but O(N log N) instead of O(N²): X = np.fft.rfft(x) # the Fast Fourier Transform mags = np.abs(X) # the spectrum you keep seeing
Our honest two loops are O(N²) — for a 4096-sample window that's ~17 million multiplies, per frame. The Fast Fourier Transform exploits the symmetry you saw in the worked example (bins reuse each other's roots of unity) to get the same answer in O(N log N) — about 50,000 multiplies. Same transform, just not wasteful. It's what AnalyserNode and np.fft run under the hood.
Run the sum the other way (flip the sign in the exponent, divide by N) and you get the inverse DFT — spectrum back to wave. That's exactly the additive synthesis you did in the synth lesson. DFT and additive synthesis are the same machine pointed in opposite directions.
Play a chord. Watch the math name it.
Time to point everything at once. Press a chord below: several oscillators sound together, their pressure waves add into one tangled signal — and the live DFT pulls them apart, lighting a peak at each note and labelling it. You hear music; the transform recovers the mathematics; the spectrum is the art. The whole course, in one button.
One catch: this reads the spectrum of one instant. A real song's notes start and stop — to see when each frequency happens you slice the sound into short windows and DFT each one. That's the Short-Time Fourier Transform, and its picture is the spectrogram — the next lesson in the Signal track, and the view a Lyria-class model's output will one day paint across the cinematic canvas.
You didn't learn the Fourier transform. You built it — and it was only ever asking, over and over: does this frequency fit?
Serra et al., Audio Signal Processing for Music Applications — Module 2, DFT (Stanford / UPF). · The Scientist & Engineer's Guide to DSP, Smith — the DFT from the ground up. · MDN, AnalyserNode — the FFT behind the panels.