Editing Discrete Fourier transform (section)

===Circular convolution theorem and cross-correlation theorem===
{{Main|Convolution theorem#Functions of a discrete variable (sequences)}}

The [[DTFT#Convolution|convolution theorem]] for the [[discrete-time Fourier transform]] (DTFT) indicates that a convolution of two sequences can be obtained as the inverse transform of the product of the individual transforms. An important simplification occurs when one of sequences is N-periodic, denoted here by <math>y_{_N},</math> because <math>\scriptstyle \text{DTFT} \displaystyle \{y_{_N}\}</math> is non-zero at only discrete frequencies (see {{slink|DTFT#Periodic_data}}), and therefore so is its product with the continuous function <math>\scriptstyle \text{DTFT} \displaystyle \{x\}.</math>&nbsp; That leads to a considerable simplification of the inverse transform.

:<math>x * y_{_N}\ =\ \scriptstyle{\rm DTFT}^{-1} \displaystyle \left[\scriptstyle{\rm DTFT} \displaystyle \{x\}\cdot \scriptstyle{\rm DTFT} \displaystyle \{y_{_N}\}\right]\ =\ \scriptstyle{\rm DFT}^{-1} \displaystyle \left[\scriptstyle{\rm DFT} \displaystyle \{x_{_N}\}\cdot \scriptstyle{\rm DFT} \displaystyle \{y_{_N}\}\right],</math>

where <math>x_{_N}</math> is a [[periodic summation]] of the <math>x</math> sequence''':''' <math>(x_{_N})_n\ \triangleq \sum_{m=-\infty}^{\infty} x_{(n-mN)}.</math>

Customarily, the DFT and inverse DFT summations are taken over the domain <math>[0,N-1]</math>. Defining those DFTs as <math>X</math> and <math>Y</math>, the result is''':'''

:<math>
(x * y_{_N})_n \triangleq \sum_{\ell=-\infty}^{\infty}x_\ell \cdot (y_{_N})_{n-\ell} = \underbrace{\mathcal{F}^{-1}}_{\rm DFT^{-1}} \left \{ X\cdot Y \right \}_n.</math>

In practice, the <math>x</math> sequence is usually length ''N'' or less, and <math>y_{_N}</math> is a periodic extension of an N-length <math>y</math>-sequence, which can also be expressed as a ''circular function''''':'''

:<math>(y_{_N})_n = \sum_{p=-\infty}^\infty y_{(n-pN)} = y_{(n\operatorname{mod}N)}, \quad n\in\mathbb{Z}.</math>
Then the convolution can be written as''':'''

{{Equation box 1|title=
|indent =: |cellpadding= 6 |border |border colour = #0073CF |background colour=#F5FFFA
|equation =
:<math>
\mathcal{F}^{-1} \left \{ X\cdot Y \right \}_n = \sum_{\ell=0}^{N-1}x_\ell \cdot y_{_{(n-\ell)\operatorname{mod}N}}
</math>
}}

which gives rise to the interpretation as a ''circular'' convolution of <math>x</math> and <math>y.</math><ref name=Oppenheim/><ref name=McGillem/> It is often used to efficiently compute their linear convolution. (see [[Circular convolution#Example|Circular convolution]], [[Convolution#Fast convolution algorithms|Fast convolution algorithms]], and [[Overlap-save method|Overlap-save]])

Similarly, the [[cross-correlation]] of <math>x</math> and <math>y_{_N}</math> is given by''':'''

:<math>(x \star y_{_N})_n \triangleq \sum_{\ell=-\infty}^{\infty} x_\ell^* \cdot (y_{_N})_{n+\ell} = \mathcal{F}^{-1} \left \{ X^* \cdot Y \right \}_n.</math>