Scribd
Upload
258 views

Overlap Add Save

The document discusses fast convolution using overlap-add and overlap-save methods for linear time-invariant systems. It describes that these block convolution techniques can be used to find the response of long sequences more efficiently than using the discrete Fourier transform. The overlap-add method partitions the input signal into blocks and overlaps and adds the filtered blocks, while the overlap-save method overlaps and saves the filtered blocks without adding. Examples are provided to illustrate both methods.

Uploaded by

Shailendra B
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
258 views

Overlap Add Save

The document discusses fast convolution using overlap-add and overlap-save methods for linear time-invariant systems. It describes that these block convolution techniques can be used to find the response of long sequences more efficiently than using the discrete Fourier transform. The overlap-add method partitions the input signal into blocks and overlaps and adds the filtered blocks, while the overlap-save method overlaps and saves the filtered blocks without adding. Examples are provided to illustrate both methods.

Uploaded by

Shailendra B
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

Digital Signal Processing

Module 8
Fast Convolution using Overlap add and Save method
Objective:

To understand and apply the overlap add and overlap save methods to find the response of LSI
systems.

Introduction:
Inspite of its computational advantages, there are some difficulties with the DFT
approach for finding linear convolution. For example, if x(n) is very long, we must commit a
significant amount of time computing very long DFTs and in the process accept very long
processing delays. In some cases, it may even be possible that x(n) is too long to compute the
DFT. The solution to these problems is to use block convolution, which involves segmenting
the signal to be filtered, x(n), into sections. Each section is then filtered with the FIR filter
h(n), and the filtered sections are pieced together to form the sequence y(n). There are two
block convolution techniques. The first is overlap-add, and the second is overlap-save.

Description:
Overlap Save Method:
Figure 8.1. Illustration of Overlap-save method of block convolution
Overlap Add Method:
Figure 8.2. Partitioning a sequence into subsequences of length M for the overlap-add method of block
convolution

Illustrative Examples:

Problem 1: Find the output y(n) of a filter whose impulse response is h(n)={1,1,1} and input
signal x(n)={3,-1,0,1,3,2,0,1,2,1}using
i) Overlap - save method
ii) Overlap - add method

Solution:
Summary:
Therefore for long duration sequences the response of an LSI system can be found by using
block convolution known as fast convolution using overlap - add and overlap - save methods
faster than the methods using DFT and IDFT.

Assignment:

Problem 1: Find the output y(n) of a filter whose impulse response is h(n)={1,2} and input
signal x(n)={1,2,-1,2,3,-2,-3,-1,1,1,2,-1}using
i) Overlap - save method
ii) Overlap - add method
Simulation:
%Overlap – Add method
clear
clc
x=input('enter x:');
h=input('enter h:');
subplot(3,1,1);
stem(0:length(x)-1,x);
xlabel('n---->');
ylabel('x(n)--->');
title('Input sequence');
subplot(3,1,2);
stem(0:length(h)-1,h);
xlabel('n---->');
ylabel('h(n)--->');
title('Impulse response sequence');
display('The fast convolution result using overlap-add method is:')
y=fftfilt(h,x)
subplot(3,1,3);
stem(0:length(y)-1,y);
xlabel('n---->');
ylabel('y(n)--->');
title('Fast Convolution using Overlap-Add method');
Input:
enter x:[3,-1,0,1,3,2,0,1,2,1]
enter h:[1 1 1]
Output:
The fast convolution result using overlap-add method is:
y= 3 2 2 0 4 6 5 3 3 4

References:
1. Digital Signal Processing, Principles, Algorithms and Applications – John G Proakis, Dimitris G Manolakis,
Pearson Education / PHI, 2007
2. Discrete Time Signal Processing – A V Oppenheim and R W Schaffer, PHI, 2009
3. Digital Signal Processing – Monson H.Hayes – Schaum’s Outlines, McGraw-Hill,1999
4. Fundamentals of Digital Signal Processing using Matlab – Robert J Schilling, Sandra L Harris, Thomson
2007.
5. Digital Signal processing – A Practical Approach, Emmanuel C Ifeachor and Barrie W Jervis, 2 nd Edition, PE
2009

6. Digital Signal Processing – A Computer Based Approach, Sanjit K.Mitra, McGraw Hill,2nd Edition, 2001

You might also like