快速傅里叶变换
引入| English | 释义 | 拼音 |
|---|---|---|
| FFT | 快速傅里叶变换 | kuài sù fù lǐ yè biàn huàn |
| twiddle factor | 旋转因子 | xuán zhuǎn yīn zi |
| butterfly | 蝶形运算 | dié xíng yùn suàn |
| bit-reversed | 位反转 | wèi fǎn zhuǎn |
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?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$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?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$\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?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
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?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$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.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$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.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
It is the same sum, reorganised. Apart from rounding, the outputs are identical.
You must transform exactly 1000 samples. What can you do?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
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$.