第 2 章 FFT 算法 / FFT Algorithm

2.1 为什么需要 FFT

DFT 直接计算复杂度为 $O(N^2)$。FFT 降至 $O(N\log_2 N)$：

1965 年 Cooley-Tukey 发表 FFT，彻底改变了 DSP。没有 FFT，就没有现代 OFDM、MP3/AAC、雷达信号处理和 SDR。

2.2 基2 DIT (Decimation-In-Time) FFT

2.2.1 分治思想

将 $x[n]$ 按偶/奇下标分解为 $e[r] = x[2r]$ 和 $o[r] = x[2r+1]$：

$$X[k] = \underbrace{\sum_{r=0}^{N/2-1} e[r] \cdot W_{N/2}^{rk}}{E[k]} + W_N^k \cdot \underbrace{\sum{r=0}^{N/2-1} o[r] \cdot W_{N/2}^{rk}}_{O[k]}$$

利用 $W_N^{k+N/2} = -W_N^k$，得蝶形运算：

$$X[k] = E[k] + W_N^k \cdot O[k]$$ $$X[k + N/2] = E[k] - W_N^k \cdot O[k]$$

2.2.2 蝶形运算

flowchart LR
    A["E[k]"] --> C(("⊕"))
    B["W_N^k · O[k]"] --> C
    C --> D["X[k] = E[k] + W_N^k·O[k]"]
    A --> E(("⊖"))
    B --> E
    E --> F["X[k+N/2] = E[k] − W_N^k·O[k]"]
    style A fill:#1565C0,color:#fff
    style B fill:#1565C0,color:#fff
    style C fill:#228B22,color:#fff
    style D fill:#C62828,color:#fff
    style E fill:#228B22,color:#fff
    style F fill:#C62828,color:#fff

总计 $N/2 \cdot \log_2 N$ 次复数乘法。

2.2.3 伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

function FFT_DIT(x):
    N = length(x)
    if N == 1: return x
    x = bit_reverse_reorder(x)
    for stage = 1 to log2(N):
        m = 2^stage
        wm = exp(-j * 2π / m)
        for k = 0 to N-1 step m:
            w = 1
            for j = 0 to m/2 - 1:
                t = w * x[k + j + m/2]
                u = x[k + j]
                x[k + j]       = u + t
                x[k + j + m/2] = u - t
                w = w * wm
    return x

2.3 基2 DIF (Decimation-In-Frequency) FFT

DIF 先做蝶形后分解输出：

$$X[2r] = \sum_{n=0}^{N/2-1} (x[n] + x[n+N/2]) \cdot W_{N/2}^{nr}$$

$$X[2r+1] = \sum_{n=0}^{N/2-1} (x[n] - x[n+N/2]) \cdot W_N^n \cdot W_{N/2}^{nr}$$

2.4 位反转排序 (Bit Reversal)

1
2
3
4
5
6

function bit_reverse(n, bits):
    result = 0
    for i = 0 to bits-1:
        result = (result << 1) | (n & 1)
        n = n >> 1
    return result

2.5 IFFT

IFFT = 对输入取共轭 → FFT → 取共轭 → 除以 N：

$$\text{IFFT}(X) = \frac{1}{N} \cdot \overline{\text{FFT}(\overline{X})}$$

同一套 FFT 代码即可实现 IFFT。

2.6 实输入的高效 FFT

利用实信号共轭对称性 $X[k] = X^*[N-k]$，用一个 $N$ 点复数 FFT 处理 $2N$ 个实数：

1. 构造 $z[n] = x[2n] + j \cdot x[2n+1]$
2. 对 $z[n]$ 做 $N$ 点 FFT 得 $Z[k]$
3. 恢复：$X_1[k] = \frac{1}{2}(Z[k] + Z^[N-k])$，$X_2[k] = \frac{1}{2j}(Z[k] - Z^[N-k])$
4. 蝶形组合得 $2N$ 点结果

节省约 50% 运算量。

2.7 快速卷积

$$\text{卷积} = \text{IFFT}(\text{FFT}(x) \cdot \text{FFT}(h))$$

补零至 $L \geq N_1 + N_2 - 1$ 即可用循环卷积实现线性卷积。

Overlap-Add

flowchart TD
    A["输入长序列"] --> B["分段（无重叠）"]
    B --> C1["段 1"]
    B --> C2["段 2"]
    B --> C3["段 3"]
    C1 --> D1["FFT 卷积"]
    C2 --> D2["FFT 卷积"]
    C3 --> D3["FFT 卷积"]
    D1 --> E["重叠区域相加"]
    D2 --> E
    D3 --> E
    E --> F["输出"]
    style A fill:#1565C0,color:#fff
    style E fill:#C62828,color:#fff
    style F fill:#228B22,color:#fff

2.8 其他 FFT 算法

工程 FFT 库：FFTW（自适应最优）、ARM CMSIS-DSP（嵌入式）、Intel MKL（x86 SIMD）、cuFFT（GPU）。

小结