Segmented folding

The segmented convolution (English overlap add , OA , OLA ) is a method for fast convolution and is used in digital signal processing . An input sequence is broken down into partial sequences that do not overlap one another. These segments are filled with zeros, from which the DFT (or FFT ) is then formed. The result forms part of the output sequence , in whose composition the overlapping areas - in contrast to the overlap save method - are added. The aim of this method is to convert the cyclic convolution operation of the fast Fourier transform used for fast convolution into the aperiodic convolution operation. In the case of segmented convolution, in contrast to the overlap save method, principle-related signal propagation times can occur which are in the range of the duration of a block for fast Fourier transformation.

In the applications, segmented convolution is used to efficiently implement higher-order FIR filters . In contrast to the direct implementation of the aperiodic convolution operation in digital signal processors (DSP), the segmented convolution has the advantage of saving resources such as memory or computing time.

Procedure

function

Graphic representation of the fast folding using segmented folding

The direct execution of the aperiodic convolution operation between an arbitrarily long input sequence x [n] and the impulse response h [n] of length M results in the output sequence y [n]:

${\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 h [m] is set equal to 0 outside the interval [1, M]. This fast folding technique is based on the following idea:

• The infinitely long input signal is divided into short sections of length L , which are given the index k below to distinguish them.
• Since the result of the folding of a portion of the length L with a function of the length M L + M may be values length equal to 0 and is lost no information on the result, each of the sections with M padded zeros (this is also called zero-padding designated ) to bring the result of the convolution operation to length L + M : ${\displaystyle x_{k}}$

${\displaystyle x_{k}[n]\ {\stackrel {\mathrm {def} }{=}}{\begin{cases}x[n+kL]&n=1,2,\ldots ,L\\0&{\textrm {ansonsten}}\end{cases}}}$

• Now the results of the individual convolution are added where the individual convolution products overlap, and the result of this operation corresponds to the convolution of the infinitely long input sequence.

Mathematical description

The input sequence x [n] consists of the sum of the partial sequences x _k [n]

${\displaystyle x[n]=\sum _{k}x_{k}[n-kL]}$ ,

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

${\displaystyle {\begin{aligned}y[n]=\left(\sum _{k}x_{k}[n-kL]\right)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL]\end{aligned}}}$

The initial partial sequences

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

are zero outside the interval [1, L + M-1]. For each value of the parameter N , which must be selected greater than or equal to L + M -1, the circular convolution operation of the output sequence results. The individual output sequences y _k [k] overlapped in the intervals [k (L + 1), k (L + M)], and the output sequence y [k] is formed by the summation .

Advantages of this procedure

The advantage is that the circular convolution operation for forming the partial sequences y _k can be efficiently implemented in the form of the fast Fourier transformation (FFT) or the inverse fast Fourier transformation (IFFT) in the following form:

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

Depending on the FFT algorithm used, it makes sense to coordinate the specific block length N for calculating the circular partial folds. When using the FFT algorithm according to Cooley and Tukey ( Radix-2 algorithm ), it is beneficial to choose the block length as a power of two:

${\displaystyle N=L+M=2^{p},\quad p\in \mathbb {N} }$

Pseudocode

Depending on the FFT algorithm N, Lselect and .

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    (die überlappenden Bereiche addieren)
    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 .
• Steven W. Smith: The Scientist and Engineer's Guide to Digital Signal Processing . Elsevier Ltd., Oxford 2002, ISBN 978-0-7506-7444-7 , chap. 18 (English, dspguide.com ).

Web links

• www.dspguide.com/ch18/2.htm