- Overlap-save method
**Overlap-save**is the traditional name for an efficient way to evaluate the discrete convolution between a very long signal $x\; [n]$ with afinite impulse response (FIR) filter $h\; [n]$**:**:$egin\{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\{=\}egin\{cases\}x\; [n+kL]\; 1\; le\; n\; le\; L+M-1\backslash 0\; extrm\{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

**:**:$egin\{align\}y\; [n]\; =\; sum\_\{m=1\}^\{M\}\; h\; [m]\; cdot\; x\_k\; [n-kL-m]\; =\; x\_k\; [n-kL]\; *\; h\; [n]\; \backslash 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]\; =\; extrm\{IFFT\}left(\; extrm\{FFT\}left(x\_k\; [n]\; ight)cdot\; extrm\{FFT\}left(h\; [n]\; ight)\; ight),$

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****Overlap-discard**"Overlap-discard" and "Overlap-scrap" are less commonly used labels for the same method described here. However, these labels are actually better (than "overlap-save") to distinguish from overlap-add, because

__both__methods "save", but only one discards. "Save" merely refers to the fact that "M" − 1 input (or output) samples from segment "k" are needed to process segment "k" + 1.**References***Cite book

author=Rabiner, Lawrence R.; Gold, Bernard

authorlink=

coauthors=

title=Theory and application of digital signal processing

date=1975

publisher=Prentice-Hall

location=Englewood Cliffs, N.J.

isbn=0-13-914101-4

pages=pp 65-67

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Overlap–save method**— Overlap–save is the traditional name for an efficient way to evaluate the discrete convolution between a very long signal x[n] and a finite impulse response (FIR) filter h[n] … Wikipedia**Overlap–add method**— The overlap–add method (OA, OLA) is an efficient way to evaluate the discrete convolution of a very long signal x[n] with a finite impulse response (FIR) filter h[n]: where h[m]=0 for m outside the region [1, M]. The concept is to divide the… … Wikipedia**Overlap-add method**— The overlap add method (OA, OLA) 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] ::egin{align}y [n] = x [n] * h [n] stackrel{mathrm{def{=} sum {m=… … Wikipedia**List of numerical analysis topics**— This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra … Wikipedia**Window function**— For the term used in SQL statements, see Window function (SQL) In signal processing, a window function (also known as an apodization function or tapering function[1]) is a mathematical function that is zero valued outside of some chosen interval … Wikipedia**List of mathematics articles (O)**— NOTOC O O minimal theory O Nan group O(n) Obelus Oberwolfach Prize Object of the mind Object theory Oblate spheroid Oblate spheroidal coordinates Oblique projection Oblique reflection Observability Observability Gramian Observable subgroup… … Wikipedia**Circular convolution**— The circular convolution, also known as cyclic convolution, of two aperiodic functions occurs when one of them is convolved in the normal way with a periodic summation of the other function. That situation arises in the context of the… … Wikipedia**Discrete Fourier transform**— Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… … Wikipedia**Dingo**— For other uses, see Dingo (disambiguation). Dingo Australian dingo Conservation status … Wikipedia**BIBLE**— THE CANON, TEXT, AND EDITIONS canon general titles the canon the significance of the canon the process of canonization contents and titles of the books the tripartite canon … Encyclopedia of Judaism