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.