Convolution

Ritu Ann Roy George Rahul Anand Ravi Yadav Rahul Chaudhary
B170106EC B170518EC B170556EC B170912EC
B-Batch B-Batch B-Batch B-Batch
NIT Calicut NIT Calicut NIT Calicut NIT Calicut

Abstract—This objective of this experiment is to study con- The tails that do not correspond to the circular convolu-
volution and various digital signal processing techniques for tion are added to the adjoining tail of the previous and
the operation. Further an image is convolved to study the subsequent sequence. This addition results in the aliasing
transformation effects that can be achieved by convolution.
that occurs in circular convolution.
I. CONVOLUTION
Convolution, one of the most important concepts in elec- II. AIM
trical engineering, can be used to determine the output signal
of a linear time invariant system for a given input signal with
knowledge of the system’s unit impulse response. A. Question I
The operation of discrete time convolution is defined such
that it performs this function for infinite length discrete time To generate the signal x[n] = {11101234}.
signals and systems. The operation of discrete time circular Write a function to compute linear convolution with system
convolution is defined such that it performs this function for impulse response h[n] = {1211}. given by
finite length and periodic discrete time signals.
In each case, the output of the system is the convolution or ∞
X
circular convolution of the input signal with the unit impulse h[n − k]x[k]
response. Discrete convolution can be performed with the k=−∞
impulse response h[n] and the input signal x[n] as:
∞
X Verify your result with that obtained from in-built function in
x[n] ∗ h[n] = h[n − k]x[k] MATLAB.
k=−∞

A long input sequence is segmented to fixed size blocks,

prior to FIR filter processing. Two methods are used to B. Question II
evaluate the discrete convolution Overlap-save method and
Overlap-add method. To use the above program to find the step response of an
LTI system given the impulse response. (Take h[n] = {1234}.
• Overlap-Save Also compute the response of the same system to a rectangular
The overlap-save procedure cuts the signal up into equal pulse, exponential signal and a sinusoidal signal.b) To express
length segments with some overlap. Then it takes the DFT the above as a 3-bit digital signal. Sample at fs3 = 15kHz
of the segments and saves the parts of the convolution .Plot the sampled signal (use ’stem’) over the original analog
that correspond to the circular convolution. Because there signal.
are overlapping sections, it is like the input is copied
therefore there is not lost information in throwing away
parts of the linear convolution. C. Question III

• Overlap-Add To read an image and resize it to 32x32. Then convert it

The overlap-add procedure cuts the signal up into equal into a row vector of length 1x1024. Apply the filter given by
length segments with no overlap. Then it zeropads the h[n] = { 13 , 13 , 13 } on the long row vector by making use of
segments and takes the DFT of the segments. Part of the overlap-add and overlap-save approach. Re-arrange the output
convolution result corresponds to the circular convolution. sequence to image format.
 III. OBSERVATIONS AND INFERENCES

A. Question I

Fig. 3. Response to Linear Convolution with Step Funtion as Input

Fig. 1. Linear Convolution

From the Linear Convolution of input x[n] = {11101234}.

with the system impulse response h[n] = {1211}., it is
inferred that both the manual convolution and the convolution
function have given the same result.The convolution result is
obtained as y[n] = {134213811914}..

B. Question II

Fig. 4. Response to Linear Convolution with Rectangular Pulse as Input

Fig. 2. Response to Linear Convolution with Step Funtion as Input Fig. 5. Response to Linear Convolution with Exponential Signal as Input
 This is then converted back to the matrix format. Here, the
matrix format must be transposed in order to get the same
orientation as of the original image.
IV. CODES
A. Question I

