Overlap–add method

In signal processing, the overlap–add method (OA, OLA) is an efficient way to evaluate the discrete convolution of a very long signal x [ n ] {displaystyle x} with a finite impulse response (FIR) filter h [ n ] {displaystyle h} : y k [ n ] = IFFT ( FFT ( x k [ n ] ) ⋅ FFT ( h [ n ] ) ) {displaystyle y_{k}={ extrm {IFFT}}left({ extrm {FFT}}left(x_{k} ight)cdot { extrm {FFT}}left(h ight) ight)}     (Eq.1) In signal processing, the overlap–add method (OA, OLA) is an efficient way to evaluate the discrete convolution of a very long signal x [ n ] {displaystyle x} with a finite impulse response (FIR) filter h [ n ] {displaystyle h} : where h = 0 for m outside the region . The concept is to divide the problem into multiple convolutions of h with short segments of x [ n ] {displaystyle x} : where L is an arbitrary segment length. Then: and y can be written as a sum of short convolutions: where   y k [ n ]   = d e f   x k [ n ] ∗ h [ n ] {displaystyle y_{k} {stackrel {mathrm {def} }{=}} x_{k}*h,}   is zero outside the region .  And for any parameter   N ≥ L + M − 1 , {displaystyle Ngeq L+M-1,,}   it is equivalent to the N {displaystyle N,} -point circular convolution of x k [ n ] {displaystyle x_{k},} with h [ n ] {displaystyle h,}   in the region . The advantage is that the circular convolution can be computed very efficiently as follows, according to the circular convolution theorem: where FFT and IFFT refer to the fast Fourier transform and inversefast Fourier transform, respectively, evaluated over N {displaystyle N} discretepoints. Fig. 1 sketches the idea of the overlap–add method. Thesignal x [ n ] {displaystyle x} is first partitioned into non-overlapping sequences,then the discrete Fourier transforms of the sequences y k [ n ] {displaystyle y_{k}} are evaluated by multiplying the FFT of x k [ n ] {displaystyle x_{k}} with the FFT of h [ n ] {displaystyle h} . After recovering of y k [ n ] {displaystyle y_{k}} by inverse FFT, the resultingoutput signal is reconstructed by overlapping and adding the y k [ n ] {displaystyle y_{k}} as shown in the figure. The overlap arises from the fact that a linearconvolution is always longer than the original sequences. In the early days of development of the fast Fourier transform, L {displaystyle L} was often chosen to be a power of 2 for efficiency, but further development has revealed efficient transforms for larger prime factorizations of L, reducing computational sensitivity to this parameter. A pseudocode of the algorithm is thefollowing: