Content deleted Content added
m use \triangleq |
|||
Line 1:
'''Overlap–save''' is the traditional name for an efficient way to evaluate the [[Convolution#Discrete convolution|discrete convolution]] between a very long signal <math>x[n]</math> and a [[finite impulse response]] (FIR) filter <math>h[n]</math>''':'''
{{NumBlk|:|<math>y[n] = x[n] * h[n] \ \
where h[m]=0 for m outside the region [1, ''M''].
Line 8:
The concept is to compute short segments of ''y''[''n''] of an arbitrary length ''L'', and concatenate the segments together. Consider a segment that begins at ''n'' = ''kL'' + ''M'', for any integer ''k'', and define''':'''
:<math>x_k[n] \ \
\begin{cases}
x[n+kL] & 1 \le n \le L+M-1\\
Line 15:
</math>
:<math>y_k[n] \ \
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] \ \ \
The task is thereby reduced to computing ''y''<sub>''k''</sub>[''n''], for ''M'' ≤ ''n'' ≤ ''L'' +'' M'' − 1. The process described above is illustrated in the accompanying figure.
Line 25:
Now note that if we periodically extend ''x''<sub>''k''</sub>[''n''] with period ''N'' ≥ ''L'' + ''M'' − 1, according to''':'''
:<math>x_{k,N}[n] \ \
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 it is 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>.
| |||