Block Convolution using Overlap Add Method

Overlap Add Method:

The overlap–add method is an efficient way to evaluate the discrete convolution of a very long signal with a finite impulse response (FIR) filter where h[m] = 0 for m outside the region [1, M].The concept here is to divide the problem into multiple convolutions of h[n] with short segments of x[n], where L is an arbitrary segment length. Because of this y[n] can be written as a sum of short convolutions.

Algorithm:

The signal is first partitioned into non-overlapping sequences, then the discrete Fourier transforms of the sequences are evaluated by multiplying the FFT xk[n] of with the FFT of h[n]. After recovering of yk[n] by inverse FFT, the resulting output signal is reconstructed by overlapping and adding the yk[n]. 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 pseudo-code 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

Note: The following method uses the block convolution algorithm to compute the convolution