Code covered by the BSD License

# Block Convolution using Overlap Save Method

### Sourangsu Banerji (view profile)

Performs block convolution using the Overlap Save Method.

OSM.m
% Theory
%
% Overlap Save Method
%
% In this method, the size of the input data blocks is N=L+M-1 and the DFTs and the IDFTs are of length L. Each Data Block consists of the
% last M-1 data points of the previous block followed by L new data points to form a data sequence of length N=L+M-1.An N point DFT  is computed
% for each data block. The impulse response of the FIR filter is increased in length by appending L-1 zeros and an N-point DFT of the sequence is
% computed once and stored. The multiplication of the N-point DFTs for the mth block of data yields
%                                                                    Ym(k)=h(k)Xm(k).
% Since the data record is of length N, the first M-1 points of Ym(n)are corrupted by aliasing and must be discarded. The last L points of Ym(n)
% are exactly the same as the result  from linear convolution. To avoid loss of data due to aliasing, the last M-1  points of each data record are
% saved and these points become the first M-1 data points of the subsequent record. To begin the processing, the first M-1 point of the first record
% is set to zero. The resulting data sequence from the IDFT are given where the first M-1 points are discarded due to aliasing and the remaining L
% points constitute the desired result from the linear convolution. This segmentation of the input data and the fitting of the output data blocks together
% form the output sequence.
%
% Note: The following method uses the block convolution algorithm to compute the convolution.
%
clc;
clear all;
x = input('Enter the sequence X(n) = ');
h = input('Enter the sequence H(n) = ');

% Code to perform Convolution using Overlap Save Method
n1 = length(x);
n2 = length(h);
N = n1+n2-1;
h1 = [h zeros(1,N-n1)];
n3 = length(h1);
y = zeros(1,N);
x1 = [zeros(1,n3-n2) x zeros(1,n3)];
H = fft(h1);
for i = 1:n2:N
y1 = x1(i:i+(2*(n3-n2)));
y2 = fft(y1);
y3 = y2.*H;
y4 = round(ifft(y3));
y(i:(i+n3-n2)) = y4(n2:n3);
end

% Code to plot X(n)
subplot(3,1,1);
stem(x(1:n1),'black');
grid on;
title('X(n)');
xlabel('n--->');
ylabel('Amplitude --->');

%Code to plot H(n)
subplot(3,1,2);
stem(h(1:n2),'red');
grid on;
title(' H(n)');
xlabel('n--->');
ylabel('Amplitude --->');

% Representation of the Convoled Signal
subplot(3,1,3);
disp(y(1:N));
stem(y(1:N));
grid on;
title('Convolved Signal');
xlabel('n--->');
ylabel('Amplitude --->');

% Add title to the Overall Plot
ha = axes ('Position',[0 0 1 1],'Xlim',[0 1],'Ylim',[0 1],'Box','off','Visible','off','Units','normalized', 'clipping' , 'off');
text (0.5, 1,'\bf Block Convolution using Overlap Save Method ','HorizontalAlignment','center','VerticalAlignment', 'top')