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为什么这个方法成立
- 输出下标 i+j 收集所有满足 k=i+j 的输入对乘积,等价于定义中的 j=k−i。
- 每一对合法输入恰好贡献一次,不丢失也不重复。
- 补零到至少线性输出长度时,循环索引不会混合不同的非零输出位置。
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,0] 与 [2,3] 卷积?
需要一点提示
逐项平移相加。
查看解析与答案
[2,3,0]。
核只有 [1] 会怎样?
需要一点提示
单位脉冲。
查看解析与答案
输出等于原输入。
多项式相乘和卷积有什么关系?
需要一点提示
指数相加。
查看解析与答案
aᵢxⁱ 与 bⱼxʲ 相乘贡献 aᵢbⱼxⁱ⁺ʲ,系数数组乘法就是卷积。