= Discrete convolution
{title2=$(a*b)_n=\sum_{m\in\mathbb Z}a_m b_{n-m}$}
For <sequences> $a,b$ indexed by the <integers>, discrete convolution adds products whose indices sum to the output index:
$$
(a*b)_n=\sum_{m\in\mathbb Z}a_m b_{n-m}.
$$
For finite sequences, treat every unspecified entry as zero; the sum then has finitely many nonzero terms. For infinite sequences, a convergence hypothesis is needed, for example <absolute summability> of both sequences.
Take $a=(1,2,1)$ at indices $0,1,2$ and $b=(1,1)$ at indices $0,1$. Their <convolution> is \b[$(1,3,3,1)$] at indices $0,1,2,3$:
$$
c_0=1\cdot1=1,\quad c_1=1\cdot1+2\cdot1=3,\quad c_2=2\cdot1+1\cdot1=3,\quad c_3=1\cdot1=1.
$$
Equivalently, $c_n=a_n+a_{n-1}$: add an unshifted and a one-step shifted copy of $a$. This explains the output by superposition, with every index included.
\Image[/discrete-convolution-sums.png]
{title=Discrete convolution combines index pairs, shifted copies, polynomial coefficients and outcome counts}
The same products appear in <polynomial> multiplication and <generating functions>:
$$
(1+2z+z^2)(1+z)=1+3z+3z^2+z^3.
$$
A term $a_mz^m$ times $b_kz^k$ contributes to coefficient $m+k$, precisely the index condition in <discrete convolution>. In probability, $a$ counts the outcomes of two independent fair coin tosses by their number of heads, while $b$ counts the outcomes of one more toss. Dividing the output by eight gives the <probability mass function> $(1,3,3,1)/8$ of the <binomial distribution> with $n=3$ and $p=1/2$. No new arithmetic is needed to pass from coefficient multiplication to counting independent sums.
The full finite <convolution> is different from <circular convolution>, where indices wrap modulo a chosen length. Wrapping this four-term output to length three adds its last entry to its first and gives $(2,3,3)$. When using a <discrete Fourier transform> to compute the full <convolution>, <zero padding> to length at least the sum of the input lengths minus one prevents this wraparound. https://ocw.mit.edu/courses/res-6-008-digital-signal-processing-spring-2011/610905d8154ec2bfc090cf78022249a5_MITRES_6_008S11_lec10.pdf[Oppenheim, MIT Digital Signal Processing, Lecture 10, circular convolution and zero padding]{ref}
Back to article page
