卷积定理：全书的收款处
前面十三章一直在付钱：混叠、泄漏、分辨率、窗、不确定性。这一章收钱。一条一行的定理，让上一章那个又慢又拧巴的二重循环塌缩成逐点相乘——而且这不是一个关于数据的赌注（第 12 章那种），是一条对任何数据都成立的定理。
两条长度都是 16384 的随机序列，要算它们的卷积（结果长 32767）。两条路：
- 直接算：按上一章那个二重循环，16384 × 16384 ≈ 2.7 亿次乘加。
- 绕道频域：各做一次变换（补零到 32768），逐点相乘，再做一次逆变换。三次变换 + 一次逐点乘。
本机实测直接算用了 402 毫秒。问：绕道频域用多久？
定理
时域卷积 ⟺ 频域相乘
F{ a ✻ b } = F{a} · F{b}
「·」是**逐点**相乘：第 k 根谱线乘第 k 根谱线，各管各的。
反过来也成立（对称的）：时域相乘 ⟺ 频域卷积。第 8 章那个「剪断信号 = 频谱被狄利克雷核涂抹」用的就是这半条，第 9 章的加窗也是。
这条定理是这本书里唯一一个「频域真正值得跑一趟」的理由。前面所有的直觉、图示、账单，都是为了让你能用得起这一行。
为什么
上一章末尾已经把线索摆出来了，这里补完。
卷积说到底是：把核平移到每一个位置，按权重叠加。而我们已经知道：
- 第 4 章：平移 m 个点，在频域里就是给第 k 根谱线乘上 e−i2πkm/N——一个单位长度的复数，只转角度不改长度。
- 线性：叠加在频域里还是叠加。
把两条合起来：
a ✻ b = Σ b[m] · (a 平移 m 个点)
m
在频域里，第 k 根谱线上发生的事：
Σ b[m] · A[k] · e^(−i2πkm/N)
m
┌─────────────────────────┐
= │ A[k] · Σ b[m]·e^(−i2πkm/N) │
└─────────────────────────┘
└────────┬────────┘
这不就是 B[k] 吗
= A[k] · B[k]
就这么四行。那个 Σ b[m]·e−i2πkm/N 正好就是 b 的傅里叶变换的定义——它本来是「平移的权重表」，被复指数一缠，自己变成了频谱。
这也是为什么这条定理属于傅里叶而不属于小波：它的全部依据是「基函数在平移下只变一个相位」。复指数有这个性质（eiθ(t+m) = eiθm·eiθt，平移出来的因子和 t 无关，可以提到求和外面），小波没有。
本机计时
长度 N 直接卷积 走频域 快多少 相对误差 ────────────────────────────────────────────────────────── 1024 3.0 ms 0.3 ms 10× 1.1 × 10⁻¹⁴ 4096 25.0 ms 0.5 ms 52× 4.8 × 10⁻¹⁴ 16384 402.4 ms 2.1 ms 189× 8.4 × 10⁻¹³ ────────────────────────────────────────────────────────── （本机 Node 24，同一份手写实现，非优化代码）
三件事：
第一，倍数随 N 增长。直接卷积是 O(N²)，走频域是 O(N log N)。N 翻四倍，直接算慢 16 倍，走频域只慢 5 倍左右。所以 N 越大，这条定理越值钱——到第 17 章的 2²⁰ 时，倍数会是五位数。
第二，误差在 10⁻¹³ 量级。这不是「近似算法」，两条路算的是同一个数学量，差别全部来自浮点舍入。而且要注意：误差随 N 增大（1.1e−14 → 8.4e−13），因为 FFT 里累加的项更多了。做超高精度计算时这一条要放在心上（这是《抹零》那本书的地盘）。
第三，N=1024 时只快 10 倍。倍数在小 N 时并不夸张，因为三次变换本身也有开销。这引出下面那条「✗ 这个直觉是错的」。
一个必须知道的坑：循环卷积
把「补零」那一步去掉，直接对两条长度 N 的序列做变换、相乘、变回来，你会得到循环卷积——超出末尾的部分不是被丢掉，而是绕回开头去了。
a = [1,2,3,4] b = [1,1,1] 线性卷积（想要的）： 1 3 6 9 7 4 长度 6 在 N=8 里算循环卷积： 1 3 6 9 7 4 0 0 ✓ 一样（补零够） 在 N=4 里算循环卷积： 8 7 6 9 ✗ 尾巴绕回来加到头上了
规则很简单：要得到长度 M = len(a) + len(b) − 1 的线性卷积，变换长度必须至少是 M。不够的话，尾巴会从另一头绕进来，而且绕得悄无声息——结果长度是对的，数值是错的。
这是用 FFT 做卷积时最常见的 bug，而且它在核很短、信号很长时特别难发现：绕回来的只有末尾几个点，前面全对。写完这类代码，一定要拿一个已知答案的短例子对一遍。
重叠相加（overlap-add）和重叠保留（overlap-save）是这条定理的工程化版本，值得知道它们解决什么问题。
问题是这样：你要给一段 3 分钟的音频加混响（脉冲响应 2 秒）。按上面的做法，得把整段音频补零到 3 分钟以上做一次巨大的变换——延迟 3 分钟，内存吃满，而且实时播放根本没法做。
解法是把长信号切成小块，每块单独和核做快速卷积，再把结果按位置叠加起来（每块的输出比输入长，尾巴要加到下一块头上，这就是「重叠相加」）。这样延迟只有一个块长，内存只要一个块。
所有实时的卷积混响插件、所有音频引擎的滤波器、所有大图像的卷积，用的都是这个。它是这条定理和「现实里的信号是流式的、无限长的」之间的那座桥。
把两条路对一遍，顺便亲手撞一次循环卷积的坑：
import numpy as np, time
rng = np.random.default_rng(20260814)
for N in (1024, 4096, 16384):
a, b = rng.standard_normal(N), rng.standard_normal(N)
t0 = time.perf_counter(); d = np.convolve(a, b); t1 = time.perf_counter()
M = 1
while M < 2*N - 1: M <<= 1
f = np.real(np.fft.irfft(np.fft.rfft(a, M) * np.fft.rfft(b, M), M))[:2*N-1]
t2 = time.perf_counter()
print(f'N={N:6d} 直接 {1000*(t1-t0):7.1f} ms FFT {1000*(t2-t1):6.1f} ms '
f'相对误差 {np.abs(d-f).max()/np.abs(d).max():.1e}')
（np.convolve 内部对短序列用直接法，所以这组数会比手写实现快一些，但趋势一样。）
循环卷积的坑，五行就能撞上：
a, b = [1,2,3,4], [1,1,1]
for M in (4, 8):
r = np.real(np.fft.ifft(np.fft.fft(a, M) * np.fft.fft(b, M)))
print(M, np.round(r, 6))
# 4 [8. 7. 6. 9.] ← 绕回来了
# 8 [1. 3. 6. 9. 7. 4. 0. 0.] ← 对的
python3 -c "import numpy as np;print(np.round(np.real(np.fft.ifft(np.fft.fft([1,2,3,4],4)*np.fft.fft([1,1,1],4))),6))"
在线跑：Google Colab。想看它在真实场景里的分量：scipy.signal.fftconvolve 就是这条定理的产品化版本，而 scipy.signal.oaconvolve 是上面说的重叠相加。
- 你听到的每一次卷积混响。一个 2 秒的脉冲响应在 48 kHz 下是 96000 个点，直接卷积每秒要 96000 × 48000 ≈ 46 亿次乘加——单核绝无可能实时。走这条定理加重叠相加，一个手机 CPU 就够了。「卷积混响」这个产品类别的存在，直接依赖这一章。
- 大整数乘法。上一章说过，大数相乘就是数位序列的卷积。于是这条定理直接变成了乘法算法：Schönhage–Strassen（1971）用 FFT 把大整数乘法从 O(n²) 降到接近 O(n log n)，2019 年 Harvey 和 van der Hoeven 做到了严格的 O(n log n)。你的密码学库在算大数乘法时跑的是傅里叶变换。
- 深度学习里的卷积。早期框架（cuDNN 的某些路径、Facebook 的 fbfft）确实用 FFT 加速卷积层。今天主流反而是 im2col + GEMM 或者 Winograd——因为 CNN 的核通常只有 3×3，太小了，落在下面那条「✗」讲的交叉点的另一侧。而扩散模型里那些大核的操作、以及所有的频域数据增强，又用回了这一条。
- 天文与显微成像的反卷积。望远镜拍到的星点是「真实星点 ✻ 点扩散函数」。要还原，理论上在频域里做个除法就行——实际上因为噪声，那个除法极其不稳定（除以一个接近零的数）。整个反卷积领域（维纳滤波、Richardson–Lucy）都是在给这个除法加正则。这条定理让正问题变简单，也让逆问题的病态暴露无遗。
「既然频域卷积快 189 倍，那所有的卷积都应该走频域。」
有个交叉点，而且比大多数人以为的靠后。走频域要付三次变换（约 3·N log N）加一次逐点乘；直接卷积是 N·K，其中 K 是核的长度。
注意这里的不对称：直接卷积的成本正比于核长，频域路线的成本和核长无关。所以：
核很短（K = 3、5、9）： 直接卷积压倒性地快
—— CNN 的 3×3 卷积就在这一侧
核很长（K 上千）： 频域压倒性地快
—— 卷积混响、大图像模糊在这一侧
交叉点： 实践中大约在 K ≈ 30–100 之间
（取决于实现和硬件，要实测）
还有第二个反例：如果你只需要输出的一小部分（比如只要中间 100 个点），直接算那 100 个点就行，而频域路线必须把整条结果都算出来。判据是：先看核有多长，再看你要多少输出——两个都大，才走频域。
正确答案是 C：2.1 毫秒，快 189 倍，相对误差 8.4 × 10⁻¹³。
A 「变换本身也不便宜」——变换确实不便宜，但它是 O(N log N)，而直接卷积是 O(N²)。N = 16384 时，log₂N = 14，两者相差一千多倍；即使算上三次变换和常数因子，实测还是快了 189 倍。这个直觉的问题在于用「感觉复杂」代替了数量级估算——傅里叶变换看起来是个大动作，卷积看起来是个小循环，但那个小循环要跑 2.7 亿次。 B 「快一个数量级」——这是最保守的合理猜测，而它在 N = 1024 时是对的（实测 10 倍）。倍数强烈依赖 N，这一点很值得记住：同一个优化，在小数据上「还行」，在大数据上「决定性」。 D 「三次变换反而不划算」——在核很短的时候这确实是对的（见上面那条「✗」）。这里两条序列都是 16384，属于「大核卷大信号」，是频域路线最擅长的场合。这个答案不是错，是错在没问核有多长。这就是这本书的全部论点，浓缩成一行代码的差别。前十三章讲的所有直觉、所有账单，都是为了让你能用得起这一行——而且知道什么时候不该用它。
还有一件事值得在这里点破：这条定理是双向的。你不只能「用频域加速卷积」，也能「用卷积去实现频域里的想法」——第 15 章的滤波器就是这么设计的：先在频域里画出你想要的形状，再逆变换成一串时域的系数，然后卷上去。频域是设计的地方，时域是执行的地方。
这一章的一句话
时域卷积 = 频域逐点相乘，这是这本书唯一的收款处；而它成立的全部依据只有一条——复指数在平移下只改变一个相位，所以每一根谱线可以各管各的。
拿到这条定理之后，「滤波」这件事的面貌就完全变了。下一章会用它重新定义滤波器：你不是在「删掉」某些频率，你是在拿频谱去乘一条曲线。而这个视角会立刻带来两个不太愉快的结论：那条理想的曲线（通带 1、阻带 0）对应的时域动作需要用到未来，所以造不出来；而任何有限长的近似，都会在边沿留下一个 8.9490% 的翘起——把抽头从 21 加到 401，它只从 9.1164% 掉到 8.9493%。