Learning the Fourier transform

Two small interactive pieces I built while working through how the Fourier transform works: a mixer that lets you build a signal out of sine waves and watch the transform pull them back apart, and a diagram of the trick that makes the Fast Fourier Transform fast.

Any signal is a stack of sine waves

The core idea: a repeating signal can be written as a sum of sine waves at different frequencies, each with its own strength. The Fourier transform goes the other way. You give it the signal, and it tells you how much of each frequency is in there.

Try it below. Each slider sets how strong one sine wave is, from 1 cycle across the window up to 8. The top plot is what you get when you add them all together. The bars underneath come from running a real discrete Fourier transform on that combined signal, and they land exactly on the amounts you set.

Signal over time Fourier transform: amount of each frequency

How the transform finds each frequency

The discrete Fourier transform (DFT) takes N samples x₀ … x₍N−1₎ and, for each frequency k, measures how well the signal lines up with a wave that completes k cycles across the window:

X_k = Σ x_n · e^(−2πi·k·n/N) for n = 0 … N−1

The complex exponential packs a cosine and a sine together, so each X_k is a correlation: multiply the signal by a test wave point by point and add it all up. Sine waves at different whole-number frequencies cancel out over a full window, so only the matching frequency survives. For a pure sine of strength a at frequency k, |X_k| comes out to a·N/2, which is why the mixer draws each bar at 2·|X_k| / N and gets your slider value back.

Why the FFT is fast

Computed directly, every one of the N outputs needs a sum over all N inputs, which is N² work. The Fast Fourier Transform (in its classic Cooley–Tukey form) notices that the even-numbered and odd-numbered samples each form a half-size DFT of their own. Transform each half, then combine them:

Input x0 … x7 Evens: x0 x2 x4 x6 Size-4 DFT → E_k (recurse) Odds: x1 x3 x5 x7 Size-4 DFT → O_k (recurse) Combine with butterflies (O(N) work) X_k = E_k + ωᵏO_k X_k+4 = E_k − ωᵏO_k Output X0 … X7
One level of the FFT for N = 8. The two halves are themselves split the same way, all the way down.

The combining step is the "butterfly". With ω = e^(−2πi/N), each pair of half-size results produces two outputs:

X_k = E_k + ωᵏ · O_k X_(k+N/2) = E_k − ωᵏ · O_k

One multiplication by ωᵏ is shared by both outputs, so each level of combining costs O(N). Halving repeatedly gives log₂ N levels, so the whole transform is O(N log N). For 1,024 samples that's about 10,000 steps instead of about a million, a hundredfold speedup that grows with N.

← More posts