1 %Exp2_Q1
2 %Linear Convolution
3
4
5 lx = -3; ux = 4;lh = -1; uh = 2;
6 ly = lx+lh; uy = ux+uh;
7
8 nx = -3:4; nh = -1:2;
9 ny = ly:uy; l = length(ny);
10
11 x = [1 1 1 0 1 2 3 4];
12 h = [1 2 1 -1];
13 X=zeros(1,l);
Fig. 6. Response to Linear Convolution with Sinusoidal Signal as Input 14 H=zeros(1,l);
15 y1=zeros(1,l);
16 X(1:length(x))=x;
Here we have taken a part of the total input signal for the 17 H(1:length(h))=h;
discrete convolution. With signals like sinusoids, it is inferred 18 for i=1:l
19 y1(i)=0;
that there is a need for convolving large input signals with 20 for j=1:i
comparatively smaller impulse sequence, which is provided 21 y1(i)=y1(i)+X(j)*H(i-j+1);
by methods such as overlap save and overlap add. 22 end
23 end
24
25 y2=conv(x,h);
C. Question III 26
27 subplot(4,1,1);
28 stem(nx,x,'k');
29 ylabel('Amplitude->');xlabel('N->');
30 title('Input sequence x');
31 axis([-5 7 -1 5]); grid on;
32 subplot(4,1,2);
33 stem(nh,h,'k');
34 ylabel('Amplitude->');xlabel('N->');
35 title('System Reponse h');
36 axis([-5 7 -1 5]); grid on;
37 subplot(4,1,3);
38 stem(ny,y1,'k');
39 ylabel('Amplitude->');xlabel('N->');
40 title('Response Obtained Using user defined ...
function');
41 axis([-5 7 -5 15]); grid on;
42 subplot(4,1,4);
43 stem(ny,y2,'k');
44 ylabel('Amplitude->');xlabel('N->');
45 title('Response Obtained Using using inbuilt ...
function');
46 axis([-5 7 -5 15]); grid on;

B. Question II
Fig. 7. Image Transformation using Overlap Add and Overlap Save Methods

1 %Exp2_Q2_a Linear Convolution with Step Sequence

The image is initially converted from RGB to grayscale to 2 lx = -3; ux = 4;lh = -1; uh = 2;
provide for a 2D matrix format. Then the image is resized and 3 ly = lx+lh; uy = ux+uh;
reshaped. 4 nx = -3:4; nh = 0:3;
5 ny = ly:uy; l = length(ny);
Once made into a 1D array, convolution operation is performed 6
on it to obtain the smoothening characteristics for the given 7 x = [0 0 0 1 1 1 1 1];
figure. Here the impulse response h acts as a low pass filter 8 h = [1 2 3 4];
9 X=zeros(1,l);
which averages and hence smoothens out the image during the 10 H=zeros(1,l);
convolution. 11 y1=zeros(1,l);
12 X(1:length(x))=x; 40 ylabel('Amplitude->');xlabel('N->');
13 H(1:length(h))=h; 41 title('Verification: using inbuilt function');
14 for i=1:l 42 axis([-5 7 -5 15]); grid on;
15 y1(i)=0;
16 for j=1:i
17 y1(i)=y1(i)+X(j)*H(i-j+1);
18 end 1 %Exp2_Q2_c Linear Convolution with ...
19 end exponential signal
20 2 lx = -3; ux = 5;lh = -1; uh = 2;
21 y2=conv(x,h); 3 ly = lx+lh; uy = ux+uh;
22 4 nx = -3:5; nh = 0:3;
23 subplot(4,1,1); 5 ny = ly:uy; l = length(ny);
24 stem(nx,x,'k'); 6 x1 = [-3 -2 -1 0 1 2 3 4 5];
25 ylabel('Amplitude->');xlabel('N->'); 7 x = exp(x1/2);
26 title('Input x = Step Function'); 8 h = [1 2 3 4];
27 axis([-5 7 -1 5]); grid on; 9 X=zeros(1,l);
28 subplot(4,1,2); 10 H=zeros(1,l);
29 stem(nh,h,'k'); 11 y1=zeros(1,l);
30 ylabel('Amplitude->');xlabel('N->'); 12 X(1:length(x))=x;
31 title('Impulse Function h'); 13 H(1:length(h))=h;
32 axis([-5 7 -1 5]); grid on; 14 for i=1:l
33 subplot(4,1,3); 15 y1(i)=0;
34 stem(ny,y1,'k'); 16 for j=1:i
35 ylabel('Amplitude->');xlabel('N->'); 17 y1(i)=y1(i)+X(j)*H(i-j+1);
36 title('Result after Convolution'); 18 end
37 axis([-5 7 -5 15]); grid on; 19 end
38 subplot(4,1,4); 20
39 stem(ny,y2,'k'); 21 y2=conv(x,h);
40 ylabel('Amplitude->');xlabel('N->'); 22
41 title('Verification: using inbuilt function'); 23 subplot(4,1,1);
42 axis([-5 7 -5 15]); grid on; 24 stem(nx,x,'k');
25 ylabel('Amplitude->');xlabel('N->');
26 title('Input x = exponential signal'); grid on;
27 subplot(4,1,2);
1 %Exp2_Q2_b Linear Convolution with ... 28 stem(nh,h,'k');
Rectangular pulse 29 ylabel('Amplitude->');xlabel('N->');
2 lx = -3; ux = 5;lh = -1; uh = 2; 30 title('Impulse Function h');grid on;
3 ly = lx+lh; uy = ux+uh; 31 subplot(4,1,3);
4 nx = -3:5; nh = 0:3; 32 stem(ny,y1,'k');
5 ny = ly:uy; l = length(ny); 33 ylabel('Amplitude->');xlabel('N->');grid on;
6 34 title('Result after Convolution');
7 x = [0 0 0 1 1 1 0 0 0 ]; 35 subplot(4,1,4);
8 h = [1 2 3 4]; 36 stem(ny,y2,'k');
9 X=zeros(1,l); 37 ylabel('Amplitude->');xlabel('N->');grid on;
10 H=zeros(1,l); 38 title('Verification: using inbuilt function');
11 y1=zeros(1,l);
12 X(1:length(x))=x;
13 H(1:length(h))=h;
14 for i=1:l 1 %Exp2_Q2_d Linear Convolution with ...
15 y1(i)=0; sinusoidal signal
16 for j=1:i 2 lx = -5; ux = 15;lh = -1; uh = 2;
17 y1(i)=y1(i)+X(j)*H(i-j+1); 3 ly = lx+lh; uy = ux+uh;
18 end 4 nx = -5:15; nh = 0:3;
19 end 5 ny = ly:uy; l = length(ny);
20 6 x = sin(2*pi/10.*nx);
21 y2=conv(x,h); 7 h = [1 2 3 4];
22 8 X=zeros(1,l);
23 subplot(4,1,1); 9 H=zeros(1,l);
24 stem(nx,x,'k'); 10 y1=zeros(1,l);
25 ylabel('Amplitude->');xlabel('N->'); 11 X(1:length(x))=x;
26 title('Input x = Rectangular pulse'); 12 H(1:length(h))=h;
27 axis([-5 7 -1 5]); grid on; 13 for i=1:l
28 subplot(4,1,2); 14 y1(i)=0;
29 stem(nh,h,'k'); 15 for j=1:i
30 ylabel('Amplitude->');xlabel('N->'); 16 y1(i)=y1(i)+X(j)*H(i-j+1);
31 title('Impulse Function h'); 17 end
32 axis([-5 7 -1 5]); grid on; 18 end
33 subplot(4,1,3); 19
34 stem(ny,y1,'k'); 20 y2=conv(x,h);
35 ylabel('Amplitude->');xlabel('N->'); 21
36 title('Result after Convolution'); 22 subplot(4,1,1);
37 axis([-5 7 -5 15]); grid on; 23 stem(nx,x,'k');
38 subplot(4,1,4); 24 ylabel('Amplitude->');xlabel('N->');
39 stem(ny,y2,'k'); 25 title('Input x = sinusoidal signal'); grid on;
26 subplot(4,1,2); 58 X=[X(1:(stage-1)*L) Z Y(M:M+L-1)];
27 stem(nh,h,'k'); 59 index=stage*L+1:(stage+1)*L;
28 ylabel('Amplitude->');xlabel('N->'); 60 end
29 title('Impulse Function h');grid on; 61
30 subplot(4,1,3); 62 i=1:N1+M-1;
31 stem(ny,y1,'k'); 63 X=X(i);
32 ylabel('Amplitude->');xlabel('N->');grid on; 64 Q=vec2mat(X,32);
33 title('Result after Convolution'); 65 R=mat2gray(Q);
34 subplot(4,1,4); 66 imshow(transpose(R));
35 stem(ny,y2,'k'); 67 title('Using Overlap Add Method');
36 ylabel('Amplitude->');xlabel('N->');grid on; 68
37 title('Verification: using inbuilt function'); 69 function Y = circonv(x,h)
70 m=length(x);n=length(h);N=max(m,n);
71 x=[x,zeros(1,N-m)];h=[h,zeros(1,N-n)];
C. Question III 72 for n=1:N
73 Y(n)=0;
74 for i=1:N
1 %Exp2_Q3 Image Modification 75 j=n-i+1;
2
76 if(j≤0)
3 I=imread('Lenna.png'); 77 j=N+j;
4 BB = rgb2gray(I); 78 end
5 J=imresize(BB,[32 32]); 79 Y(n)=[Y(n)+x(i)*h(j)];
6 subplot(2,2,1); 80 end
7 imshow(I);title('Original Image'); 81 end
8 subplot(2,2,2); 82 end
9 imshow(J);title('ResizedImage');
10 K=reshape(J,[1 1024]);
11
V. RESULT
12 x=K; A. Question I
13 h=[1/3 1/3 1/3];
14 L=3; Linear convolution is performed and the result is verified
15 N1=length(x); with MATLAB inbuilt function.
16 M=length(h);
17 x=[x zeros(1,mod(-N1,L))];
18 N2=length(x);
B. Question II
19 h=[h zeros(1,L-1)]; Convolution is performed for various input signals. The
20 H=fft(h,L+M-1);
21 S=N2/L;
convolved output is plotted against the output of the inbuilt
22 index=1:L; conv function to verify the output.
23
24 subplot(2,2,3); C. Question III
25 %Overlap Save Method
26 x=[x zeros(1,mod(-N1,L)) zeros(1,L)]; Image transformation is performed on the image named
27 xm=x(index); Lena. The image is smoothened using two techniques Overlap
28 x1=[zeros(1,M-1) xm]; Add and Save to yield same results in each case.
29 X=[];
30 for stage=1:S
31 Y=circonv(x1,h);
32 index2=M:M+L-1;
33 Y=Y(index2);
34 X=[X Y];
35 index3=(((stage)*L)-M+2):((stage+1)*L);
36 if(index3(L+M-1)≤N2)
37 x1=x(index3);
38 end
39 end
40
41 i=1:N1+M-1;
42 X=X(i);
43
44 i=1:N1+M-1;
45 X=X(i);
46 Q=vec2mat(X,32);
47 R=mat2gray(Q);
48 imshow(transpose(R));
49 title('Using Overlap Save Method');
50
51 %Overlap Add Method
52 subplot(2,2,4);
53 X=[zeros(M-1)];
54 for stage=1:S
55 xm=[x(index) zeros(1,M-1)];
56 Y=circonv(xm,h);
57 Z=X((length(X)-M+2):length(X))+Y(1:M-1);