La transformée de Fourier rapide
Introduit| English | Sens |
|---|---|
| FFT | transformée de Fourier rapide (TFR) |
| twiddle factor | twiddle factor |
| butterfly | butterfly |
| 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?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
$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?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
$\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?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
$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.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
$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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
It is the same sum, reorganised. Apart from rounding, the outputs are identical.
You must transform exactly 1000 samples. What can you do?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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$.