Overlap–add method

The segmented folding (English overlap add, OA, OLA ) is a method for fast convolution, and is used in digital signal processing. In this case, an input sequence is decomposed into non-overlapping sub-sequences. These segments are filled with zeros, one of which then the DFT (or FFT) is formed. The result forms a part of the output sequence, the overlapping areas in the composition - are added - in contrast to the Overlap -Save method. The objective of this procedure is to convert the cyclic convolution of the fast convolution used for fast Fourier transform in the non-periodic convolution. Wherein the segmented folding can, in contrast to the overlap-save method, operating principle, signal delays occur which are within the duration of a block fast Fourier transform.

In the applications, the segmented folding for efficient implementation of FIR filters of higher order will be used. The segmented folding has when trying to save as opposed to the direct implementation of the aperiodic convolution operation in digital signal processors ( DSP), the advantage of resources such as memory or processor time.

Method

Function

Direct execution of aperiodic convolution between an arbitrarily long input sequence x [n ] and the impulse response h [n ] of length M produces the output sequence y [n]:

Where h [m ] outside the interval [1, M] is equal to 0. This method for fast convolution based on the following idea:

  • The infinitely long input signal is divided into short sections of length L, which are provided in the following, the index k to distinguish.
  • As the result of the convolution of a portion of the length L with a function of the length M L M values ​​may be equal to 0, and there shall lose no information on the result, each of the portions M zeros is filled (this is also known as zero padding ) to get the result of the convolution operation to the length L M
  • Now the results of the individual folds are added where overlap each convolution products, and the result of this operation corresponds to the convolution of the infinitely long input sequence.

Mathematical Description

The input sequence x [n] is the sum of the partial sequences xk [n]

Which the output sequence y [ n] can be represented as the sum of individual folds:

The output subsequences

Are outside the interval [ 1, L M -1] is zero. For each value of the parameter N, which must be greater than or equal chosen as L M-1, the result is the circular convolution of the output sequence. The individual output sequences yk [k ] overlapped in the intervals [k (L 1), k ( L M) ], and by summing the output sequence y [ k] is formed.

Advantages of this method

The advantage is that the circular convolution operation for the formation of the partial sequences in the form y k efficient Fast Fourier Transform (FFT ) and inverse fast Fourier transform (IFFT) may be implemented according to the following form:

Depending on the FFT algorithm used, it is useful to match the actual block length N for calculating the circular portion folds. When using the FFT algorithm by Cooley and Tukey ( radix-2 algorithm), it is convenient to choose the block length as a power of two:

Pseudocode

Depending on the FFT algorithm N and L choose.      H = FFT (H, N)      i = 1      while i < = Nx          il = min ( i L-1, Nx)          yt = IFFT (FFT (x ( i: il ), N ) * H, N)          k = min ( i N-1, Nx)          y (i: k) = y (i: k) YT ( ​​the overlapping portions add )          i = i L      end literature

  • Karl -Dirk Kammeyer, Kristian Kroschel: Digital Signal Processing. 6th edition. Teubner, 2006, ISBN 3-8351-0072-6.
  • Steven W. Smith, Ph.D.: The Scientist and Engineer 's Guide to Digital Signal Processing. 1 edition. Elsevier Ltd., Oxford, 2002, ISBN 978-0750674447, 18 ( http://www.dspguide.com ).
Convolution#Fast convolution algorithms Discrete Fourier transform Overlap–save method Transmission delay
628018
de