Scribd
Upload
783 views36 pages

Convolution & IDFT Part 6 PDF

The document discusses various methods for computing the discrete Fourier transform (DFT) and discrete convolution, including: 1. Radix-2 DIT and DIF FFT algorithms for computing the DFT and inverse DFT. 2. Linear, circular, and linear convolution via circular convolution for computing the response of linear time-invariant systems. 3. Matrix and graphical methods for computing circular convolution.

Uploaded by

Abishek Rajesh
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
783 views36 pages

Convolution & IDFT Part 6 PDF

The document discusses various methods for computing the discrete Fourier transform (DFT) and discrete convolution, including: 1. Radix-2 DIT and DIF FFT algorithms for computing the DFT and inverse DFT. 2. Linear, circular, and linear convolution via circular convolution for computing the response of linear time-invariant systems. 3. Matrix and graphical methods for computing circular convolution.

Uploaded by

Abishek Rajesh
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/ 36

STEPS:

1. Take Conjugate of the given sequence X*(k)


2. Apply FFT algorithm ( DIT/DIF)
3. Take Conjugate of the output sequence from FFT
4. Divide the entire sequence by N

PROBLEMS:

1. Determine the IDFT of the sequence Y(k) ={ 16, -6-2j, 0, -6+2j} by


using radix-2 DIT-FFT algorithm
Additional Problem

Determine x(n) of the sequence X(k) ={10,4-2j,-2,4+2j} by radix-2 DIF-


FFT algorithm

Ans:

CONVOLUTION
Three types of convolution

1. Linear Convolution - Used to find the Response y(n) of the system


2. Circular convolution – Apply Shifting in circular fashion
3. Linear via Circular Convolution- Used to find the Response y(n) of the
system
4. Sectioned Convolution - Used to find the Response y(n) of the system

CIRCULAR CONVOLUTION PROPERTY OF DFT

1.
ANOTHER METHOD (MATRIX METHOD OF DFT)
2. In an LTI system the input x(n) = {1,2,1) and impulse response
h(n) = {1,3}. Determine the response of LTI system using
a) Radix-2 DIT-FFT b) DFT
Step 4: Take IDFT of Y(k)

Y*(k) = {16,-6+2j,0,-6-2j}

Take Bit-reversal of Y*(k) = {16,0,-6+2j,-6-2j}

Apply DIT-FFT ALGORITHM and Take Conjugate of the Output sequence we get

N y(n) = {4,20,28,12}

Divide by N, we get y(n) = {1,5,7,3}


CIRCULAR CONVOLUTION

Procedure:

1. Represent sequences on Circle ( Second sequence must follow


first one)
2. Apply Folding (Mirror image) on second sequence.
3. Apply Shifting on Second sequence towards the first sequence
(reference sequence) direction
4. Multiple First sequence with Shifted sequence
5. Add all the samples of Product sequence, we get the final
answer.

Two Approaches

a) Graphical Method b) Matrix method

1.

x1(n) = { 1,1,2,2} and x2(n) = {1,2,3,4}

LINEAR CONVOLUTION
CIRCULAR CONVOLUTION ( Graphical Method)
1. Represent Input sequences on the circle

2. Apply Folding operation on 3. Apply Shifting on x2(-n) with


x2(n) the second sequence ‘m’ values where shifting
parameter m = ( 0 -3 ) get
x2(m-n) and Multiply with
x1(n)
CIRCULAR CONVOLUTION (MATRIX METHOD)
1 2 2 1 1 15

1 1 2 2 2 = 17

2 1 1 2 3 15

2 2 1 1 4 13

Linear through Circular Convolution:

Problem:
Determine the response of the system whose input x(n) = ( 1,-2,3} and

h(n) = {5,-1} using a) Linear convolution b) Circular convolution(Linear thro


circular)
a) Use Tabular method
b) i) N1+N2-1 = 4 , ii) According this value make the length of x(n) & h(n)
x(n) ={1,-2,3,0} , h(n)= {5,-1,0,0}
iii) Perform Circular convolution using graphical (or) matrix method to get
response y(n)
TWO APPROACHES:

1. OVERLAP- ADD METHOD 2. OVERLAP-SAVE METHOD


1.

Ans:

y(n)= {-1,2,-3,4,-5,6,-7,8,-4}
2.
Additional Problems:

1.

ANS:

2.

ANS:

3.

ANS:
4.Compute Circular convolution of the following sequences

x1(n) = δ(n)+ δ(n-1)- δ(n-2)- δ(n-3) and

x2(n) = δ(n)- δ(n-2)- δ(n-4)


Given N=5

ANS:

You might also like