Overlap save process

The overlap save method is a fast convolution method . In contrast to the overlap-add method, the input sequence x [n] is broken down into overlapping partial sequences. From the periodic convolution products formed (cyclic convolution) those components are then taken that correspond to the aperiodic, fast convolution. The overlap-save method is used in applications, for example, for the efficient implementation of higher-order FIR filters .

General

The following relationship exists between an input sequence x [n] and the impulse response h [n] formed only by zeros and the output sequence y [n] formed :

${\displaystyle 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]}$

where outside the interval [1, M ] the values ​​of h [m] are equal to 0.

The signal sequence x [n] generally has a significantly greater length than the length of the impulse response h [n]. Due to the fact that the impulse response h [n] has no poles, h [n] can also be interpreted as the transfer function of an FIR filter .

The output signal y [n], which arises from the convolution of two finite signals, can generally be divided into three parts. Transient behavior, stationary behavior and decay behavior. With the overlap save method, the input signal is broken down into segments and each segment is individually folded by means of cyclic convolution with a filter. The partial folds are then reassembled, the decay area of ​​each of these partial folds now overlapping the next one and thereby interfering with it. Therefore, this decay area, which leads to an incorrect result, is discarded in the context of the method. The individual stationary parts of the individual folds now butt directly against one another and thus deliver the correct result of the fold.

Procedure

The principle is to calculate short sections of y [n] with any length L and then to string these sections together. For a sub-segment that starts at n = kL  +  M , k is an integer, the following applies:

${\displaystyle x_{k}[n]\ {\stackrel {\mathrm {def} }{=}}{\begin{cases}x[n+kL]&M\leq n\leq M+L-1\\0&{\textrm {ansonsten}}.\end{cases}}}$

${\displaystyle y_{k}[n]\ {\stackrel {\mathrm {def} }{=}}\ x_{k}[n]*h[n]\,}$

With these partial sequences we get in the interval kL  +  M  ≤  n  ≤  kL  +  L  +  M  - 1, or equivalently in the interval M  ≤  n  -  kL  ≤  L  +  M  - 1, for y [n]:

${\displaystyle {\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}}}$

For the calculation of y _k [ n ] is the interval M  ≤  n  ≤  L  +  M  - 1 is sufficient.

For the periodic continuation x _{k, N} [ n ] of x _k [ n ] with the period N  ≥  L  +  M  - 1:

${\displaystyle x_{k,N}[n]\ {\stackrel {\mathrm {def} }{=}}\ \sum _{k=-\infty }^{\infty }x_{k}[n-kN],}$

the convolution of   and     in the interval M  ≤  n  ≤  L  +  M  - 1 is equivalent. Therefore it is sufficient to circularly fold N elements of x _k [n] with h [n] in the interval [1,  N ]. The subsection [ M ,  L  +  M  - 1] is added to the output sequence, all other values ​​are discarded. ${\displaystyle (x_{k,N})*h\,}$ ${\displaystyle x_{k}*h\,}$

The advantage of this method is that a circular convolution operation can be implemented with the aid of the fast Fourier transformation (FFT) and the inverse fast Fourier transformation (IFFT) with a drastically reduced effort:

${\displaystyle y_{k}[n]={\textrm {IFFT}}\left({\textrm {FFT}}\left(x_{k}[n]\right)\cdot {\textrm {FFT}}\left(h[n]\right)\right)}$

For details, see the quick fold article .

Pseudocode

H = FFT(h,N)
i = 1
Nx = length(x)
while i <= Nx
    il = min(i+N-1,Nx)
    yt = IFFT( FFT(x(i:il),N) * H, N)
    y(i : i+N-M) = yt(M : N)
    i = i+L
end

literature

• Karl-Dirk Kammeyer, Kristian Kroschel: Digital signal processing . 6th edition. Teubner, 2006, ISBN 3-8351-0072-6 .
• Alan V. Oppenheim, Ronald W. Schafer: Discrete-time signal processing . 3. Edition. R.Oldenbourg, 1999, ISBN 3-486-24145-1 .

Web links

• Fast Convolution - Efficient computation of convolution using FFTs (in English)