Be the first to rate this file! 15 Downloads (last 30 days) File Size: 2.28 KB File ID: #41338
image thumbnail

Block Convolution using Overlap Add Method

by

 

Performs block convolution using the Overlap Add Method.

| 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

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

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.

Contact us