Code covered by the BSD License  

Highlights from
Overlap Add Method using Circular Convolution Technique

Be the first to rate this file! 25 Downloads (last 30 days) File Size: 3.03 KB File ID: #41173
image thumbnail

Overlap Add Method using Circular Convolution Technique

by

 

08 Apr 2013 (Updated )

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

| Watch this File

File Information
Description

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

Required Products MATLAB
MATLAB release MATLAB 7.14 (R2012a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Updates
09 Apr 2013

Fixed some errors in the generated graph.

11 Apr 2013

Fixed some errors.

Contact us