FFT & windowing

Chapter 01 left us holding 48,000 numbers per second, and chapter 02 told us which frequencies those numbers can faithfully contain. Neither answered the question a decoder actually asks: which frequencies is this signal made of, right now? That question has a famous answer. The Fourier transform takes a block of samples and re-describes it, losslessly and reversibly, as a sum of sine waves. Feed it a block of N samples and it hands back N/2 + 1 bins, one magnitude for each frequency from 0 Hz up to the Nyquist limit, each bin covering a slice of spectrum exactly sampleRate / windowSize hertz wide. The wiggling line becomes a skyline: a spike wherever the signal has energy, silence between.

The FFT, the fast Fourier transform, is not a different transform, just the trick that makes it affordable: instead of comparing the block against every sine wave separately (N² multiplications), it splits the problem in half, then in half again, log₂(N) times. The engine that computes every spectrum in this pipeline lives in packages/dsp/src/fft.ts, and its header says why it looks the way it does: a radix-2 Cooley–Tukey FFT, “hand-rolled on purpose: this implementation is meant to be read.” It is about sixty lines — a bit-reversal shuffle, then log₂(N) passes of little two-point “butterfly” merges with precomputed twiddle factors — and every figure in this chapter runs it for real. No library, no black box; you can open the file and watch the whole trick.

Now the catch, and it is the catch: the central tradeoff of this entire field. The bin width is sampleRate / windowSize, so the only way to get finer frequency detail is to analyze a longer block of time. At 48 kHz, a 2048-sample window is 42.7 ms of signal and yields 23.4 Hz bins. Grow it to 8192 samples and the bins sharpen to 5.9 Hz, but now each spectrum describes 171 ms of the past, and anything that happened inside that window is smeared into one answer. Shrink it to 512 samples and the analysis reacts in 10.7 ms, but the bins fatten to 93.8 Hz and neighboring tones melt together. You can resolve close-together frequencies, or you can notice events quickly. Never both. This is not a flaw in the code; it is an uncertainty principle, and no cleverness removes it — you only get to choose where it hurts.

The figure opens at the setting where this project lives: two equal tones 73 Hz apart (the true spacing of the telephone keypad’s low group) under a 2048-sample window. Two clean spikes, a valley between, and the guides landing on top of each. Now drop the window size to 1024 and watch the spikes fuse into one fat peak: Δ is only 1.6 bins, and no downstream logic can recover what the transform already blurred. Widen Δ with the slider and the pair separates again even at small windows. Press play — the sound never changes when you change the window. Only the measurement does, which is exactly the point.

The seam, and why we taper it

The second control, the window function, exists because of a quiet assumption buried in the math. The Fourier transform doesn’t know your 2048 samples are a snippet; it treats them as one period of a signal that repeats forever, end spliced to beginning, for all time. A raw slice almost never cooperates: the wave exits the right edge mid-swing and re-enters the left edge somewhere else entirely. To the transform that splice is real — a sudden jump, and a jump is a click, and a click contains energy at every frequency. So a pure tone that should occupy one bin grows skirts that drape across the whole spectrum. The effect is called spectral leakage, and the fix is almost embarrassingly physical: before transforming, multiply the block by a curve that tapers smoothly to zero at both edges. Zero splices to zero. The seam is gone.

The tapering curve is the window function, and the engine ships four (packages/dsp/src/window.ts, another file meant to be read). Rectangular is no window at all: the narrowest possible spike but the worst skirts. Flip the figure to it and watch the leakage rise. Hann, the pipeline’s default, is one smooth cosine arch from zero to zero. Hamming is Hann adjusted to hover just above zero at the edges, tuned to cancel the nearest sidelobe. Blackman adds a second cosine term and buys the lowest skirts of the four. What you are trading is always the same pair of goods: how far down the skirts sit versus how wide the central spike swells. Taper harder and leakage falls, but each spike fattens — the same resolution currency the window size spends, collected by a different tollbooth.

The algorithm is older than its name. Cooley and Tukey published in 1965, when the cold war wanted to distinguish Soviet nuclear tests from earthquakes in seismometer data. Only later did historians find the same recursion in Gauss’s unpublished notebooks from 1805, invented to interpolate asteroid orbits. The FFT was discovered twice, both times to listen to the ground and the sky.

The tradeoff stops being abstract the moment a real signal shows up. DTMF’s low group sits at 697, 770, 852, and 941 Hz, neighbors just 73 Hz apart. At 48 kHz, separating them cleanly needs bins meaningfully narrower than that spacing: a 2048-sample FFT (23.4 Hz bins) is the floor, and 4096 (11.7 Hz) is comfortable. That is a 43–85 ms analysis window against key presses the standard allows to be as short as 40 ms — the recognizer in chapter 07 lives its whole life inside that squeeze. It is exactly why the engine’s default window is 2048 samples: the smallest power of two that keeps a telephone keypad legible.

A spectrum, though, is still just N/2 + 1 numbers: nothing in it says “here are the two tones.” Picking the spikes out of the skyline, and pinning them down finer than one bin, is chapter 05. Before that, chapter 04 uses the spectrum to answer an older question — why a piano and a trumpet playing the same note look nothing alike up here. And much later, chapter 09 asks the heretical one: if you already know the eight frequencies you care about, why measure a thousand?