Chapter 7The DFT & FFT

Everything so far has been building intuition. This is the actual algorithm: given nothing but a list of sampled numbers, compute exactly which frequencies are in the signal — no peeking at how it was built.

Design a signal (same as Chapter 5)

Drag to set each frequency's amplitude

Spectrum computed from the samples alone (the DFT output)

Signal / samples |X_k| recovered by the DFT

The formula

The Discrete Fourier Transform takes $N$ samples $x_0, x_1, \dots, x_{N-1}$ and produces $N$ complex numbers describing the signal's frequency content:

Discrete Fourier Transform

$$ X_k = \sum_{n=0}^{N-1} x_n \, e^{-i 2\pi k n / N} \qquad k = 0, 1, \dots, N-1 $$

Each $X_k$ answers one question: "how much of frequency $k$ (in cycles per sample-window) is present?" $|X_k|$ — the magnitude of that complex number — is exactly the bar height you see plotted above. This is the same $e^{-i\theta}$ rotation from Chapter 4's circles, just run once per frequency you want to test for, instead of drawn out over time.

Notice the spectrum above lights up only at the frequencies you actually dialed in with the sliders — everything else reads essentially zero. The DFT recovered your recipe of frequencies from nothing but the raw sample values.

Why the FFT exists

Computed directly, the formula above costs $O(N^2)$ multiplications — for every one of the $N$ output frequencies, you sum over all $N$ input samples. The Fast Fourier Transform (FFT) is not a different formula; it's the same DFT computed cleverly, by recursively splitting the sum into even- and odd-indexed samples and reusing work between them. That drops the cost to $O(N \log N)$:

N (samples)	DFT: N² ops	FFT: N·log₂N ops	Speedup

At small $N$ the difference barely matters. At the sizes real audio, image, and radio-signal processing use — millions of samples — the FFT is the only reason any of this runs in real time at all.

The full loop, in one sentence: a signal is sampled (Ch. 6) respecting the Nyquist limit, the FFT turns those samples into a spectrum (this chapter) using the same rotating-phasor idea as the epicycles (Ch. 4), that spectrum is edited or analyzed in the frequency domain (Ch. 5), and an inverse transform — the same formula run backwards — rebuilds a time-domain signal as a sum of sine waves (Ch. 3). That round trip is the Fourier transform.