FFT 实现快速卷积时，为什么会出现混叠？(二)如何用 Overlap-Save 解决？

上一篇我们讲了：FFT 实现快速卷积时，问题不在 FFT 本身，而在于频域乘法 + IFFT 默认得到的是循环卷积。如果直接把循环卷积结果当成线性卷积来用，就会出现“尾巴折回前面”的时域混叠。

第一期介绍的是 overlap-add，它的思路是：先把每一块卷积结果完整算出来，再把块与块之间的重叠部分加起来。这一期我们看他的姊妹方法：overlap-save， 它的主要思路是：既然循环卷积前面那一小段会被污染，那就不要它，直接丢掉，只保留后面那一段有效输出。

本文和仿真实验代码同步发在个人博客网站VoxWorking · 声学与音频知识平台，网站定期更新音频处理、语音处理和声学相关知识，欢迎大家浏览交流~

1. FFT快速卷积时的混叠和Overlap-Save思路

先回顾上一篇里的关键结论：如果一块输入做 N 点 FFT，与滤波器频响相乘，再做 N 点 IFFT，得到的是 N 点循环卷积，不是线性卷积。如果滤波器长度为 M，那么循环卷积中最容易出问题的是前 M-1 个样本。当前块真实线性卷积的尾部，会按模 N 折回到块前面，于是 IFFT 输出最前面的那一小段被“上一轮折返”污染。

Overlap-save 的思路是：既然IFFT 输出最前面的那一小段被“上一轮折返”污染，那就每次取长度为 N 的输入块，相邻输入块之间重叠 M-1 个样本，做 FFT、乘法、IFFT，丢掉前 M-1 个污染样本，保留后 L = N - M + 1 个有效样本，下一块继续处理，再把这些有效段顺次拼接。

所以Overlap-Save和Overlap-Add两种方法本质上都在解决同一个问题：**如何把循环卷积重新组织成线性卷积。**只是实现思路不一样：OLS（Overlap-Save）让输入先重叠，再把每块输出前面的污染段丢掉;OLA（Overlap-Add）完整保留每块输出，再把输出重叠区相加。

假如FFT 点数为 N、FIR 滤波器长度为 M，每块最终保留的有效输出长度为 L，那 overlap-save 的基本关系就是：L = N - M + 1。即：每做一次 N 点循环卷积，其中前 M-1 点不可信，后 L 点才是可以直接拼接到总输出里的有效部分。

为什么是前 M-1 点被污染 ：因为对一个长度为 N 的输入块和一个长度为 M 的滤波器做线性卷积时，真实输出长度应该是：N + M - 1，而循环卷积只能保留 N 点，超出的后半段会折返到前部。折返影响的正好就是前面那 M-1 个位置，所以 overlap-save 里要把它们丢掉。

2. 结合Python仿真说明：混叠和Overlap-Save解决方法

本文构造一个包含多频正弦和两个瞬态脉冲的测试信号，再让它通过一个长度为 25 的 FIR 滤波器。

图1：(a)一个包含多频正弦和两个瞬态脉冲的测试信号 和 (b)一个长度为 25 的 FIR 滤波器

仿真参数：FFT 点数：N = 128，滤波器长度：M = 25，每块有效输出长度：L = N - M + 1 = 104，每块需要丢弃的污染长度：M - 1 = 24。

先单独看一个块：

图2： (a)线性卷积结果和FFT快速卷积（循环卷积）结果； (b)两者之间的误差结果图

上半部分绿色：线性卷积结果中对应这一段的真实输出，红色虚线：FFT 乘法再 IFFT 得到的循环卷积输出。可以看到最前面一段不对，后面一大段逐渐和线性卷积重合。下半部分画出了误差，前 M-1 = 24 个点误差明显，从第 24 点之后，误差接近 0。

如果把每块循环卷积的前面那段错当成有效输出，就会出现周期性失真；而如果按 overlap-save 的规则保留后 L 点，结果就会恢复成正确的线性卷积。对应仿真结果如下：

图3：(a)错误方法与真值对比；(b)错误方法相对真值的误差; (c) overlap-save 与真值对比

从图3中可以看出：如果错误地保留每块前面的污染段，失真会按块周期性重复。这些错误不是偶然数值波动，而是循环卷积折返造成的结构性错误。overlap-save 只保留每块后面的有效段后，结果与时域线性卷积重合。脚本同时输出误差指标，错误方法最大绝对误差超过 1.8，overlap-save 与时域直接卷积在本实验里数值一致，在满足条件时，overlap-save可以严格恢复线性卷积。

nfft=128
filter_len=25
valid_len=104
discard_len=24
wrong_keep_first_max_abs_error=1.8308787814
wrong_keep_first_rmse=0.9946940693
overlap_save_max_abs_error=0.0000000000
overlap_save_rmse=0.0000000000

误差分布图如下：

图4： (a) 错误方法的误差分布图； (b)overlap-save方法的误差分布图

3. Python 仿真代码

完整代码见：工程实践 · VoxWorking，主要的两个函数如下：

错误示范：把每块前面的污染段错当成有效输出保留下来。

def naive_keep_first_valid(x, h, nfft):
    m = len(h)
    l = nfft - m + 1
    h_fft = np.fft.fft(h, nfft)
    xpad = np.concatenate((np.zeros(m - 1), x, np.zeros(m - 1)))
    outputs = []
    starts = range(0, len(x) + m - 1, l)
    for start in starts:
        block = xpad[start : start + nfft]
        if len(block) < nfft:
            block = np.pad(block, (0, nfft - len(block)))
        y_block = np.fft.ifft(np.fft.fft(block) * h_fft).real
        outputs.append(y_block[:l])
    return np.concatenate(outputs)[: len(x) + m - 1]

正确做法：每块丢弃前 M-1 个样本，只保留后 L 个样本。

def overlap_save_filter(x, h, nfft):
    m = len(h)
    l = nfft - m + 1
    h_fft = np.fft.fft(h, nfft)
    xpad = np.concatenate((np.zeros(m - 1), x, np.zeros(m - 1)))
    outputs = []
    starts = range(0, len(x) + m - 1, l)
    for start in starts:
        block = xpad[start : start + nfft]
        if len(block) < nfft:
            block = np.pad(block, (0, nfft - len(block)))
        y_block = np.fft.ifft(np.fft.fft(block) * h_fft).real
        outputs.append(y_block[m - 1 :])
    return np.concatenate(outputs)[: len(x) + m - 1]

4. overlap-save 和 overlap-add 怎么选？

很多人学完这两种方法后，可能会有个疑问：到底什么时候用 OLA，什么时候用 OLS？其实这两个方法没有什么好坏，都可以把 FFT 的块循环卷积恢复成正确的线性卷积。用哪个方法取决具体的应用场景和个人习惯，我个人更习惯OLS方法，显式丢弃污染段；如果更容易接受“线性卷积完整输出再叠加”的思路，OLA 更直观也完全可以。

5. 小结

FFT 快速卷积中的每一块 IFFT 输出，本质上仍然是循环卷积。循环卷积前 M-1 个样本会受到尾部折返污染，因此不能直接当线性卷积使用。overlap-save 通过“输入块重叠 + 丢弃前 M-1 点 + 保留后 L 点”，恢复出正确的线性卷积输出。overlap-add 和 overlap-save 只是组织方式不同，目标都是修正块循环卷积的边界问题。