Overlap-save method

From Wikipedia, the free encyclopedia

Overlap-save is the traditional name for an efficient way to evaluate the discrete convolution between a very long signal $x [n]$ with a finite impulse response (FIR) filter $h [n]$ :

$\begin{align} y[n] = x[n] * h[n] \ \stackrel{\mathrm{def}}{=} \ \sum_{m=-\infty}^{\infty} h[m] \cdot x[n-m] = \sum_{m=1}^{M} h[m] \cdot x[n-m], \end{align}$

where h[m]=0 for m outside the region [1, M].

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:

$x_k[n] \ \stackrel{\mathrm{def}}{=} \begin{cases} x[n+kL] & 1 \le n \le L+M-1\\ 0 & \textrm{otherwise}. \end{cases}$

$y_k[n] \ \stackrel{\mathrm{def}}{=} \ x_k[n]*h[n]\,$

Then, for kL + M ≤ n ≤ kL + L + M − 1, and equivalently M ≤ n − kL ≤ L + M − 1, we can write:

$\begin{align} y[n] = \sum_{m=1}^{M} h[m] \cdot x_k[n-kL-m] &= x_k[n-kL] * h[n] \\ &\stackrel{\mathrm{def}}{=} \ y_k[n-kL]. \end{align}$

The task is thereby reduced to computing y_k[n], for M ≤ n ≤ L + M − 1.

Now note that if we periodically extend x_k[n] with period N ≥ L + M − 1, according to:

$x_{k,N}[n] \ \stackrel{\mathrm{def}}{=} \ \sum_{k=-\infty}^{\infty} x_k[n - kN],$

the convolutions $(x_{k,N})*h\,$ and $x_k*h\,$ are equivalent in the region M ≤ n ≤ L + M − 1. So it is sufficient to compute the $N\,$ -point circular (or cyclic) convolution of $x_k[n]\,$ with $h[n]\,$ in the region [1, N]. The subregion [M, L + M − 1] is appended to the output stream, and the other values are discarded.

The advantage is that the circular convolution can be computed very efficiently as follows, according to the circular convolution theorem:

$y_k[n] = \textrm{IFFT}\left(\textrm{FFT}\left(x_k[n]\right)\cdot\textrm{FFT}\left(h[n]\right)\right),$

where FFT and IFFT refer to the fast Fourier transform and inverse fast Fourier transform, respectively, evaluated over N discrete points.

[edit] Pseudocode

   (Overlap-save algorithm for linear convolution)
   H = FFT(h,N)
   i = 1
   while i <= Nx
       il = min(i+N-1,Nx)
       yt = IFFT( FFT(x(i:il),N) * H, N)
       y(i : i+N-L-1) = yt(1+L : N)
       i = i+L
   end

[edit] Overlap-discard

Overlap-discard is a less commonly used label for the same method described here. But it actually does a better job of distinguishing the method from overlap-add which overlaps the output segments and therefore also "saves", but does not discard. "Save" merely refers to the fact that M − 1 input (or output) samples from segment k are needed to process segment k + 1.

[edit] References

Rabiner, Lawrence R.; Gold, Bernard (1975). Theory and application of digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall, pp 65-67. ISBN 0-13-914101-4.