Mathematics
Fast Fourier Transform (FFT)
Quick fact
A 1-second audio clip with 44,100 samples would need about 1.9 billion complex multiplications for a direct DFT, while the FFT reduces this to roughly 700,000 operations—thousands of times faster, and enough to make real-time analysis possible.
Why this is interesting
You've seen an audio equalizer's bars dancing to music—but how does a computer instantly separate a messy sound wave into distinct frequencies? The answer is the Fast Fourier Transform (FFT).
Read the full explanation
Understanding Fast Fourier Transform (FFT)
Think of a signal as a musical chord. The chord is a single sound wave, but your brain can sense that it contains multiple notes. Mathematically, any digital signal can be built from a set of sine and cosine waves of different frequencies, each with its own amplitude and phase. The DFT calculates how much of each frequency exists in the signal. The direct way to do this is like checking every possible frequency against every sample: if you have N samples and N frequency candidates, you need N × N operations. For even a short sound clip, that's billions of calculations—too slow for live use. The FFT takes a smarter route. It rearranges the problem by splitting the signal into even-indexed and odd-indexed samples, computing smaller transforms, then combining them using clever symmetries. This divide-and-conquer strategy eliminates repeated work, cutting the number of operations down to N × log₂N. Instead of 44,100 times itself, you do 44,100 times about 15.
A deeper explanation
The FFT is not a new transform; it is a fast way to compute the same DFT. The DFT formula is Xk = Σ xn · e^{-2πi·nk/N}. Direct evaluation requires N² complex multiplications. The FFT exploits two properties of the complex exponentials (twiddle factors): their periodicity and their symmetry. The most famous version, the Cooley–Tukey algorithm, works by recursively splitting the N-point DFT into two N/2-point DFTs—one on even-indexed inputs, one on odd-indexed inputs. Each split reduces the problem size, and the results are combined with a 'butterfly' operation (adding and subtracting values multiplied by twiddle factors). Because the pattern repeats at every level, the same arithmetic is reused many times. The total number of operations becomes roughly N log₂N, a dramatic reduction that turns frequency analysis from a theoretical tool into a practical one. This is why FFT powers everything from MP3 compression and medical MRI reconstruction to radar systems and Wi-Fi signal processing.