The overlap–add method is an efficient way to evaluate the discrete convolution

Convolution

In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...

 of a very long signal with a finite impulse response

Finite impulse response

A finite impulse response filter is a type of a signal processing filter whose impulse response is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response filters, which have internal feedback and may continue to respond indefinitely...

 (FIR) filter :


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 :


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 + M − 1].  And for any parameter    it is equivalent to the -point circular convolution

Circular convolution

The circular convolution, also known as cyclic convolution, of two aperiodic functions occurs when one of them is convolved in the normal way with a periodic summation of the other function.  That situation arises in the context of the Circular convolution theorem...

 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 discrete
points.

The algorithm

Fig. 1 sketches the idea of the overlap–add method. The
signal is first partitioned into non-overlapping sequences,
then the discrete Fourier transform

Discrete Fourier transform

In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...

s of the sequences
are evaluated by multiplying the FFT of with the FFT of
. After recovering of by inverse FFT, the resulting
output signal is reconstructed by overlapping and adding the
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, 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

Pseudocode

In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...

 of the algorithm is the
following:

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

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(N-M+1);
h=[h zeros(1,N-M)];
d=floor(Nx/L);
for j=0:d-1
k=1:L;
x1(k) = x(k+j*L);
x1=[x1 zeros(1,N-L)];
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 overlap-add 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 radix-2 algorithm
applied to a signal of length roughly calls for
complex multiplications. It turns out that the number of complex multiplications
of the overlap-add method are:


accounts for the FFT+filter multiplication+IFFT operation.

The additional cost of the 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
can be found by numerical search of the minimum of
by spanning the integer in the range .
Being a power of two, the FFTs of the overlap–add method
are computed efficiently. Once evaluated the value of it
turns out that the optimal partitioning of has .
For comparison, the cost of the standard circular convolution of
and 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   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

MATLAB

MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...

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