The FFT
Introduced| English | Meaning |
|---|---|
| FFT | A family of fast algorithms for computing the discrete Fourier transform, commonly with work proportional to N log N. |
| twiddle factor | A complex exponential weighting factor, typically a root of unity, used in DFT and FFT computations. |
| butterfly | A small repeated computation combining transform branches using additions, subtractions and weighting factors in an FFT. |
| bit-reversed | bit-reversed |
A million multiplies
- A direct 1024-point DFT needs about a million complex multiplies. For real-time audio or radar that is far too slow.
- The FFT 快速傅里叶变换 computes the same answer about a hundred times faster. It made digital signal processing practical.
The cost of the direct DFT
- Each of the $N$ outputs sums $N$ products, so the direct DFT costs $N^{2}$ operations.
- Doubling $N$ makes it four times slower.
How many operations does a direct 256-point DFT take?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$256^{2} = 65\,536$.
Split, and split again
- Split the input into even and odd samples. Each half is an $N/2$-point DFT, and the halves combine with the twiddle factor 旋转因子 $W_{N}^{k} = e^{-j2\pi k/N}$.
- Repeat the split $\log_{2}N$ times, down to 2-point transforms.
How many butterfly stages does a 512-point FFT have?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$\log_{2}512 = 9$ stages, each of 256 butterflies.
Butterflies
- The combining unit is the butterfly 蝶形运算: one multiply and two adds. There are $\log_{2}N$ stages of $N/2$ butterflies.
- The repeated even/odd split puts the inputs in bit-reversed 位反转 order: index 1 (001) of 8 goes to position 4 (100).
In an 8-point decimation-in-time FFT, input index 3 (011) goes to which position?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Reverse the bits 011 to 110, which is 6.
Worked example: the count
- $N = 1024$: direct $1024^{2} = 1\,048\,576$; FFT $N\log_{2}N = 10\,240$. That is 102 times fewer.
- $N = 4096$: 341 times fewer. The gap keeps growing with $N$.
How many times fewer operations does the FFT need than the direct DFT at N = 256?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$N^{2}/(N\log_{2}N) = N/\log_{2}N = 256/8 = 32$.
Worked example: a spectrum analyser
- 1 Hz bins at $f_{s} = 1$ kHz need $N \ge 1000$; take $N = 1024$ for $\Delta f = 0.977$ Hz. Bin 100 is $100 \times 0.977 = 97.66$ Hz.
- At 10 ns per operation the transform takes about 100 µs, against a 1.024 s record: easily real time.
A 2048-point FFT runs at f_s = 48 kHz. How wide is each bin, in Hz? Give 1 decimal place.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$48\,000/2048 = 23.4$ Hz.
Three common slips
- "N must be a power of 2." Other FFT algorithms handle any $N$; powers of 2 are just fastest.
- "The FFT changes the answer." It computes exactly the DFT, only faster.
- Bins as hertz. Bin $k$ is still $k f_{s}/N$.
An FFT gives a slightly different, approximate answer compared with the direct DFT.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
It is the same sum, reorganised. Apart from rounding, the outputs are identical.
You must transform exactly 1000 samples. What can you do?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
1000 = 2³ × 5³, which a mixed-radix FFT handles. Padding to 1024 also works, at a slightly different bin spacing.
Recap
- Direct DFT: $N^{2}$. FFT: $N\log_{2}N$.
- Even/odd split, twiddle factors, $\log_{2}N$ stages of butterflies.
- Same answer, 102 times faster at $N = 1024$.