# 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.