搞数字信号处理的没被循环卷积和线性卷积折磨过那基本不太正常。尤其是学到DFT那一章书上突然冒出来一句“循环卷积可以通过DFT计算”紧跟着又说“线性卷积可以通过补零然后用循环卷积实现”很多人直接就晕了两个东西明明长得不一样怎么绕一圈又等价了这不矛盾吗我当时学这块也卡了很久。后来自己亲手把两个序列的卷积结果列出来补零、延拓、对位、相加一步步走一遍才发现这件事其实特别直观就是“周期延拓之后发生混叠”和“补零补够长度让混叠自然消失”的区别而已。搞明白这个DFT做快速卷积、分段卷积这些实用技巧就都通了。这篇文章就围绕“循环卷积和线性卷积的关系”来写适合刚学完DFT、正在做课程设计或者是被“为什么FFT卷积要先补零”这个问题困扰的同学。我会从两者定义讲起配合具体的数值演算把等价条件为什么是 L ≥ N1 N2 - 1 讲透再补充快速卷积的实现步骤和工程里常见的坑。1. 先搞懂两个卷积的底层逻辑1.1 线性卷积我们最熟悉的“反折-移位-相乘-累加”线性卷积的定义我不多念书上的公式了直接给个直观理解。假设有两个有限长序列一个长度 N一个长度 M那么它们的线性卷积结果长度是 N M - 1。怎么算出来的就是拿一个序列逐点滑动和另一个序列相乘再累加滑一次出一个点。举例来说取 x[n] [1, 2, 3]h[n] [4, 5]它俩的线性卷积用手写一遍y[0] 1×4 4y[1] 1×5 2×4 13y[2] 2×5 3×4 22y[3] 3×5 15所以结果 y [4, 13, 22, 15]长度是 3 2 - 1 4。线性卷积的物理意义很明确它对应的是“输入信号通过一个线性时不变系统的完整响应”每个输出点都是系统对所有历史输入的记忆叠加。滤波、系统响应、信号通过信道这些场景下我们通常要的都是线性卷积。1.2 循环卷积周期延拓以后的对位相乘累加循环卷积的定义看起来也很简单只是把“反折-移位”里的移位换成了“循环移位”。所谓循环移位就是平移之后超出序列范围的元素不从另一边补回来而是绕回去像在一个圆环上转圈。设两个序列长度都为 L循环卷积要求两个序列按同一个长度 L 来算那么循环卷积定义为y[k] Σ_{n0}^{L-1} x[n] · h[(k-n) mod L]重点在 (k-n) mod L这就是循环的意思。算出来的结果长度也是 L不会变长。所有下标都是对 L 取模之后的值所以序列被看成是长度为 L 的周期序列。还是用 x[n] [1, 2, 3]h[n] [4, 5] 来举例但做循环卷积时两个序列都得先扩展成同样长度。假设取 L 4那就要给 x 补一个零、给 h 补两个零x [1, 2, 3, 0]h [4, 5, 0, 0]按循环卷积公式一项项算y[0] x[0]h[0] x[1]h[3] x[2]h[2] x[3]h[1] 1×4 2×5 3×4 0×5 26y[1] x[0]h[1] x[1]h[0] x[2]h[3] x[3]h[2] 1×5 2×4 3×5 0×4 28y[2] x[0]h[2] x[1]h[1] x[2]h[0] x[3]h[3] 1×4 2×5 3×4 0×5 26y[3] x[0]h[3] x[1]h[2] x[2]h[1] x[3]h[0] 1×5 2×4 3×5 0×4 28结果是 [26, 28, 26, 28]跟线性卷积的 [4, 13, 22, 15] 完全对不上。问题就出在循环卷积里 h 的下标是取模得到的比如 h[(0-1) mod 4] 取到的其实是 h[3]而在原来的线性卷积里 h[3] 根本不存在它应该是补零后的点不是绕回来的值。这就是循环卷积和线性卷积最本质的区别线性卷积干干净净地算完结果变长循环卷积把超出边界的部分“绕回来”叠加到了前面的输出点上导致结果被“污染”。1.3 为什么DFT天然对应循环卷积这里要给刚学到这儿的同学提一个重要结论时域循环卷积对应频域乘积即 DFT(x ⊛ h) X(k) · H(k)。同样的频域循环卷积对应时域乘积。但很多人容易忽略一个点DFT处理的是有限长序列可它在数学上有一个隐含的“周期延拓”假设。教科书上会说“DFT是DFS取主值区间”意思就是你先想象这个序列在无限长周期延拓然后取其中一个周期做变换。既然信号是周期的那么时域卷积自然也是周期的也就是循环卷积。所以当你直接用 FFT 做两个序列的频域相乘再逆变换回来得到的结果本质上是循环卷积不是线性卷积。工程当中大多数场景要的是线性卷积这就直接导致我们在用 FFT 之前必须做一些处理把循环卷积的结果“修正”成线性卷积。2. 核心关系两者什么时候相等为什么是这个条件2.1 循环卷积是怎么“混叠”线性卷积结果的上面那个例子已经看到现象了用 L 4 做循环卷积结果跟线性卷积完全不是一回事。那如果把 L 逐步变大会发生什么如果取 L 5那么两个序列补零成 x [1, 2, 3, 0, 0]h [4, 5, 0, 0, 0]。此时再按循环卷积公式算y[0] 1×4 4y[1] 1×5 2×4 13y[2] 2×5 3×4 22y[3] 3×5 15y[4] 0结果是 [4, 13, 22, 15, 0]。你看前面 4 个点跟线性卷积一模一样就多了一个 0。为什么因为当 L 足够大之后循环移位 (k-n) mod L 取到的那些“绕回”位置都正好落在补零的区域内。也就是说原本会从尾部绕到头部造成混叠的那些项现在全部乘的是 0混叠也就随之消失了。换个角度想线性卷积结果长度为 NM-1只要循环长度 L 不小于这个长度那么线性卷积结果的 NM-1 个点可以被完整放进一个周期里不会出现前后周期相互重叠的情况。反之如果 L NM-1周期延拓后的各个周期就会“叠”在一起重叠部分的数值加到一起导致输出跟线性卷积不同。2.2 条件推导L ≥ NM-1 是怎么来的这里可以很直观地推一下。线性卷积的非零范围是x 的非零范围0 ≤ n ≤ N-1h 的非零范围0 ≤ n ≤ M-1卷积结果 y[n] 的非零范围0 ≤ n ≤ NM-2总长度 NM-1。如果用循环卷积长度 L 来做两个序列都补零到 L 点。循环卷积在取模移位时如果它访问到的 h[(k-n) mod L] 对应的是补零区间就不会产生混叠如果它访问到的是 h 原本的非零区间才是正常贡献。判断混叠是否发生关键看线性卷积结果的“尾巴”会不会在周期延拓时再退回到头部。线性卷积结果是一个长度为 NM-1 的有限长序列现在要以 L 为周期延拓。做周期延拓就是把它不断复制平移每个周期的位置相隔 L。如果 NM-1 ≤ L那么相邻两个周期的结果刚好首尾相邻不会重叠取主值区间后就是完整的线性卷积结果。如果 NM-1 L那相邻两个周期就会有长度为 NM-1-L 的重叠段重叠部分的数值必须相加这在时域上等价于“尾部折叠叠加到头部”。所以条件就是循环卷积长度 L 必须满足 L ≥ NM-1此时循环卷积的结果在 0 到 NM-2 这些点上等于线性卷积其余点为零。这也是为什么用 DFT 做卷积时通常会取 L NM-1 或者取一个不小于它的 2 的幂方便 FFT这个 2 的幂还要大于等于 NM-1。2.3 改变循环卷积长度的本质是改变周期大小这个点可以再深挖一下对真正理解 DFT 卷积特别有帮助。循环卷积长度 L 一拍脑袋随便取本质上是人为设定周期延拓的周期。同一个序列周期越短相邻周期之间的重叠越严重混叠加的项越多。比如同样是 x[n] [1, 2, 3]h[n] [4, 5]你取 L 3两个序列各只有 3 个点循环卷积算出来是y[0] x[0]h[0] x[1]h[2] x[2]h[1] 1×4 2×5 3×4 26这里 h[2] 取的是 h[0] 绕回h[1] 是正常的y[1] x[0]h[1] x[1]h[0] x[2]h[2] 1×5 2×4 3×5 28y[2] x[0]h[2] x[1]h[1] x[2]h[0] 1×4 2×5 3×4 26结果是 [26, 28, 26]和 L4 时的前三个值一样因为真正造成差异的就是尾部绕回的那一项。取 L3 时尾部绕回的项更多、叠加得更严重整段结果都乱了。我自己的理解是循环卷积的长度 L 决定了周期有多长周期越长线性卷积结果延拓后互相叠的概率越小L 只要超过结果总长度就“一点重叠都不剩”此时循环卷积和线性卷积完全一致。所以你不需要记住复杂的数学证明记住“周期延拓重叠则混叠”这八个字就够了。3. 实战用循环卷积实现线性卷积的完整流程3.1 核心步骤补零、DFT、相乘、IDFT既然 DFT 做的是循环卷积那要实现线性卷积思路就一句话把循环卷积的周期拉长长到不重叠为止。假设 x[n] 长度 Nh[n] 长度 M目标是算 y[n] x[n] * h[n]线性卷积。标准做法如下计算最小循环长度L_min N M - 1。选实际 FFT 长度 L为了用 FFT 加速一般取 L 2^ceil(log2(NM-1))即不小于 L_min 的最接近的 2 的幂。当然如果直接用 DFTL 取任意不小于 L_min 的数都行。给 x[n] 后面补 L-N 个零给 h[n] 后面补 L-M 个零让两个序列长度都变成 L。分别做 L 点 DFT得到 X[k] 和 H[k]。逐点相乘 Y[k] X[k] * H[k]。对 Y[k] 做 L 点 IDFT得到 y[n]。取 y[0] 到 y[NM-2] 这 NM-1 个点作为最终线性卷积结果后面从 y[NM-1] 开始应该是 0数值上有浮点误差时会是非常小的数。第 3 步是这个方法里最“灵魂”的一步。很多新手犯的错就是“我已经补零到两个序列一样长了”但实际上补的零根本不够。比如 N1000M50有人直接把两个序列都补零到 1000 点就去做 FFT结果出来前一段是对的、后一段全乱了就是因为 L1000 小于 NM-11049尾部混叠已经发生。3.2 一个可以照着跑的代码示例为了把流程固定下来这里给一段 Python 代码核心逻辑用 numpy 实现并把每一步都注释清楚。这段代码可以直接复制到一个 .py 文件里运行。import numpy as np # 两个测试序列 x np.array([1.0, 2.0, 3.0]) h np.array([4.0, 5.0]) N len(x) M len(h) # 1. 最少需要的循环卷积长度 L_min N M - 1 # 2. 实际FFT长度为了加速取不小于L_min的2的幂 L 1 while L L_min: L 1 # 3. 补零到长度L x_pad np.zeros(L) x_pad[:N] x h_pad np.zeros(L) h_pad[:M] h # 4. 各自FFT X np.fft.fft(x_pad) H np.fft.fft(h_pad) # 5. 频域逐点相乘 Y X * H # 6. 逆变换回时域 y_ifft np.fft.ifft(Y).real # 理论上应该是实数浮点误差会产生极小的虚部 # 7. 取前NM-1个点作为线性卷积结果 y_lin y_ifft[:L_min] # 对比用numpy直接算的线性卷积 y_conv np.convolve(x, h) print(直接线性卷积: , y_conv) print(FFT循环卷积: , y_lin) print(误差: , np.max(np.abs(y_lin - y_conv)))这段代码跑出来误差基本在 1e-14 这个量级可以认为是数值误差不是算法错误。很多人会问为什么 ifft 之后要取 .real因为浮点运算里 FFT/IFFT 产生的虚部误差虽然极小但你如果不取实部后面看数据时总觉得哪里不对劲甚至有人直接把虚部当成错误信号。实际上对于实数信号IDFT 的理论结果是实数所以取实部是合理且常规的操作。3.3 FFT卷积到底快在哪什么时候该用直接线性卷积的复杂度是 O(NM)因为每个输出点要做 M 次乘法累加总共 NM-1 个输出点。FFT 方法复杂度是 O(L log L)其中 L 取 2 的幂。补零后 L 约等于 NM所以复杂度近似 O((NM) log(NM))。当 N 和 M 都大时FFT 方法的优势非常明显。比如 NM1024直接卷积大约要做 100 万次乘加而 L2048 的 FFT 大约是 2048×11 ≈ 22528 次蝶形运算量差距接近 50 倍。信号越长差距越夸张。但要注意如果其中一个序列特别短比如滤波器长度只有 8 个点输入也只有 64 个点那这种短序列直接用 conv 反而更快。因为 FFT 有固定开销包含补零、正变换两次、反变换一次、频域复数乘法光这些调用本身的成本就超过直接卷积了。我实测过阈值大概在 N、M 都超过 30~50 以后FFT 才开始体现优势。工程上到底用哪种可以先算一下量级再决定别迷信“FFT 一定快”。4. 工程里的延伸长序列滤波和分段卷积4.1 一个输入无限长滤波器有限长怎么搞实际工程里经常遇到这种情况滤波器 h[n] 长度固定为 M但输入信号 x[n] 非常长甚至是一个流式信号不能等全部收到再做 FFT。比如实时音频处理、雷达回波处理信号一直在来内存也存不下整个序列。这时候就需要分段卷积。分段卷积的基本思路是把长输入切成长度 L_block 的小块每块分别和 h[n] 做线性卷积然后把各块的卷积结果按重叠部分相加。这就是重叠相加法overlap-add。做法如下取块长 L_block要求 L_block M - 1 不超过 FFT 长度通常直接让 FFT 长度 L L_block M - 1。对每一块 x_i[n] 补零后做 FFT乘以 H[k]H 是 h 补零后的 FFT只需要算一次再 IFFT。每块的输出长度是 L_block M - 1相邻块的输出会有 M-1 个点的重叠。将当前块输出与上一次保留下来的 M-1 个点相加再输出有效的前 L_block 个点后 M-1 个点留给下一次叠加。这个过程用代码实现并不复杂但有点绕。核心点就一个每块独立卷积的结果在重叠区要相加而不是直接覆盖。与之对偶的方法是重叠保留法overlap-save它不重叠相加而是重叠保留输入丢弃输出中混叠的那部分。两种方法效果一样只是实现细节和边界处理习惯不同。分段卷积是 FFT 卷积真正发挥价值的地方因为如果整体做 FFT需要等信号全部到齐这在实时系统里根本不可能。4.2 频域滤波其实也是循环卷积思想自适应滤波、OFDM 调制解调、声学回声消除这类系统里块处理方式非常常见。它们的共同点是先把时域信号分块转频域处理再转回时域。如果块长度和滤波器长度考虑不当就很容易出现“看起来处理了但数据对不上”的诡异现象。举个例子OFDM 里为了保护多径时延扩展会在符号之间插入循环前缀。循环前缀的本质是一种循环延拓它让线性卷积的信道响应变成循环卷积的形式这样接收端就能直接用频域均衡做单抽头补偿。这里面“线性卷积变循环卷积”的思路跟本文讲的补零恰好是相反方向的操作但都是同一个思想在不同场景下的应用。另一个例子是很多音频处理教材里提到的“频域卷积”实验把一段音频和某个房间冲激响应做卷积模拟混响效果。如果你不补零直接对两个信号做 FFT 相乘再 IFFT出来的音频会有一个很明显的“回环”杂音这就是循环卷积的尾部混叠在音频上听起来像回声短路一样其实也就是周期延拓导致的时域 aliasing。4.3 圆周卷积谱与快速卷积理论的统一视角如果仔细琢磨可以感觉到这里面的理论闭环DFT 是傅里叶变换的离散化周期化版本它处理的所有序列都隐含周期延拓因此在 DFT 域做卷积天然是循环卷积而线性卷积是物理世界对“有限长输入经过有限长冲激响应系统”的描述。要在 DFT 域实现物理世界的线性卷积就必须通过补零扩大周期消除周期重叠。补零这个操作看似简单实质是把“循环卷积”的周期拉大到足以承载“线性卷积”的结果长度让两个数学对象在同一个计算平台上统一起来。这也是很多专业课程里把 DFT、循环卷积、快速卷积、重叠相加法串在一起讲的原因。理解了这条主线遇到相关问题时你脑子里会有一个统一的判断标准这个系统里线性卷积结果会不会发生周期重叠重叠了怎么处理是补零防混叠还是故意利用循环卷积的特性5. 学习与实操中常见的坑5.1 补零长度只补到两个输入一样长这个错误简直太典型了。比如 x 长度 500h 长度 200很多人觉得“我把两个都补零到 512然后用 512 点 FFT”看起来挺对称。但注意线性卷积长度是 699512 根本不够。结果就是卷出来的前 500 个点可能还能看从第 500 个点开始后续响应全部消失尾部混叠值直接叠在头部附近整体结果和预期差一大截。正确做法是先算 NM-1再决定 FFT 长度。哪怕不用 FFT、直接调库函数也要对输出长度的预期心里有数。5.2 忘记取 IFFT 的前 NM-1 个点补零补够了FFT 也做了IFFT 也做了结果发现输出数组长度为 L而 L 往往大于预期的 NM-1。如果直接把整个数组拿去跟线性卷积结果比后面多出来的一串近似为 0 的数会影响误差判断有时候甚至有人把多出来的零当成有效信号导致后面处理数组长度不匹配。习惯做法是IFFT 后只取前 NM-1 个点。多出来的点要么是非常小的浮点噪声要么是严格为 0。处理信号数组时长度不匹配的 bug 很难排查最好一开始就指定输出区间。5.3 实数序列做完 FFT 后埋着复数虚部不管很多信号是实数FFT 之后变成复数IFFT 回来理论上是实数但由于浮点误差虚部会有 1e-15 量级的残留。如果不取实部后面绘制波形图时会看到一些莫名其妙的极小虚部虽然不影响幅值但有些工具里会警告“数据是复数”甚至导致画图报错。建议在 IFFT 后用 .real 取实部。但也别用全盘取绝对值的方式处理因为信号里可能有负值取绝对值会把负半轴整体翻上去破坏波形。5.4 下标从 1 还是从 0最容易把人绕晕MATLAB 里索引从 1 开始Python 里从 0 开始。线性卷积定义里 y[n] 的 n 也是从 0 开始标。写代码的时候补零位置、取主值区间、分段卷积的块索引这些地方但凡少一个 1 或者多一个 -1结果就可能整体偏移一位。而且这种偏移在波形图上肉眼几乎看不出来只有和参考结果做数值对比时才能发现。我的经验是写卷积相关代码时不要直接看公式抄先把一个特别小的测试序列跑起来比如 x[1,2]h[3,4]手算出线性卷积结果然后程序跑一遍逐步打印中间过程来核对索引。5.5 用频域相乘实现卷积时忘了 H 也要补零有时候 x 补零了H 的 FFT 却用的是原始长度或者反过来。这会造成 X[k] 和 H[k] 的频谱点数不一致FFT 长度不匹配时直接相乘会报错或者更隐蔽的是长度碰巧一致但补零规则不一样比如 X 补到了 1024H 只补到了 512然后广播相乘结果完全没有意义。所有参与 DFT 的序列必须补到同一个长度 L。这里没有例外。5.6 把 FFT 卷积用在小规模序列上反而更慢这一点是性能上的坑。FFT 卷积虽然在大规模下有巨大优势但小规模下并不划算。比如两个长度都只有 8 的序列直接用双重循环 64 次乘法就够了FFT 反而要做补零、64 点 FFT、复数乘法、IFFT耗时可能是直接卷积的 5 到 10 倍。我在实际项目里一般会设置一个阈值比如 N*M 2000 时才切换 FFT 方案低于阈值直接暴力卷积整体性能最优。5.7 验证结果时只看“像不像”不看数值做实验最忌讳的就是输出画出来“看起来差不多”就交差。循环卷积与线性卷积的差异不是噪声而是结构性的。如果你补零长度差得不多混叠可能只出现在特定区间图像整体趋势接近但个别点偏差很大。这种问题肉眼不一定看得出来但数值一对比就暴露了。我自己的习惯是每次跑通 FFT 卷积后用 np.convolve 或者 MATLAB 的 conv 函数做一次对照计算 max(abs(y_fft - y_conv))只要这个值在 1e-10 以下说明实现没问题。之后再去做长信号的工程实现心里就有底了。最后说点实际的循环卷积和线性卷积的关系说到底是数学在“有限长”这件事上的一次精妙折中DFT 只能处理有限长序列但它骨子里又是周期性的所以卷积必须按循环来做而物理世界大量场景需要的线性卷积恰好可以通过把周期拉长来“假装”实现。补零不是为了好看也不是为了凑 2 的幂而是为了给线性卷积结果腾出一个不重叠的周期空间。我在实验室里第一次自己写 FFT 卷积滤波器的时候就是没把补零长度当回事用的 512 点 FFT 去处理 300 点信号和 200 点冲激响应结果输出从第 113 个点左右开始完全变形。后来画图才发现是尾部周期混叠一下就想通了“L ≥ NM-1”这个条件到底在防什么东西。从那以后再遇到频域卷积、分段滤波我第一件事就是算清楚长度再开始写代码。希望这篇文章也能让你少走这个弯路。