Prepared by – R J Patil
Linear Vs Circular
Convolution
• Compute linear and circular convolution of following
x(n)={2,2,3,4}
h(n)={1,-1,3}
Linear convolution = {2 0 7 7 5 12}
Circular convolution = {7 12 7 7}
Note that the results of linear and circular
convolution are different. This is a problem! Why?
Prepared by – R J Patil
The Scenario : : : : :-----
• All LTI systems are based on the principle of linear convolution, as
the output of an LTI system is the linear convolution of the system
impulse response and the input to the system, which is equivalent to
the product of the respective DTFTs in the frequency domain.
• However, if we use DFT instead of DTFT (so that we can compute it
using a computer), then the result appear to be invalid:
Prepared by – R J Patil
The Scenario : : : : :-----
• DTFT is based on linear convolution, and DFT is based on circular
convolution, and they are not the same!!!
• They are not even of equal length: For two sequences of length N
and M, the linear convolution is of length N+M-1,
• Whereas circular convolution of the length max(N,M)
Prepared by – R J Patil
The Scenario : : : : :-----
• If we zero pad both sequences x[n] and h[n], so that they are both of
length N+M-1, then linear convolution and circular convolution result in
identical sequences
• If the respective DFTs of the zero padded sequences are X[k] and H[k],
then the inverse DFT of X[k]∙H[k] is equal to the linear convolution of
x[n] and h[n]
• Normally, the inverse DFT of X[k].H[k] is the circular convolution of x[n]
and h[n]. If they are zero padded, then the inverse DFT is also the linear
convolution of the two.
Prepared by – R J Patil
Conclusion……
• Basically Convolution is either Linear or Circular
• Only DFT deals with Circular convolution
• All other domains (Z, FS, DTFT) uses Linear Convolution
• Circular convolution is unavoidably and carefully used to
implement linear convolution using frequency domain
Prepared by – R J Patil
Circular Convolution – DFT formula method
Given Sequences : Use convolution property of DFT
x(n) = [ x(0) x(1) x(2) x(3) ]
y(n) = [ y(0) y(1) y(2) y(3) ] Step 1 : find DFT[x(n)] = X(k)
Step 2 : find DFT[y(n)] = Y(k)
Compute : Step 3 : compute Z(k) = X(k) Y(k)
z(n) = x(n) * y(n) Step 4 : find IDFT[Z(k)] = z(n)
Prepared by – R J Patil
Circular Convolution – Graphical Method
1st Step X(3)
Given Sequences :
x(n) = [ x(0) x(1) x(2) x(3) ]
y(n) = [ y(0) y(1) y(2) y(3) ]
y(1)
X(2) y(2) y(0) X(0)
Compute :
z(n) = x(n) * y(n)
y(3)
X(1) 1st Step Calculation :
z(1) = x(0)*y(0) + x(1)*y(3) + x(2)*y(2) + x(3)*y(1)
Prepared by – R J Patil
Circular Convolution – Graphical Method
2nd Step X(0)
y(1)
X(3) y(2) y(0) X(1)
y(3)
X(2) 2nd Step Calculation :
z(2) = x(0)*y(1) + x(1)*y(0) + x(2)*y(3) + x(3)*y(2)
Prepared by – R J Patil
Circular Convolution – Graphical Method
3rd Step X(1)
y(1)
X(0) y(2) y(0) X(2)
y(3)
X(3) 3rd Step Calculation :
z(2) = x(0)*y(2) + x(1)*y(1) + x(2)*y(0) + x(3)*y(3)
Prepared by – R J Patil
Circular Convolution – Graphical Method
4th Step X(2)
Output :
y(1) z(n) = x(n) * y(n)
X(1) y(2) y(0) X(3) z(n) = [ z(0) z(1) z(2) z(3) ]
y(3)
X(0) 4th Step Calculation :
z(3) = x(0)*y(3) + x(1)*y(2) + x(2)*y(1) + x(3)*y(0)
Prepared by – R J Patil
Circular Convolution – Matrix Method
Given Sequences : Compute :
x(n) = [ x(0) x(1) x(2) x(3) ] z(n) = x(n) * y(n)
y(n) = [ y(0) y(1) y(2) y(3) ]
x(0) x(3) x(2) x(1) y(0) z(0)
x(1) x(0) x(3) x(2) y(1) z(1)
z(n) = =
x(2) x(1) x(0) x(3) y(2) z(2)
x(3) x(2) x(1) x(0) y(3) z(3)
Prepared by – R J Patil
Difference between
Circular & Linear Convolution
Sr. No. Linear Convolution Circular Convolution
Length of input sequences can Length of input sequences
1 be different should be same
2 Zero padding is not required Zero padding required
Input sequences need not be Input sequences should be
3 periodic periodic
4 Output sequence is non periodic Output sequence is periodic
Length of output sequence is Length of output sequence is
5 greater than input sequences same as input sequences
Prepared by – R J Patil
About Linear Convolution
1. Consider two DT sequences x(n) & h(n) of length N1 & N2
2. Consider x(n)*h(n) = y(n) [linear convolution]
3. Then length of convolution y(n) is N1+N2-1
4. If x(n) starts at n=p & h(n) starts at n=q then y(n) starts at n=p+q
5. y(n) ends at n=(p+q)+(N1+N2-2)
Prepared by – R J Patil
Linear using Circular Convolution
1. Consider two sequences x(n) = [ -1 1 2 -2 ] & h(n) = [ 2 1 -1 2 0 ]
2. Lengths of x(n) = 4 & h(n) = 5
3. x(n) starts at n=0 & h(n) at n=-1 hence y(n) will start at n=0+(-1)=-1
4. y(n) will ends at n=(0+(-1))+(4+5-2) =6
5. Therefore
I. Both sequences should start at -1
II. Both sequence should ends at 6
III. Pad zeros for the same
IV. Length of input/output sequences will be (-1 to 6) = 8
6. Here
1. Y(n) = [-2 1 6 -5 -2 6 -4 0]
Prepared by – R J Patil
Sectioned Convolution
or Linear using Circular
--When one sequence is longer than other
Given Sequences : Compute :
x(n) = [ 0 1 2 1 -1 -2 -1 0 3 2 1 1 ] y(n) = x(n) * h(n)
h(n) = [ 1 1 1 ]
M = length of smaller sequence L = Consider any value
Here But
M=3 L ≥ M here L=3
Modify h(n) by zero padding But length of h(n) should be L+M-1
h(n) = [1 1 1 0 0 ]
Prepared by – R J Patil
Overlap – Save Method (Discard method )
x(n) = [ 0 1 2 1 -1 -2 -1 0 3 2 1 1 ]
Divide longer sequence into smaller parts, Such that
x1(n) = [ 0 0 0 1 2 ] * h(n) = [1 1 1 0 0 ] = y1(n)
M-1 L data points L+M-1 Zeros
Prepared by – R J Patil
Overlap – Save Method (Discard method )
x(n) = [ 0 1 2 1 -1 -2 -1 0 3 2 1 1 ]
Divide longer sequence into smaller parts, Such that
x2(n) = [ 1 2 1 -1 -2 ] * h(n) = [1 1 1 0 0 ] = y2(n)
M-1 L data points L+M-1 Zeros
Prepared by – R J Patil
Overlap – Save Method (Discard method )
x(n) = [ 0 1 2 1 -1 -2 -1 0 3 2 1 1 ]
Divide longer sequence into smaller parts, Such that
x3(n) = [ -1 -2 -1 0 3 ] * h(n) = [1 1 1 0 0 ] = y3(n)
M-1 L data points L+M-1 Zeros
Prepared by – R J Patil
Overlap – Save Method (Discard method )
x(n) = [ 0 1 2 1 -1 -2 -1 0 3 2 1 1 ]
Divide longer sequence into smaller parts, Such that
x3(n) = [ 0 3 2 1 1 ] * h(n) = [1 1 1 0 0 ] = y4(n)
M-1 L data points L+M-1 Zeros
Prepared by – R J Patil
Overlap – Save Method (Discard method )
y1(n) M-1
y2(n) M-1
y3(n) M-1
y4(n) M-1
y(n)
Prepared by – R J Patil
Overlap – Add Method
x(n) = [ 0 1 2 1 -1 -2 -1 0 3 2 1 1 ]
Divide longer sequence into smaller parts, Such that
x1(n) = [0 1 2 0 0 ] * h(n) = [1 1 1 0 0 ] = y1(n)
L data points M-1 L+M-1 Zeros
Prepared by – R J Patil
Overlap – Add Method
x(n) = [ 0 1 2 1 -1 -2 -1 0 3 2 1 1 ]
Divide longer sequence into smaller parts, Such that
x2(n) = [ 1 -1 -2 0 0 ] * h(n) = [1 1 1 0 0 ] = y2(n)
L data points L+M-1 Zeros
Prepared by – R J Patil
Overlap – Add Method
x(n) = [ 0 1 2 1 -1 -2 -1 0 3 2 1 1 ]
Divide longer sequence into smaller parts, Such that
x3(n) = [ -1 0 3 0 0 ] * h(n) = [1 1 1 0 0 ] = y3(n)
L data points L+M-1 Zeros
Prepared by – R J Patil
Overlap – Add Method
x(n) = [ 0 1 2 1 -1 -2 -1 0 3 2 1 1 ]
Divide longer sequence into smaller parts, Such that
x3(n) = [ 2 1 1 0 0 ] * h(n) = [1 1 1 0 0 ] = y4(n)
L data points L+M-1 Zeros
Prepared by – R J Patil
Overlap – Add Method
y1(n) M-1
y2(n) M-1
y3(n) M-1
y4(n) M-1
y(n)
Prepared by – R J Patil
Important MATLAB commands
• Consider two DT sequences a & b
• And n is modulo value with respect to length of a & b
1. Only linear convolution c = conv(a,b);
2. Only circular convolution c = cconv(a,b,n)
3. Linear using circular convolution c = cconv(a,b)