专题进阶 · 信号处理推荐总顺序 · 第 118 / 148 课

从离散乘加理解卷积,解释线性卷积、循环卷积和补零长度。

先学会这些,再进入本课 离散傅里叶变换 快速傅里叶变换
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 信号处理

卷积Convolution

把输入与翻转平移的核逐点乘加;FFT 计算线性卷积时要填零以避免循环混叠。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

从离散乘加理解卷积,解释线性卷积、循环卷积和补零长度。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

输入 [1,2,3] 经过核 [1,1],每个输出如何由附近输入叠加得到?

02一步步得到方法

每个输入向输出贡献一个平移后的核

定义 y[k]=Σᵢa[i]b[k−i],越界值视为零。也可从另一角度看:a[i] 乘整条 b,并平移 i 个位置,加到输出。这样自然得到输出长度 n+m−1。

卷积公式里核索引是 k−i,隐含翻转和平移;互相关通常使用不同索引方向。深度学习库很多名为卷积的算子实际实现互相关,必须看定义,不要只看 API 名。

频域逐点乘法为什么要补零

DFT 假定长度 N 的序列按周期延拓,所以频域相乘对应 N 点循环卷积。若要得到普通线性卷积,N 必须至少 n+m−1,让非零结果不会绕回开头。

实际选择支持的 FFT 长度,补零、变换、逐点相乘、逆变换,再截取 n+m−1 项。整数卷积的浮点舍入需特别检查,规模大时可考虑模数变换等方法。

每个输出汇总所有贡献到同一位置的配对

离散线性卷积 y[k]=Σᵢa[i]b[k−i],可以看作每个输入脉冲触发一个平移后的响应,再把所有响应相加。输出索引是两个输入索引之和,因此长度为 n+m−1。

DFT 中逐点相乘对应循环卷积。要用 FFT 得到线性卷积,应至少补零到 n+m−1,再选适合实现的变换长度,否则尾部贡献会绕回开头产生混叠。

03把一个小例子完全算清楚

a=[1,2,3],b=[1,1]。

步骤计算与状态为什么这样做
a[0] 的贡献[1,1,0,0]核乘 1,平移 0
a[1] 的贡献[0,2,2,0]核乘 2,平移 1
a[2] 的贡献[0,0,3,3]核乘 3,平移 2
叠加[1,3,5,3]每个输入贡献相加

窄屏可左右滑动表格,阅读完整计算与理由。

若错误使用长度 3 的循环卷积,最后的 3 会绕到首项,得到 [4,3,5]。

04为什么这个方法成立

  1. 输出下标 i+j 收集所有满足 k=i+j 的输入对乘积,等价于定义中的 j=k−i。
  2. 每一对合法输入恰好贡献一次,不丢失也不重复。
  3. 补零到至少线性输出长度时,循环索引不会混合不同的非零输出位置。

05把推导翻译成代码

Python · 可独立运行的教学实现

def convolution(a,b):
    if not a or not b:
        return []
    output = [0]*(len(a)+len(b)-1)
    for i,x in enumerate(a):
        for j,y in enumerate(b):
            output[i+j] += x*y
    return output

逐个理解关键决定

output[i+j] += x*y
下标相加就是两条序列位置组合后的输出位置。
len(a)+len(b)-1
最大下标为 (n−1)+(m−1),所以长度需再加 1。

06时间、空间与实现范围

直接卷积时间 O(nm),输出空间 O(n+m)。

FFT 路线约 O(N log N),但有变换常数和浮点误差;短核直接法常更合适,不能只按渐近式判断。

07改变条件,检查哪里会出错

FFT 不补零直接相乘

得到循环卷积,尾部会折回前部。

把卷积和相关的索引方向混用

相关通常不采用同样的翻转索引,复数场景还涉及共轭,定义不同会改变结果。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[1,0] 与 [2,3] 卷积?

需要一点提示

逐项平移相加。

查看解析与答案

[2,3,0]。

练习 2 · 边界与辨析

核只有 [1] 会怎样?

需要一点提示

单位脉冲。

查看解析与答案

输出等于原输入。

练习 3 · 变式与迁移

多项式相乘和卷积有什么关系?

需要一点提示

指数相加。

查看解析与答案

aᵢxⁱ 与 bⱼxʲ 相乘贡献 aᵢbⱼxⁱ⁺ʲ,系数数组乘法就是卷积。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 科学计算与 FFT 代码

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。