Discrete convolution ( $(a * b)_{n} = \sum_{m \in 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 Z} a_{m} b_{n - m} .

(1)

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 $(1, 3, 3, 1)$ at indices

0, 1, 2, 3

c_{0} = 1 \cdot 1 = 1, c_{1} = 1 \cdot 1 + 2 \cdot 1 = 3, c_{2} = 2 \cdot 1 + 1 \cdot 1 = 3, c_{3} = 1 \cdot 1 = 1.

(2)

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.

Figure 1.
Discrete convolution combines index pairs, shifted copies, polynomial coefficients and outcome counts
. **Details**.

The same products appear in polynomial multiplication and generating functions:

(1 + 2 z + z^{2}) (1 + z) = 1 + 3 z + 3 z^{2} + z^{3} .

(3)

A term

a_{m} z^{m}

times

b_{k} z^{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. ^[ref]

Table of contents

XOR convolution

 0  0

For arrays indexed by

b

-bit nonnegative integers, their XOR convolution is

(a *_{\oplus} c)_{r} = \sum_{i} a_{i} c_{i \oplus r}

, where

\oplus

is bitwise exclusive or. If entries count choices of Grundy numbers, its repeated application counts sums of impartial games with a specified combined Grundy number. The Hadamard transform turns this operation into pointwise multiplication.

Cyclic convolution ( $a *_{k} b$ )

 0  0

For arrays

a, b

indexed by integers modulo

k

, their cyclic convolution is

(a *_{k} b)_{r} = \sum_{i = 0}^{k - 1} a_{i} b_{(r - i) mod k} .

(1)

When

a_{i}

and

b_{j}

count choices with respective residue classes

i

and

j

, the cyclic convolution counts pairs whose sum has residue class

r

. Repeated cyclic convolution therefore counts sums of longer sequences. The discrete Fourier transform converts cyclic convolution into pointwise multiplication.

Circular convolution ( $(a *_{N} b)_{n} = \sum_{m = 0}^{N - 1} a_{m} b_{(n - m) mod N}$ )

 1  0

Circular convolution of two length-

N

sequences uses modular arithmetic for their indices. Extending both inputs periodically gives the displayed formula. Equivalently, fold a finite discrete convolution into residue classes modulo

N

by adding entries whose indices are congruent. The discrete Fourier transform of the circular convolution is the product of the two discrete Fourier transforms, with the usual unnormalized forward transform and