Overlap Add Method using Circular Convolution Technique

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

Circular convolution with the overlap–add method:

When sequence x[n] is periodic, and Nx 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 ≤ Nx, 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 ≤ Nx will represent the desired convolution.
The modified pseudo-code 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

Please note: The "mycirconv" function should be in the same path directory with the main Overlap_Add_Method.m file