|
:<math>y[n] = \sum_{m=1}^{M} h[m] \cdot x_k[n-kL-m] \ \ \triangleq \ \ y_k[n-kL].</math>
TheWith the substitution {{math|j ≜ n-kL}}, the task is thereby reduced to computing ''{{math|y''<{{sub>''|k''</sub>[''n'']}}(j)}}, for '''''M''''' ≤ ''n''{{mvar|j}} ≤ '''''L'' +'' M'' − 1'''. The process described above is illustrated in the accompanying figure.
NowAlso note that if we periodically extend ''x''<sub>''k''</sub>[''n''] with period ''N'' ≥ ''L'' + ''M'' − 1, according to''':'''
:<math>x_{k,N}[n] \ \triangleq \ \sum_{\ell=-\infty}^{\infty} x_k[n - \ell N],</math>
the convolutions <math>(x_{k,N})*h\,</math> and <math>x_k*h\,</math> are equivalent in the region ''M'' ≤ ''n'' ≤ ''L'' + ''M'' − 1. So itIt is therefore sufficient to compute the '''N'''-point [[circular convolution|circular (or cyclic) convolution]] of <math>x_k[n]\,</math> with <math>h[n]\,</math> in the region [1, ''N'']. The subregion [''M'', ''L'' + ''M'' − 1] is appended to the output stream, and the other values are <u>discarded</u>. The advantage is that the circular convolution can be computed more efficiently than linear convolution, according to the [[Discrete Fourier transform#Circular convolution theorem and cross-correlation theorem|circular convolution theorem]]''':'''
The advantage is that the circular convolution can be computed very efficiently as follows, according to the [[Discrete Fourier transform#Circular convolution theorem and cross-correlation theorem|circular convolution theorem]]''':'''
:<math>y_k[n] = \scriptstyle \text{DFT}^{-1} \displaystyle (\ \scriptstyle \text{DFT} \displaystyle (x_k[n])\cdot \scriptstyle \text{DFT} \displaystyle (h[n])\ ),</math>
where''':'''
*DFT and DFT<sup>−1</sup> refer to the [[Discrete Fourier transform]] and its inverse Discrete Fourier transform, respectively, evaluated over ''N'' discrete points, and
*''N''{{math|L}} is customarily chosen tosuch bethat {{math|N {{=}} L+M-1}} is an integer power-of-2, which optimizesand the efficiencytransforms ofare implemented with the [[Fast Fourier transform|FFT]] algorithm, for efficiency.
**Optimal N is in the range [4M, 8M].
*Unlike*As shown in the figure (3rd trace), the leading and trailing edge-effects of convolution are overlapped and added{{efn-ua
|Not to be confused with the [[Overlap-add method]], which preserves separate leading and trailing edge-effects, this method causes them to be overlapped.
}} (and added. So they aresubsequently discarded together). In other words, with circular convolution, the first output value is a weighted average of the <u>last</u> M-1 samples of the input segment (and the first sample of the segment). The next M-2 outputs are weighted averages of both the beginning and the end of the segment. The M<sup>th</sup> output value is the first one that combines only samples from the beginning of the segment.
==Pseudocode==
| patent-number = 6898235
}}</li>
==Further reading==
*Rabiner, Lawrence R.; Gold, Bernard (1975). ''Theory and application of digital signal processing''. Englewood Cliffs, N.J.: Prentice-Hall. pp 65–67. {{ISBN|0139141014}}.
{{refend}}
| 