File Exchange

## Overlap Add Method using Circular Convolution Technique

version 1.2 (3.03 KB) by

Performs convolution using the Overlap Add Method with the Circular convolution.

Updated

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