circular convolution

Ciruclar convolution is defined as

\begin{equation} f[n] \circledast g[n] = \sum_{m = 0}^{N-1} a[m]*b[n-m (mod N)] \end{equation}

for \(n = 0..N\).

This operation is thus defined only on two sequences of equal length, \(N\).

Important result from the upper boundary of the sum: the reversed sequence begins at index zero and then starts reversed from \(N..1\)

This operation commutes

m 0 1 2 3
a(m) a(0) a(1) a(2) a(3)
b(0-m) b(0) b(3) b(2) b(1)
b(1-m) b(1) b(0) b(2) b(3)
b(2-m) b(2) b(1) b(0) b(3)
b(3-m) b(3) b(2) b(1) b(0)

This can clearly also be written in matrix form.

According to the convolution theorem, \(f \circledast g\) = \(F \cdot G\) where \(F\) and \(G\) are Fourier transforms of the original sequence. Thus, it can be computed fast with FFT.

The matrix that gives circular convolution is called a circulant matrix.

Back to index