- Overlap-add method
The

**overlap-add method (OA, OLA)**is an efficient way to evaluate the discreteconvolution between a very long signal $x\; [n]$ with afinite 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\backslash \backslash 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)\backslash \backslash =\; 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 methodWhen 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\; N$complex 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 $N$can 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.**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.

*Wikimedia Foundation.
2010.*