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
Cite As
Sourangsu Banerji (2024). Overlap Add Method using Circular Convolution Technique (https://www.mathworks.com/matlabcentral/fileexchange/41173-overlap-add-method-using-circular-convolution-technique), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
- Signal Processing > Signal Processing Toolbox > Transforms, Correlation, and Modeling > Transforms > Discrete Fourier and Cosine Transforms > Fast Fourier Transforms >
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.