第4章频域卷积定理

4. 频域卷积定理：时域卷积等于频域乘积、FFT加速卷积的数学推导、计算复杂度分析

好，咱们今天聊点硬核的。频域卷积定理，这名字听着挺吓人，其实说白了就一句话：时域里的卷积，等于频域里的乘法。

我当年刚接触这个定理时，第一反应是——这不废话吗？后来真上手做推理优化才发现，这玩意儿是FFT加速卷积的理论基石。没有它，我们后面所有加速手段都是空中楼阁。

先看数学定义。假设有两个离散信号 \( x[n] \) 和 \( h[n] \)，它们的卷积是：

y[n] = x[n] * h[n] = Σ x[k] · h[n - k]   (k从0到N-1)

这个公式，你想想看，每个输出点都要做N次乘加。如果信号长度是N，复杂度就是O(N²)。

而频域卷积定理告诉我们：

FFT(x[n] * h[n]) = FFT(x[n]) · FFT(h[n])

也就是说：先做FFT，频域里点乘，再做IFFT，结果和时域卷积一模一样。

核心结论：时域卷积的复杂度是O(N²)，频域乘法的复杂度是O(N)。但别忘了，我们还得算两次FFT和一次IFFT。所以整体复杂度是O(N log N)。

我在项目中遇到过这样一个场景：一个3x3的卷积核，在1024x1024的图像上做滑动窗口。直接卷积要算将近1000万次乘加，而用FFT方法，三次变换加一次点乘，总共才几十万次操作。差距就是这么明显。

好，咱们一步步推。别怕，我尽量用大白话。

第一步：补零

卷积核和输入信号长度不同，直接做FFT会出问题。我习惯把两者都补零到相同长度L，且L ≥ N + M - 1（N是信号长度，M是卷积核长度）。

x_pad = [x[0], x[1], ..., x[N-1], 0, 0, ..., 0]  (长度L)
h_pad = [h[0], h[1], ..., h[M-1], 0, 0, ..., 0]  (长度L)

第二步：FFT变换

对补零后的信号做FFT：

X = FFT(x_pad)
H = FFT(h_pad)

第三步：频域点乘

在频域里，每个频率点直接相乘：

Y[k] = X[k] · H[k]   (k = 0, 1, ..., L-1)

第四步：IFFT逆变换

把结果变回时域：

y = IFFT(Y)

取前N+M-1个点，就是卷积结果。

我的小技巧：实际工程中，我一般用L = 2^ceil(log2(N+M-1))，这样FFT效率最高。因为FFT对2的幂次长度有优化，速度能快好几倍。

咱们来算笔账。假设输入信号长度N，卷积核长度M，且N远大于M。

方法	复杂度	实际例子（N=1024, M=3）
直接卷积	O(N·M)	约3072次乘加
FFT卷积	O(L log L) + O(L) + O(L log L)	约3·1024·log2(1024) ≈ 30720次操作

等等，你可能会问：这看起来FFT更慢啊？

嗯，这里有个关键点：当卷积核很大时，FFT的优势才体现出来。比如M=256时：

方法	复杂度	实际例子（N=1024, M=256）
直接卷积	O(N·M)	约262144次乘加
FFT卷积	O(L log L)	约30720次操作

看到了吧？当卷积核大到一定程度，FFT方法能快一个数量级。

我曾经踩过的坑：有一次我用FFT加速一个3x3的卷积，结果发现比直接卷积还慢。后来一查，原来是FFT变换的开销太大，小卷积核根本划不来。所以，经验法则：卷积核尺寸大于7x7时，才考虑用FFT加速。

说实话，在AI芯片部署中，我们很少直接用FFT做卷积。为什么？

但FFT卷积在大卷积核、大分辨率的场景下，依然是利器。比如某些语音模型、雷达信号处理，卷积核动不动就几百点，这时候FFT就是最优解。

我个人习惯是：先评估卷积核大小和输入尺寸，再决定用哪种方法。如果卷积核小于7x7，直接卷积；如果大于，就上FFT。中间地带可以用Winograd算法，那是另一个话题了。

好了，这一节就到这里。记住一句话：时域卷积等于频域乘积，这是FFT加速的理论基础，但工程实现要权衡利弊。下一节咱们聊聊怎么在NPU上高效实现FFT卷积，那才是真正的实战环节。