= Circular convolution
{title2=$(a*_Nb)_n=\sum_{m=0}^{N-1}a_m b_{(n-m)\bmod N}$}
{wiki}
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 $1/N$ inverse convention.
Back to article page
