Overlap–save method

The overlap-save method is a method for quickly folding. In this case, in contrast to the overlap-add method, the input sequence x [n] is divided into overlapping sub-sequences. Then those shares will be removed from the formed periodic convolution products (cyclic convolution ), which correspond to the aperiodic fast convolution. The overlap-save method is used in the applications, for example for the efficient implementation of FIR filters of higher order.

General

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

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

The signal sequence x [n] generally has a substantially greater length than the length of the impulse response h [n]. By the fact that the impulse response h [n] does not have a pole, h [n] may also be regarded as the transfer function of a FIR filter.

The output signal y [ n], which results from the convolution of two finite signals may be generally divided into three parts. Transient, steady-state response and decay. In the overlap-save method the input signal is divided into segments and each segment individually folded by means of the cyclic convolution with a filter. Then the part folds are reassembled, the Ausschwingbereich each of these partial folds would now overlaps the subsequent and thus interfere. Therefore, this Ausschwingbereich, which leads to a wrong result, discarded during the procedure. It launched the single stationary parts of the individual folds now directly to each other and thereby provide the correct result of folding.

Method

The principle is to compute short sections of y [n] with an arbitrary length L, and then this series of sections together. For a sub-segment, which begins at n = kL M, k integer, the following applies:

With these subsequences n ≤ kL L M results in the interval kL M ≤ - 1, or equivalent to the interval M ≤ n - kL ≤ L M - 1, for y [ n]:

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

For the periodic continuation xk, N [ n] of xk [n ] with period N ≥ L M - 1:

Is the convolution of and in the interval M ≤ n ≤ L M - 1 equivalent. Therefore, it is sufficient, N elements of x k [n] to be folded with circularly h [n] is in the interval [ 1, N ]. The section [M, L M - 1] is appended to the output sequence, all other values ​​are rejected.

The advantage of this method is that a circular convolution operation using the fast Fourier transform (FFT) and inverse fast Fourier transform (IFFT) can be realized with a drastically reduced amount:

For details, see the article on Fast Convolution.

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.