Overlap-add method

The overlap-add method (OA, OLA) is an efficient way to evaluate the discrete convolution between a very long signal $$x [n] with a finite impulse response (FIR) filter $$h [n] :

:$$egin{align}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] ,end{align}

where h [m] =0 for m outside the region [1, M] .

The concept is to divide the problem into multiple convolutions of h [n] with short segmentsof $$x [n] :

:$$x_k [n] stackrel{mathrm{def{=} egin{cases}x [n+kL] & n=1,2,ldots,L\\0 & extrm{otherwise},end{cases}

where L is an arbitrary segment length. Then:

:$$x [n] = sum_{k} x_k [n-kL] ,,

and y [n] can be written as a sum of short convolutions:

:$$egin{align}y [n] = left(sum_{k} x_k [n-kL] ight) * h [n] &= sum_{k} left(x_k [n-kL] * h [n] ight)\\&= sum_{k} y_k [n-kL] ,end{align}

where $$y_k [n] stackrel{mathrm{def{=} x_k [n] *h [n] , is zero outside the region [1,L+M-1] . And for any parameter $$Nge L+M-1,, it is equivalent to the $$N,-point circular convolution of $$x_k [n] , with $$h [n] , in the region [1,N] .

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 discretepoints.

The algorithm

Fig. 1 sketches the idea of the overlap-add method. Thesignal $$x [n] is first partitioned into non-overlapping sequences,then the discrete Fourier transforms of the sequences $$y_k [n] are evaluated by multiplying the FFT of $$x_k [n] with the FFT of$$h [n] . After recovering of $$y_k [n] by inverse FFT, the resultingoutput signal is reconstructed by overlapping and adding the $$y_k [n] as shown in the figure. The overlap arises from the fact that a linearconvolution is always longer than the original sequences. Note that$$L should be chosen to have $$N a power of 2 which makesthe FFT computation efficient. A pseudocode of the algorithm is thefollowing:

Algorithm 1 ("OA for linear convolution") Evaluate the best value of N and L H = FFT(h,N) ("zero-padded FFT") 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 ("add the overlapped output blocks") i = i+L end

Circular convolution with the overlap-add method

When sequence x [n] is periodic, and N_x is the period, then y [n] is also periodic, with the same period. To compute one period of y [n] , Algorithm 1 can first be used to convolve h [n] with just one period of x [n] . In the region M ≤ n ≤ N_x, the resultant y [n] sequence is correct. And if the next M-1 values are added to the first M-1 values, then the region 1 ≤ n ≤ N_x will represent the desired convolution. The modified pseudocode is:

Algorithm 2 ("OA for circular convolution") Evaluate Algorithm 1 y(1:M-1) = y(1:M-1) + y(Nx+1:Nx+M-1) y = y(1:Nx) end

Cost of the overlap-add method

The cost of the convolution can be associated to the number of complexmultiplications involved in the operation. The major computationaleffort is due to the FFT operation, which for a radix-2 algorithmapplied to a signal of length $$N roughly calls for $$C=frac{N}{2}log_2 Ncomplex multiplications. It turns out that the number of complex multiplicationsof the overlap-add method are:

:$$C_{OA}=leftlceil frac{N_x}{N-M+1} ight ceilNleft(log_2 N+1 ight),

$$C_{OA} accounts for the FFT+filter multiplication+IFFT operation.

The additional cost of the $$M_L sections involved in the circularversion of the overlap-add method is usually very small and can beneglected for the sake of simplicity. The best value of $$Ncan be found by numerical search of the minimum of $$C_{OA}left(N ight)=C_{OA}left(2^m ight)by spanning the integer $$m in the range $$log_2left(M ight)le mlelog_2 left(N_x ight).Being $$N a power of two, the FFTs of the overlap-add methodare computed efficiently. Once evaluated the value of $$N itturns out that the optimal partitioning of $$x [n] has $$L=N-M+1.For comparison, the cost of the standard circular convolution of $$x [n] and $$h [n] is:

:$$C_S=N_xleft(log_2 N_x+1 ight),

Hence the cost of the overlap-add method scales almost as $$Oleft(N_xlog_2 N ight)while the cost of the standard circular convolution method is almost$$Oleft(N_xlog_2 N_x ight). However such functions accountsonly for the cost of the complex multiplications, regardless of theother operations involved in the algorithm. A direct measure of thecomputational time required by the algorithms is of much interest.Fig. 2 shows the ratio of the measured time to evaluatea standard circular convolution using EquationNote|Eq.1 withthe time elapsed by the same convolution using the overlap-add methodin the form of Alg 2, vs. the sequence and the filter length. Both algorithms have been implemented under Matlab. Thebold line represent the boundary of the region where the overlap-addmethod is faster (ratio>1) than the standard circular convolution.Note that the overlap-add method in the tested cases can be threetimes faster than the standard method.

frame|none|Figure 2: Ratio between the time required by ">EquationNote|Eq.1 and the time required by the overlap-add Alg. 2 to evaluatea complex circular convolution, vs the sequence length $$N_x andthe filter length $$M.

See also

*Overlap-save method
*Weigthed Overlap Add (WOLA), an efficient filterbank method which uses FFT, that can be used to split a continuous signal stream into multiple equally-spaced subbands signal streams.

References

*Cite book
author=Rabiner, Lawrence R.; Gold, Bernard
authorlink=
coauthors=
title=Theory and application of digital signal processing
date=1975
publisher=Prentice-Hall
location=Englewood Cliffs, N.J.
isbn=0-13-914101-4
pages=pp 63-67
*Cite book
author=Oppenheim, Alan V.; Schafer, Ronald W.
authorlink=
coauthors=
title=Digital signal processing
date=1975
publisher=Prentice-Hall
location=Englewood Cliffs, N.J.
isbn=0-13-214635-5
pages=
*Cite book
author=Hayes, M. Horace
authorlink=
coauthors=
title = Digital Signal Processing
series = Schaum's Outline Series
date=1999
publisher=McGraw Hill
location=New York
isbn=0-07-027389-8
pages=

External links

* [http://www.mathworks.com Matlab] for the implementation of the overlap-add method through the function fftfilt.m.