Overlap–save method

The overlap-save method is 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{aligned}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],\quad (1)\end{aligned}}

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\leq n\leq 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{aligned}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{aligned}}

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 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.

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

References

Rabiner, Lawrence R.; Gold, Bernard (1975). Theory and application of digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall. pp. pp 65-67. ISBN 0-13-914101-4. {{cite book}}: |pages= has extra text (help); Cite has empty unknown parameter: |coauthors= (help)CS1 maint: multiple names: authors list (link)

Pseudocode

See also

References