circular convolution
Ciruclar convolution is defined as
f[n]⊛g[n]=N−1∑m=0a[m]∗b[n−m(modN)]
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⊛g = F⋅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.