离散卷积 | Codeboy's Blog

形式陈述

对有限支撑序列或 $\ell^1(\mathbb Z)$ 序列 $a,b$ ，离散卷积定义为

(a*b)_n=\sum_{k\in\mathbb Z}a_kb_{n-k}.

有限支撑使每个输出只有有限项；在 $\ell^1$ 情形，绝对可和性保证卷积仍属于 $\ell^1$ ，并有

\|a*b\|_1\le\|a\|_1\|b\|_1.

卷积满足交换律与结合律，集中在下标 $0$ 的序列 $\delta_0$ 是单位元。若 $a,b$ 是整数上的概率质量函数，这个公式正是一般测度卷积在计数测度下的坐标表示。

直觉

输出位置 $n$ 不只读取 $a_n$ 与 $b_n$ ，而是遍历所有满足 $k+(n-k)=n$ 的下标分解。第一条序列提供一部分下标，第二条提供余下部分，两项相乘后再把所有形成同一总下标的路径相加。多项式乘法中，同样的机制把次数相加。

例子与边界

若 $a=(1,1)$ 、 $b=(1,1)$ 只支撑在下标 $0,1$ ，则 $a*b=(1,2,1)$ ：中间系数 $2$ 来自分解 $1=0+1=1+0$ 。公平骰子质量函数的自卷积产生先升后降的三角分布，因为中间点数和拥有更多分解。

有限长度信号的 DFT 相乘后逆变换得到循环卷积：下标按长度取模，越界项会绕回开头。若想得到线性卷积，必须先零填充到至少 $m+n-1$ ；遗漏这一步会发生混叠。没有绝对可和性时，重排无穷级数可能改变结果，结合律也不能只凭形式符号宣称。

推论与应用

普通生成函数相乘时， $x^n$ 的系数正是序列卷积，这连接了普通生成函数与组合分拆。快速 Fourier 变换利用“循环卷积在频域变成逐点乘法”，配合零填充把有限线性卷积加速到 $O(n\log n)$ 。离散概率中，独立整数值随机变量之和的质量函数也按同一公式计算。

参考资料

Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022，polynomial multiplication and FFT。
Ronald N. Bracewell, The Fourier Transform and Its Applications, 3rd ed., McGraw–Hill, 2000，discrete and circular convolution。