Overlap–save method

In signal processing, overlap–save is the traditional name for an efficient way to evaluate the discrete convolution between a very long signal x [ n ] {\displaystyle x[n]} and a finite impulse response (FIR) filter h [ n ] {\displaystyle h[n]} :

where h[m] = 0 for m outside the region [1, M]. This article uses common abstract notations, such as y ( t ) = x ( t ) ∗ h ( t ) , {\textstyle y(t)=x(t)*h(t),} or y ( t ) = H { x ( t ) } , {\textstyle y(t)={\mathcal {H}}\{x(t)\},} in which it is understood that the functions should be thought of in their totality, rather than at specific instants t {\textstyle t} (see Convolution#Notation).

The concept is to compute short segments of y[n] of an arbitrary length L, and concatenate the segments together. That requires longer input segments that overlap the next input segment. The overlapped data gets "saved" and used a second time. First we describe that process with just conventional convolution for each output segment. Then we describe how to replace that convolution with a more efficient method. Consider a segment that begins at n = kL + M, for any integer k, and define:

x k [ n ] ≜ { x [ n + k L ] , 1 ≤ n ≤ L + M − 1 0 , otherwise . {\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {otherwise}}.\end{cases}}}

y k [ n ] ≜ x k [ n ] ∗ h [ n ] = ∑ m = 1 M h [ m ] ⋅ x k [ n − m ] . {\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-m].}

Then, for k L + M + 1 ≤ n ≤ k L + L + M {\displaystyle kL+M+1\leq n\leq kL+L+M} , and equivalently M + 1 ≤ n − k L ≤ L + M {\displaystyle M+1\leq n-kL\leq L+M} , we can write:

y [ n ] = ∑ m = 1 M h [ m ] ⋅ x k [ n − k L − m ] ≜ y k [ n − k L ] . {\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].}

With the substitution j = n − k L {\displaystyle j=n-kL} , the task is reduced to computing y k [ j ] {\displaystyle y_{k}[j]} for M + 1 ≤ j ≤ L + M {\displaystyle M+1\leq j\leq L+M} . 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 ≤ j ≤ L. If we periodically extend xk[n] with period N ≥ L + M − 1, according to:

x k , N [ n ] ≜ ∑ ℓ = − ∞ ∞ x k [ n − ℓ N ] , {\displaystyle x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],}

… excerpt ends here. Continue reading the full article.