The FFT from Scratch — Why Convolution Turns into Multiplication

A from-zero walk through the Fourier transform: a smoothie metaphor, the spinning-needle intuition, the DFT formula, and the divide-and-conquer trick behind the FFT — ending with the polynomial-multiplication view that makes the convolution theorem feel obvious.

An Algorithm for the Machine Calculation of Complex Fourier Series (Cooley & Tukey

Your Ear Already Does This

Play a C-major chord on a piano — three keys at once — and the air carries a single wave. A microphone records exactly that: one long column of numbers, "air pressure at each instant," with all three notes dissolved into it. And yet your ear pulls the three notes back apart without effort.

The Fourier transform is that trick, written down as mathematics: it unmixes a tangled wave into "how much of each pitch is inside." The FFT (Fast Fourier Transform) is the algorithm that makes the computation dramatically cheaper. It spread through the world via Cooley and Tukey's 1965 paper (the core idea appears in Gauss's notebooks from the early 1800s), and it routinely tops lists of the most important algorithms of the 20th century. It is the beating heart of signal processing.

The Metaphor: Guessing a Smoothie's Recipe

There are two "languages" for describing a signal.

• Time domain: the finished smoothie — a list of "the value at each instant." This is what microphones and sensors hand you directly
• Frequency domain: the recipe — a table of "which pitch, how strong, and with what timing offset"

The Fourier transform is a machine that takes one sip of the smoothie and recites the complete recipe. The inverse transform rebuilds the smoothie from the recipe. Nothing is lost in either direction — they are the same information written in two languages.

Why bother translating? Because different operations are easy in different languages. "Keep the low notes, remove the hiss" is hopeless to express directly on a waveform, but on the recipe side it's just "delete the high-frequency rows." The same is true of convolution, the subject of this article's subtitle: heavy labor in the time domain, a plain multiplication in the frequency domain.

The Intuition: Winding a Signal Around a Spinning Needle

So how do you measure "how much of frequency $f$ is inside"? This is the most beautiful part of the whole subject.

Picture a clock hand whose speed you control. To probe frequency $f$, wind the signal around a needle that spins $f$ times per second, plotting it on a disc — at each instant, place a weight at the needle's tip, heavy when the signal is large, light when it is small.

• If the signal really contains an $f$ Hz component, the weights pile up on one side of the disc, and the disc's center of mass drifts away from the middle
• If it doesn't, the weights scatter evenly and the center of mass stays put

The distance of that drift is the strength of the component; its direction is the timing offset (the phase). To describe rotation with a single number we use the complex exponential $e^{i\theta}$ ($= \cos\theta + i\sin\theta$, the point on the unit circle at angle $\theta$). Complex numbers show up not to make things harder, but because they let "rotate" be written as one multiplication.

The Machinery: the Discrete Fourier Transform (DFT)

Computers don't hold continuous waves; they hold $N$ samples $x_0, x_1, \dots, x_{N-1}$ measured at regular intervals. The tool that unmixes them is the discrete Fourier transform (DFT), and its entire definition is one line:

Put in words: "wind the signal around a needle that makes exactly $k$ full turns across the $N$ samples, and compute the center of mass (times $N$)." Here $x_n$ is the signal value at time step $n$, $e^{-2\pi i\,kn/N}$ is the direction the needle points at step $n$, and the sum is the act of loading all the weights and finding the balance point. Sweep $k$ from $0$ to $N-1$ and you get every component, from the slowest wave to the fastest.

Each $X_k$ is a complex number: its magnitude is the component's strength, its angle is the phase. The spectrum display in any audio app is simply $|X_k|$ plotted across $k$.

Computed Naively, That's N² Operations

Take equation (1) literally and each $X_k$ costs $N$ multiply-adds, and there are $N$ values of $k$ — about $N^2$ operations total. One second of CD-quality audio is 44,100 samples, and $44100^2$ is roughly 1.9 billion operations. For one second of sound. That rules out real-time audio, video frames arriving dozens of times per second, and most of modern communications.

Just how different $N^2$ and $N \log N$ are is better felt than told:

Now for the main event: the trick that crushes $N^2$ down to $N \log N$, and the payoff promised in the title — why convolution becomes multiplication.