Editing Convolution (section)

=== Circular discrete convolution ===
When a function <math>g_{_N}</math> is periodic, with period <math>N,</math> then for functions, <math>f,</math> such that <math>f*g_{_N}</math> exists, the convolution is also periodic and identical to''':'''

:<math>(f * g_{_N})[n] \equiv \sum_{m=0}^{N-1} \left(\sum_{k=-\infty}^\infty {f}[m + kN]\right) g_{_N}[n - m].</math>

The summation on <math>k</math> is called a [[periodic summation]] of the function <math>f.</math>

If <math>g_{_N}</math> is a periodic summation of another function, <math>g,</math> then <math>f*g_{_N}</math> is known as a [[circular convolution]] of <math>f</math> and <math>g.</math>

When the non-zero durations of both <math>f</math> and <math>g</math> are limited to the interval <math>[0,N-1],</math>&nbsp; <math>f*g_{_N}</math> reduces to these common forms''':'''

{{Equation box 1|title=
|indent=: |cellpadding= 0 |border= 0 |background colour=white
|equation={{NumBlk2|
|<math>\begin{align}
 \left(f * g_N\right)[n] &= \sum_{m=0}^{N-1} f[m]g_N[n - m] \\
 &= \sum_{m=0}^n f[m]g[n - m] + \sum_{m=n+1}^{N-1} f[m]g[N + n - m] \\[2pt]
 &= \sum_{m=0}^{N-1} f[m]g[(n - m)_\bmod{N}] \\[2pt]
 &\triangleq \left(f *_N g\right)[n]
\end{align}</math> &nbsp; &nbsp; &nbsp; &nbsp;
|Eq.1}}}}

The notation <math>f *_N g</math> for ''cyclic convolution'' denotes convolution over the [[cyclic group]] of [[modular arithmetic|integers modulo {{math|''N''}}]].

Circular convolution arises most often in the context of fast convolution with a [[fast Fourier transform]] (FFT) algorithm.