离散卷积

形式陈述 ​

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

$$(a\ast b{)}_n=\sum _{k\in \mathbb{Z}}{a}_k{b}_{n-k}.$$

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

$$\Vert a\ast b{\Vert }_1\le \Vert a{\Vert }_1\Vert b{\Vert }_1.$$

卷积满足交换律与结合律，集中在下标 $0$ 的序列 ${\delta }_0$ 是单位元。若 $a,b$ 是整数上的概率质量函数，这个公式正是一般测度卷积公理库卷积Convolution · 卷积运算在加法群上把两份测度按加法映射推前，汇总所有可合成为同一输出的输入贡献。在计数测度下的坐标表示。

直觉 ​

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

例子与边界 ​

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

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

推论与应用 ​

普通生成函数相乘时，$x^n$ 的系数正是序列卷积，这连接了普通生成函数公理库普通生成函数Ordinary generating function把序列编码为形式幂级数 Σ a_n x^n。与组合分拆。快速 Fourier 变换公理库快速 Fourier 变换Fast Fourier transform · FFT利用单位根的偶奇分解在 $O(n\log 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。