4. 快速傅里叶变换(FFT)：Cooley-Tukey算法、蝶形运算、位反转排序
好，咱们进入FFT的核心环节。说实话，我第一次接触FFT时，满脑子都是“这玩意儿到底怎么加速卷积的？”后来亲手搭了一遍Cooley-Tukey算法，才恍然大悟——原来就是把计算量从O(n²)砍到O(n log n)。
你想想看，一个1024点的DFT，直接算要一百多万次复数乘法。用FFT呢？大概一万次。这差距，在深度学习里就是“等下班”和“等明天”的区别。
4.1 从DFT到FFT：分治思想
DFT的公式长这样：
X[k] = Σ x[n] * W_N^(kn), 其中 W_N = e^(-j*2π/N)直接算，每个k都要遍历所有n。Cooley-Tukey的核心思路就一句话：把大问题拆成小问题。
具体怎么拆？假设N是2的幂（比如1024=2^10），我们把序列分成奇偶两组：
- 偶数项：x[0], x[2], x[4], ...
- 奇数项：x[1], x[3], x[5], ...
然后你会发现一个神奇的事情：
X[k] = X_even[k] + W_N^k * X_odd[k]
X[k + N/2] = X_even[k] - W_N^k * X_odd[k]嗯，这里要注意：X_even[k]和X_odd[k]都是N/2点的DFT。也就是说，一个N点DFT变成了两个N/2点DFT。递归下去，直到变成2点DFT。
关键洞察：FFT不是发明了新东西，而是利用了旋转因子W_N^k的对称性和周期性。说白了，就是发现了很多重复计算，把它们合并了。
4.2 蝶形运算：FFT的基本单元
上面那个公式，画成图就是一只蝴蝶。真的，两只翅膀扑棱扑棱的。
蝶形运算的输入是两个复数a和b，输出是两个复数A和B：
A = a + W * b
B = a - W * b其中W是旋转因子。这个结构在FFT里反复出现，就像卷积神经网络里的卷积核一样，是基本操作单元。
我个人习惯把蝶形运算记成“加一减一乘个W”。为什么？因为每次蝶形只需要一次复数乘法（W*b）和两次复数加法。相比直接DFT，省了太多。
实战技巧：在GPU上实现FFT时，蝶形运算的访存模式很关键。我曾经因为没处理好数据局部性，导致显存带宽跑不满，性能直接腰斩。后来改成按“蝶形组”批量处理，带宽利用率从40%飙到85%。
4.3 位反转排序：数据重排的艺术
好，现在问题来了。递归分治之后，输入序列的顺序被打乱了。你想想看，第一次分奇偶，第二次分奇偶的奇偶...最后得到的顺序是什么？
答案是：二进制位反转。
举个例子，N=8时：
| 原始索引 | 二进制 | 反转后 | FFT输入索引 |
|---|---|---|---|
| 0 | 000 | 000 | 0 |
| 1 | 001 | 100 | 4 |
| 2 | 010 | 010 | 2 |
| 3 | 011 | 110 | 6 |
| 4 | 100 | 001 | 1 |
| 5 | 101 | 101 | 5 |
| 6 | 110 | 011 | 3 |
| 7 | 111 | 111 | 7 |
看到没？索引1（001）反转后变成4（100），所以x[1]要放到第4个位置。这就是位反转排序。
实现位反转排序的代码很简单：
void bit_reverse(float* data, int n) {
int j = 0;
for (int i = 0; i < n - 1; i++) {
if (i < j) {
swap(data[i], data[j]);
}
int k = n >> 1;
while (k <= j) {
j -= k;
k >>= 1;
}
j += k;
}
}避坑指南：我曾经在实现时犯过一个低级错误——把位反转排序和蝶形运算的顺序搞反了。正确的流程是：先位反转排序，再做蝶形运算。如果顺序错了，结果会完全不对。调试了整整一个下午才发现。
4.4 完整的Cooley-Tukey FFT实现
把上面这些拼起来，就是一个完整的基2-FFT：
void fft(complex* data, int n) {
// 1. 位反转排序
bit_reverse(data, n);
// 2. 蝶形运算，逐层合并
for (int len = 2; len <= n; len <<= 1) {
float angle = -2 * M_PI / len;
complex wlen(cos(angle), sin(angle));
for (int i = 0; i < n; i += len) {
complex w(1, 0);
for (int j = 0; j < len / 2; j++) {
complex u = data[i + j];
complex v = data[i + j + len / 2] * w;
data[i + j] = u + v;
data[i + j + len / 2] = u - v;
w *= wlen;
}
}
}
}这段代码虽然短，但包含了FFT的全部精髓。外层循环控制“层数”，内层循环做蝶形运算。每层有N/2个蝶形，一共log2(N)层，总计算量就是O(N log N)。
我的经验：在实际的深度学习框架中，很少直接用这种递归实现。因为递归调用有栈开销，而且不利于向量化。更常见的做法是用迭代方式，配合查表法预计算旋转因子。我在优化一个语音识别模型时，把旋转因子提前算好存起来，推理速度提升了15%。
4.5 FFT加速卷积：到底怎么用？
好了，现在你理解了FFT。那它怎么加速卷积层？
核心定理就一个：时域卷积等于频域相乘。
具体步骤：
- 对输入特征图和卷积核分别做FFT
- 在频域做逐元素乘法
- 对结果做IFFT（逆FFT）
为什么这样更快？因为FFT是O(N log N)，而直接卷积是O(N²)。当卷积核尺寸较大时（比如7×7、11×11），FFT的优势就体现出来了。
不过要注意，小卷积核（3×3）用FFT反而慢。为什么？因为FFT有额外的变换开销，而且需要把数据补齐到2的幂次。我做过实验，在3×3卷积上，FFT比im2col+GEMM慢了2-3倍。所以现在主流框架里，FFT主要用在5×5以上的大核卷积。
一句话总结：FFT加速卷积，本质是用O(N log N)的变换代价，换取O(N²)的卷积计算。核越大，赚得越多。
嗯，这一章的内容就到这儿。下一章咱们聊聊怎么把FFT真正塞进卷积层里，包括内存布局、边界处理这些实战细节。到时候我会分享一个我在项目里踩过的坑——因为没处理好padding，结果FFT出来的结果全是错的，排查了整整两天。