Fast Fourier transform

How a music player's bouncing bars tell bass from treble

Those bars show how loud each pitch is at that moment. To draw them, software must turn a stretch of sound samples into a list of frequencies. That conversion is called the discrete Fourier transform, or DFT.

Done directly, the DFT checks each of N frequencies by multiplying all N samples by a wave at that frequency and adding up the results. That is N × N multiplications: about a million for 1,024 samples.

The fast Fourier transform (FFT) gives exactly the same answer with about N × log₂N steps, roughly 10,000 for 1,024 samples. That is why the bars can keep up with the music.

Fast Fourier transform

Shazam names a song from a few seconds of sound

Shazam cuts the recording into short slices and runs an FFT on each one. This gives a spectrogram, a map of which frequencies are loud at each moment. It then matches the strongest peaks against its song database.

The same algorithm is at work in Wi-Fi and 4G and 5G phones. They send data on many closely spaced frequencies at once, and an FFT separates them again at the receiver.

Fast Fourier transform

Split the samples into two half-size lists, again and again

The FFT splits the samples into even-numbered and odd-numbered ones and transforms each half. Those half-size results repeat every N/2 frequencies, so each is used twice: added once and subtracted once, after a rotation by w.

This butterfly step turns one size-N problem into two of size N/2, plus about N cheap operations. Halving down to single samples takes log₂N levels of about N operations each, so the total is about N log₂N.

In the simplest version, N must be a power of two so the halving comes out even. Software usually pads the signal with zeros to reach one.