Linear and Circular Convolution | MATLAB Tutorial

Convolution is a mathematical process that relates the output of a LTI system to its input and impulse response.

where ‘*’ represents commutative convolution operation. Lets see what is Linear and Circular Convolution.

Linear Convolution:

It takes two functions of an independent variable and convolves them using the convolutions formula. It is a correlation of one function with the time-reversed version of the other function. Linear convolution refers to the convolution between infinitely supported sequences. The linear convolution of an N-point vector, x, and an L-point vector, y, has length N + L – 1.

Example:

  • Let us consider x(n)=[1 3 -2 1] and y(n)=[1 1 0 0] to find linear convolution. The best way to solve linear convolution is the tabular method format. We first write the sequences in first row and first column and then at each intersecting point we find the product and place it. Lastly we sum the diagonals and get the result of convolution.

Linear Convolution

So,
y1(0) = 1

y1(1) = 1+3 = 4

y1(2) = 0+3-2 = 1

y1(3) = 0+0-2+1= -1

y1(4) = 0+0+1 =1

y1(5) = 0+0 =0

y1(6) = 0

 

Thus x(n)*y(n)= y1(n)=[1 4 1 -1 1 0]. Also length of y1(n) is 7 obtained by equation N + L – 1, where ‘N’ is length of x(n) and ‘L’ is length of y(n) {Here 4+4-1 = 7}. We can write code for MATLAB and compare the theoretical answer.

MATLAB Code

xn=[1 3 -2 1];
yn=[1 1 0 0];
ans= conv(xn,yn)
n=1:8;
stemplot(ans,n)

Output:

ans =     1     4     1    -1     1     0     0

Linear Convolution
Figure 1

Circular Convolution:

Circular Convolution refers to the convolution between finitely supported and circularly extended sequences and filters. It is mathematically given as,

 

 

Mathematically also defined as,





Example:

  • Let us consider the same example x(n)=[1 3 -2 1] and y(n)=[1 1 0 0] to find circular convolution.
    [Note, we can compute circular convolution by- (a) Using Graphical Method (b) using Matrix Method (c) Using DFT, IDFT method. We shall be using DFT, IDFT method to compute the result]

The four point DFT of x(n) is X(k),

X(k)=[W4]. x(n) and

The four point DFT of y(n) is Y(n),

Y(k)=[W4].y(n)
where [W4] is called as twiddle factor and is given as [W4]=

Thus,

Matrix Form

Now according to the property of circular convolution,

Let Y1(n) = X(k).Y(k) = {3, 3-2j, -5, 3+2j}.{2, 1-j, 0, 1+j}= {6, 1-5j, 0, 1+5j}

Take inverse DFT of this sequence to get the result,

Matrix Form

Hence, y1(n)=[2 4 1 -1] and this is the required result of circular convolution.

MATLAB Code:

xn=[1 3 -2 1];
yn=[1 1 0 0];
X=fft(xn);
Y=fft(yn);
C=X.*Y;
y1=ifft(C);
n=1:4
stemplot(y1,n)

Output:

y1 =
     2     4     1    -1


Figure 2

Why the result of linear and circular convolution is not same?

Circular convolution contains same number of samples as that of input x(n) and h(n). Where as in linear convolution the number of samples increases and to get the length of result we use the equation N + L – 1. That’s why the result of linear and circular convolution doesn’t match.

How to obtain same result from linear and circular convolution?

  • Using the equation N + L – 1, calculate length; that means number of samples contained in linear convolution. Let us say it is 15.
  • By doing zero padding make the length of every sequence equal to 15. That means simply add zeros after the sequence to get a total sequence length of 15.
  • Perform circular Convolution. The result of Circular convolution and linear convolution should be same.

Let us try implementing this using MATLAB code, let us consider the same two sequences for which we got the result of linear convolution x(n)=[1 3 -2 1] and y(n)=[1 1 0 0]. Now according to the steps we find length of result sequence- 4+4-1=7. Next we zero pad the given sequence of length with 3 zeros at the end of each sequence to get total length of 7. Thus the new sequence would be xn=[1 3 -2 1 0 0 0] and yn=[1 1 0 0 0 0 0]. Let us write a code for this sequence.

MATLAB Code:

xn=[1 3 -2 1 0 0 0];
yn=[1 1 0 0 0 0 0];
X=fft(xn);Y=fft(yn);
C=X.*Y;
y1=ifft(C)
n=1:8;
stemplot(y1,n)

Output:
y1 =
    1.0000    4.0000    1.0000   -1.0000    1.0000         0    0.0000


Figure 3

We see the obtained result matches with the previous result of circular convolution.


Pursuing Bachelor's Degree in Electronics and Telecommunication Engineering from K. J. Somaiya Institute of Engineering and Information Technology, Mumbai University.

Comments

  1. […] Linear and Circular Convolution | MATLAB Tutorial […]

  2. […] Linear and Circular Convolution | MATLAB Tutorial […]

Comments are closed.