 Overlap–add method

The overlap–add method (OA, OLA) is an efficient way to evaluate the discrete convolution of a very long signal x[n] with a finite impulse response (FIR) filter h[n]:
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 segments of x[n]:
where L is an arbitrary segment length. Then:
and y[n] can be written as a sum of short convolutions:
where is zero outside the region [1,L+M1]. And for any parameter it is equivalent to the point circular convolution of with 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 inverse fast Fourier transform, respectively, evaluated over N discrete points.
Contents
The algorithm
Fig. 1 sketches the idea of the overlap–add method. The signal x[n] is first partitioned into nonoverlapping 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 resulting output signal is reconstructed by overlapping and adding the y_{k}[n] as shown in the figure. The overlap arises from the fact that a linear convolution is always longer than the original sequences. In the early days of development of the fast Fourier transform, 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 the following:
Algorithm 1 (OA for linear convolution) Evaluate the best value of N and L H = FFT(h,N) (zeropadded FFT) i = 1 while i <= Nx il = min(i+L1,Nx) yt = IFFT( FFT(x(i:il),N) * H, N) k = min(i+N1,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 M1 values are added to the first M1 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:M1) = y(1:M1) + y(Nx+1:Nx+M1) y = y(1:Nx) end
Linear convolution with overlap–add implemented in MATLAB or Octave
clc, close all, clear all; x=input('Enter the input sequence:'); h=input('Enter the impulse response:'); conv(x,h) N=input('Enter the length,N:'); x1=zeros(1,10); Nx=length(x); M=length(h); L=ceil(NM+1); h=[h zeros(1,NM)]; d=floor(Nx/L); for j=0:d1 k=1:L; x1(k) = x(k+j*L); x1=[x1 zeros(1,NL)]; r=1:j*L+1; z(j+1,r)=0; y=cconv(x1,h,N); t=1:N; z(j+1,t+j*L)=y(t); end for j=1:length(z) b(j)=0; for k=1:d b(j)=b(j)+z(k,j); end end disp(b);
Cost of the overlapadd method
The cost of the convolution can be associated to the number of complex multiplications involved in the operation. The major computational effort is due to the FFT operation, which for a radix2 algorithm applied to a signal of length N roughly calls for complex multiplications. It turns out that the number of complex multiplications of the overlapadd method are:
C_{OA} accounts for the FFT+filter multiplication+IFFT operation.
The additional cost of the M_{L} sections involved in the circular version of the overlap–add method is usually very small and can be neglected for the sake of simplicity. The best value of N can be found by numerical search of the minimum of by spanning the integer m in the range . Being N a power of two, the FFTs of the overlap–add method are computed efficiently. Once evaluated the value of N it turns 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:
Hence the cost of the overlap–add method scales almost as while the cost of the standard circular convolution method is almost . However such functions accounts only for the cost of the complex multiplications, regardless of the other operations involved in the algorithm. A direct measure of the computational time required by the algorithms is of much interest. Fig. 2 shows the ratio of the measured time to evaluate a standard circular convolution using Eq.1 with the time elapsed by the same convolution using the overlap–add method in the form of Alg 2, vs. the sequence and the filter length. Both algorithms have been implemented under Matlab. The bold line represent the boundary of the region where the overlap–add method is faster (ratio>1) than the standard circular convolution. Note that the overlap–add method in the tested cases can be three times faster than the standard method.
See also
References
 Rabiner, Lawrence R.; Gold, Bernard (1975). Theory and application of digital signal processing. Englewood Cliffs, N.J.: PrenticeHall. pp. 63–67. ISBN 0139141014.
 Oppenheim, Alan V.; Schafer, Ronald W. (1975). Digital signal processing. Englewood Cliffs, N.J.: PrenticeHall. ISBN 0132146355.
 Hayes, M. Horace (1999). Digital Signal Processing. Schaum's Outline Series. New York: McGraw Hill. ISBN 0070273898.
External links
Categories: 
Wikimedia Foundation. 2010.
Look at other dictionaries:
Overlapadd 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=… … Wikipedia
Overlap–save method — Overlap–save is the traditional name for an efficient way to evaluate the discrete convolution between a very long signal x[n] and a finite impulse response (FIR) filter h[n] … Wikipedia
Overlapsave method — Overlap save is the traditional name for 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=… … Wikipedia
Overlap — may mean one of: In music theory, overlap is a synonym for reinterpretation of a chord at the boundary of two musical phrases. In railway signalling, an Overlap (railway signalling) is the length of track beyond a stop signal that is proved to be … Wikipedia
Method of matched asymptotic expansions — In mathematics, particularly in solving singularly perturbed differential equations, the method of matched asymptotic expansions is a common approach to finding an accurate approximation to a problem s solution. Contents 1 Method overview 2… … Wikipedia
List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra … Wikipedia
List of mathematics articles (O) — NOTOC O O minimal theory O Nan group O(n) Obelus Oberwolfach Prize Object of the mind Object theory Oblate spheroid Oblate spheroidal coordinates Oblique projection Oblique reflection Observability Observability Gramian Observable subgroup… … Wikipedia
Audio timescalepitch modification — Time stretching is the process of changing the speed or duration of an audio signal without affecting its pitch.Pitch scaling or pitch shifting is the reverse: the process of changing the pitch without affecting the speed. There are also more… … Wikipedia
Timecompressed speech — is a technique used, often in advertising, to make recorded speech contain more words in a given time, yet still be understandable. Contents 1 History 2 Methods 3 Advantages 4 Disadvantages … Wikipedia
PSOLA — In digital signal processing techniques PSOLA stands for Pitch Synchronous Overlap Add Method.It is used in speech synthesis.ee alsoAudio timescale pitch modification.External links* [http://www.fon.hum.uva.nl/praat/manual/PSOLA.html PSOLA… … Wikipedia