|
:<math>y_k[n] \ \triangleq \ x_k[n]*h[n] = \sum_{m=1}^{M} h[m] \cdot x_k[n-m].</math>
Then, for <math>kL+M+1 \le n \le kL+L+M</math>, and equivalently <math>M+1 \le n-kL \le L+M</math>, we can write:
Then, for ''kL'' + ''M'' ≤ ''n'' ≤ ''kL'' + ''L'' + ''M'' − 1, and equivalently '''''M''''' ≤ ''n'' − ''kL'' ≤ '''''L'' + ''M'' − 1''', we can write''':'''
:<math>y[n] = \sum_{m=1}^{M} h[m] \cdot x_k[n-kL-m] \ \ \triangleq \ \ y_k[n-kL].</math>
With the substitution {{<math|>j ≜= n-kL}}</math>, the task is reduced to computing {{<math|y{{sub|k}}(>y_k[j)}},]</math> for '''''<math>M'''''+1 ≤ \le {{mvar|j}} \le ≤ '''''L'' +'' M'' − 1'''</math>. These steps are illustrated in the first 3 traces of Figure 1, except that the desired portion of the output (third trace) corresponds to '''''1''''' ≤ {{mvar|j}} ≤ '''''L''.{{efn-ua
|Shifting the undesirable edge effects to the last M-1 outputs is a potential run-time convenience, because the IDFT can be computed in the <math>y[n]</math> buffer, instead of being computed and copied. Then the edge effects can be overwritten by the next IDFT. A subsequent footnote explains how the shift is done, by a time-shift of the impulse response.}}
:<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 ''<math> M''+1 ≤ \le ''n'' ≤ \le ''L'' + ''M'' − 1 </math>. It 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'' + 1, ''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]]''':'''
{{NumBlk|:|<math>y_k[n]\ =\ \scriptstyle \text{IDFT}_N \displaystyle (\ \scriptstyle \text{DFT}_N \displaystyle (x_k[n])\cdot\ \scriptstyle \text{DFT}_N \displaystyle (h[n])\ ),</math>|{{EquationRef|Eq.2}}}}
| 