Smartworld.

asia 1

Digital Signal Processing 10EC52

SYLLABUS
SUBJECT CODE : 10EC52 IA MARKS : 25
NO. OF LECTURE HRS/WEEK : 04 EXAM HOURS : 03
TOTAL NO. OF LECTURE HRS. : 52 EXAMMARKS : 100

UNIT - 1
DISCRETE FOURIER TRANSFORMS (DFT): FREQUENCY DOMAIN SAMPLING AND
RECONSTRUCTION OF DISCRETE TIME SIGNALS. DFT AS A LINEAR TRANSFORMATION, ITS
RELATIONSHIP WITH OTHER TRANSFORMS. 6 HRS
UNIT - 2
PROPERTIES OF DFT, MULTIPLICATION OF TWO DFTS- THE CIRCULAR CONVOLUTION,
ADDITIONAL DFT PROPERTIES. 6 HRS

UNIT - 3
USE OF DFT IN LINEAR FILTERING, OVERLAP-SAVE AND OVERLAP-ADD METHOD. DIRECT
COMPUTATION OF DFT, NEED FOR EFFICIENT COMPUTATION OF THE DFT (FFT
ALGORITHMS). 7 HRS

UNIT - 4
RADIX-2 FFT ALGORITHM FOR THE COMPUTATION OF DFT AND IDFT–DECIMATIONIN-
TIME AND DECIMATION-IN-FREQUENCY ALGORITHMS. GOERTZEL ALGORITHM, AND CHIRP-Z
TRANSFORM. 7 HRS

UNIT - 5
IIR FILTER DESIGN: CHARACTERISTICS OF COMMONLY USED ANALOG FILTERS –
BUTTERWORTH AND CHEBYSHEVE FILTERS, ANALOG TO ANALOG FREQUENCY
TRANSFORMATIONS. 6 HRS

UNIT - 6
IMPLEMENTATION OF DISCRETE-TIME SYSTEMS: STRUCTURES FOR IIR AND FIR SYSTEMS
DIRECT FORM I AND DIRECT FORM II SYSTEMS, CASCADE, LATTICE AND PARALLEL
REALIZATION. 7 HRS

UNIT - 7
FIR FILTER DESIGN: INTRODUCTION TO FIR FILTERS, DESIGN OF FIR FILTERS USING -
RECTANGULAR, HAMMING, BARTLET AND KAISER WINDOWS, FIR FILTER DESIGN USING
FREQUENCY SAMPLING TECHNIQUE. 6 HRS
UNIT - 8
DESIGN OF IIR FILTERS FROM ANALOG FILTERS (BUTTERWORTH AND CHEBYSHEV) -
IMPULSE INVARIANCE METHOD. MAPPING OF TRANSFER FUNCTIONS: APPROXIMATION OF
DERIVATIVE (BACKWARD DIFFERENCE AND BILINEAR TRANSFORMATION) METHOD,
MATCHED Z TRANSFORMS, VERIFICATION FOR STABILITY AND LINEARITY DURING MAPPING
7 HRS

Dept., of ECE/SJBIT Page 1

Smartworld.asia 2

Digital Signal Processing 10EC52

TEXT BOOK:
1. DIGITAL SIGNAL PROCESSING – PRINCIPLES ALGORITHMS & APPLICATIONS, PROAKIS &
MONALAKIS, PEARSON EDUCATION, 4TH EDITION, NEW DELHI, 2007.

REFERENCE BOOKS:
1. DISCRETE TIME SIGNAL PROCESSING, OPPENHEIM & SCHAFFER, PHI, 2003.
2. DIGITAL SIGNAL PROCESSING, S. K. MITRA, TATA MC-GRAW HILL, 3RD EDITION, 2010.
3. DIGITAL SIGNAL PROCESSING, LEE TAN: ELSIVIER PUBLICATIONS, 2007

Dept., of ECE/SJBIT Page 2

Smartworld.asia 3

Digital Signal Processing 10EC52

INDEX SHEET

SL.NO TOPIC PAGE NO.

I Unit-1: Discrete Fourier Transforms 6-16
1.1 Frequency Domain Sampling
1.2 Reconstruction of Discrete time signals
1.3 DFT as a Linear Transform
1.4 DFT relationship with other transforms
II UNIT - 2 : Properties of DFT 18-26
2.1 Multiplication of two DFTs –Circular convolution
2.2 Additional DFT properties
2.3 Use of DFT in Linear Filtering
2.4 Overlap save and Overlap Add Method
2.5 Solution to Problems
III UNIT – 3 : Fast Fourier Transform Algorithms 27-35
3.1 Direct computation of DFT
3.2 Need for Efficient computation of DFT
3.2 FFT algorithms
UNIT – 4 : Radix-2 FFT Algorithms for DFT and
IV 39-60
IDFT
4.1 Decimation In Time Algorithms
4.2 Decimation-in-Frequency Algorithms
4.3 Goertzel Algorithms
4.4 Chirp-z-Transforms
V UNIT – 5 : IIR Filter Design 61-78
5.1 Characteristics of commonly used Analog Filters
5.2 Butterworth and Chebysheve Filters
5.3 Analog to Analog Frequency Transforms
5.4 Solution to problems
VI UNIT – 6 : FIR Filter Design 79-106
6.1 Introduction to FIR filters
Design of FIR Filters using Rectangular and Hamming
6.2
window
6.3 Design of FIR Filters using Bartlet and Hamming window
6.4 F IR filter design using frequency sampling technique
VII UNIT – 7 : Design of IIR Filters from Analog Filters 107-144
7.1 Impulse Invariance Method
7.2 Mapping of Transfer Functions
Approximation of derivative (Backward Difference and
7.3
Bilinear Transforms) method
7.4 Matched Z transforms
7.5 Verification for stability and Linearity during mapping
7.6 Solution to problems
VIII UNIT – 8 : Implementation of Discrete time systems 141-161

Dept., of ECE/SJBIT Page 3

Smartworld.asia 4

Digital Signal Processing 10EC52

8.1 Structure of IIR and FIR systems

8.2 Direct form I and direct form II Systems
8.3 Cascade Realization
8.4 Lattice Realization
8.5 Parallel Realization
8.6 Solution to problems

Dept., of ECE/SJBIT Page 4

Smartworld.asia 5

Digital Signal Processing 10EC52

UNIT 1

DISCRETE FOURIER TRANSFORMS (DFT)

CONTENTS:-

DISCRETE FOURIER TRANSFORMS (DFT): FREQUENCY DOMAIN SAMPLING AND

RECONSTRUCTION OF DISCRETE TIME SIGNALS. DFT AS A LINEAR TRANSFORMATION, ITS

RELATIONSHIP WITH OTHER TRANSFORMS. 6 HRS

RECOMMENDED READINGS

1. DIGITAL SIGNAL PROCESSING – PRINCIPLES ALGORITHMS & APPLICATIONS, PROAKIS &

MONALAKIS, PEARSON EDUCATION, 4TH EDITION, NEW DELHI, 2007.

2. DISCRETE TIME SIGNAL PROCESSING, OPPENHEIM & SCHAFFER, PHI, 2003.

3. DIGITAL SIGNAL PROCESSING, S. K. MITRA, TATA MC-GRAW HILL, 2ND EDITION, 2004.

Dept., of ECE/SJBIT Page 5

Smartworld.asia 6

Digital Signal Processing 10EC52

UNIT 1
Discrete Fourier Transform
1.1 Introduction:
Before we introduce the DFT we consider the sampling of the Fourier transform of an
aperiodic discrete-time sequence. Thus we establish the relation between the sampled Fourier
transform and the DFT.A discrete time system may be described by the convolution sum, the
Fourier representation and the z transform as seen in the previous chapter. If the signal is
periodic in the time domain DTFS representation can be used, in the frequency domain the
spectrum is discrete and periodic. If the signal is non-periodic or of finite duration the
frequency domain representation is periodic and continuous this is not convenient to
implement on the computer. Exploiting the periodicity property of DTFS representation the
finite duration sequence can also be represented in the frequency domain, which is referred to
as Discrete Fourier Transform DFT.
DFT is an important mathematical tool which can be used for the software
implementation of certain digital signal processing algorithms .DFT gives a method to
transform a given sequence to frequency domain and to represent the spectrum of the sequence
using only k frequency values, where k is an integer that takes N values, K=0, 1, 2,…..N-1.
The advantages of DFT are:
1. It is computationally convenient.
2. The DFT of a finite length sequence makes the frequency domain analysis much
simpler than continuous Fourier transform technique.

1.2 FREQUENCY DOMAIN SAMPLING AND RECONSTRUCTION OF DISCRETE

TIME SIGNALS:

Consider an aperiodic discrete time signal x (n) with Fourier transform, an aperiodic finite
energy signal has continuous spectra. For an aperiodic signal x[n] the spectrum is:


X w   xn e  jwn
………………………………(1.1)
n  

Dept., of ECE/SJBIT Page 6

Smartworld.asia 7

Digital Signal Processing 10EC52

Suppose we sample X[w] periodically in frequency at a sampling of w radians between

successive samples. We know that DTFT is periodic with 2, therefore only samples in the
fundamental frequency range will be necessary. For convenience we take N equidistant
2
samples in the interval (0<=w<2 ). The spacing between samples will be w  as shown
N
below in Fig.1.1.
X[w]

w
0  2

Fig 1.1 Frequency Domain Sampling

Let us first consider selection of N, or the number of samples in the frequency domain.
2k
If we evaluate equation (1) at w 
N
 2k  
X    xne  j 2kn / N k  0,1,2,......., ( N  1) ………………………. (1.2)
 N  n  
We can divide the summation in (1) into infinite number of summations where each sum
contains N terms.

 2k  1 N 1 2 N 1
X   .......   xn e  j 2kn / N
  xn e  j 2kn / N
  xne  j 2kn / N
 N  n N n 0 n N

 lN  N 1
   xne
l  n lN
 j 2kn / N

If we then change the index in the summation from n to n-l N and interchange the order of
summations we get:

Dept., of ECE/SJBIT Page 7

Smartworld.asia 8

Digital Signal Processing 10EC52

 2k  N 1     j 2kn / N
 N      xn  lN e for k  0,1,2,......, ( N  1) …….(1.3)
n  0 l   

Denote the quantity inside the bracket as xp[n]. This is the signal that is a repeating version of
x[n] every N samples. Since it is a periodic signal it can be represented by the Fourier series.

N 1
x p n   ck e j 2kn / N n  0,1,2,........, ( N  1)
k 0

With FS coefficients:

N 1

 x ne
1  j 2kn / N
ck  p k  0,1,2,......., ( N  1) …………… (1.4)
N n 0

Comparing the expressions in equations (1.4) and (1.3) we conclude the following:

1  2 
ck  X k k  0,1,......., ( N  1) ………………. (1.5)
N  N 

Therefore it is possible to write the expression xp[n] as below:

N 1
 2  j 2kn / N
x p n 
1
N
 X  N
k 0
k e

n  0,1,....., ( N  1) ………. (1.6)

The above formula shows the reconstruction of the periodic signal xp[n] from the samples of
the spectrum X[w]. But it does not say if X[w] or x[n] can be recovered from the samples.

Let us have a look at that:

Since xp[n] is the periodic extension of x[n] it is clear that x[n] can be recovered from x p[n] if
there is no aliasing in the time domain. That is if x[n] is time-limited to less than the period N
of xp[n].This is depicted in Fig. 1.2 below:

Dept., of ECE/SJBIT Page 8

Smartworld.asia 9

Digital Signal Processing 10EC52

x[n]

0 L

xp[n] N>=L
No aliasing

0 L N

xp[n] N<L
Aliasing

0 N

Fig. 1.2 Signal Reconstruction

Hence we conclude:
The spectrum of an aperiodic discrete-time signal with finite duration L can be exactly
2k
recovered from its samples at frequencies wk  if N >= L.
N

We compute xp[n] for n=0, 1,....., N-1 using equation (1.6)

Then X[w] can be computed using equation (1.1).

1.3 Discrete Fourier Transform:

The DTFT representation for a finite duration sequence is
∞ -jωn
X (jω) = ∑ x (n) ℮
n= -∞
jωn
X (n) =1/2π ∫X (jω) e dω , Where ω═ 2πk/n

Dept., of ECE/SJBIT Page 9

Smartworld.asia 10

Digital Signal Processing 10EC52

2π
Where x(n) is a finite duration sequence, X(jω) is periodic with period 2π.It is
convenient sample X(jω) with a sampling frequency equal an integer multiple of its period =m
that is taking N uniformly spaced samples between 0 and 2π.
Let ωk= 2πk/n, 0≤k≤N-1

∞ -j2πkn/N
Therefore X(jω) = ∑ x(n) ℮
n=−∞
Since X(jω) is sampled for one period and there are N samples X(jω) can be expressed
as
N-1 -j2πkn/N
X(k) = X(jω)│ ω=2πkn/N ═∑ x(n) ℮ 0≤k≤N-1
n=0

1.4 Matrix relation of DFT

The DFT expression can be expressed as

[X] = [x(n)] [WN]

T
Where [X] = [X(0), X(1),……..]

[x] is the transpose of the input sequence. WN is a N x N matrix

WN = 1 1 1 1 ………………1
1 wn1 wn2 wn3……………...wn n-1
1 wn2 wn4 wn6 ……………wn2(n-1)
…………………………………………….
…………………………………………….
1………………………………..wN (N-1)(N-1)

ex;
4 pt DFT of the sequence 0,1,2,3

X(0) 1 1 1 1
X(1) 1 -j -1 j
X(2) = 1 -1 1 -1
X(3) 1 j -1 -j

Solving the matrix X(K) = 6 , -2+2j, -2 , -2-2j

1.5 Relationship of Fourier Transforms with other transforms

Dept., of ECE/SJBIT Page 10
Smartworld.asia 11

Digital Signal Processing 10EC52

1.5.1 Relationship of Fourier transform with continuous time signal:

Suppose that xa(t) is a continuous-time periodic signal with fundamental period Tp= 1/F0.The
signal can be expressed in Fourier series as

Where {ck} are the Fourier coefficients. If we sample xa(t) at a uniform rate Fs = N/Tp = 1/T,
we obtain discrete time sequence

Thus {ck’} is the aliasing version of {ck}

1.5.2 Relationship of Fourier transform with z-transform

Let us consider a sequence x(n) having the z-transform

With ROC that includes unit circle. If X(z) is sampled at the N equally spaced points on the
unit circle Zk = e j2πk/N for K= 0,1,2,………..N-1 we obtain

The above expression is identical to Fourier transform X(ω) evaluated at N equally spaced
frequencies ωk = 2πk/N for K= 0,1,2,………..N-1.

Dept., of ECE/SJBIT Page 11

Smartworld.asia 12

Digital Signal Processing 10EC52

If the sequence x(n) has a finite duration of length N or less. The sequence can be recovered
from its N-point DFT. Consequently X(z) can be expressed as a function of DFT as

Fourier transform of a continuous time signal can be obtained from DFT as

Dept., of ECE/SJBIT Page 12

Smartworld.asia 13

Digital Signal Processing 10EC52

Recommended Questions with solutions

Question 1
The first five points of the 8-point DFT of a real valued sequence are {0.25, 0.125-j0.318, 0,
0.125-j0.0518, 0}. Determine the remaining three points

Ans: Since x(n) is real, the real part of the DFT is even, imaginary part odd. Thus the
remaining points are {0.125+j0.0518,0,0, 0.125+j0.318}.

Question 2
Compute the eight-point DFT circular convolution for the following sequences.
x2(n) = sin 3πn/8
Ans:

Question 3
Compute the eight-point DFT circular convolution for the following sequence
X3(n) = cos 3πn/8

Dept., of ECE/SJBIT Page 13

Smartworld.asia 14

Digital Signal Processing 10EC52

Question 4
Define DFT. Establish a relation between the Fourier series coefficients of a continuous time
signal and DFT

Solution

The DTFT representation for a finite duration sequence is

∞
X (jω) = ∑ x (n) ℮-jωn
n= -∞

X (n) =1/2π ∫X (jω) e jωn dω , Where ω═ 2πk/n

2π
Where x(n) is a finite duration sequence, X(jω) is periodic with period 2π.It is
convenient sample X(jω) with a sampling frequency equal an integer multiple of its period =m
that is taking N uniformly spaced samples between 0 and 2π.
Let ωk= 2πk/n, 0≤k≤N
∞
Therefore X(jω) = ∑ x(n) ℮-j2πkn/N
n=−∞
Since X(jω) is sampled for one period and there are N samples X(jω) can be expressed
as
N-1
X(k) = X(jω)│ ω=2πkn/N ═∑ x(n) ℮-j2πkn/N 0≤k≤N-1
n=0
Question 5

Solution:-

Dept., of ECE/SJBIT Page 14

Smartworld.asia 15

Digital Signal Processing 10EC52

Question 6

Find the 4-point DFT of sequence x(n) = 6+ sin(2πn/N), n= 0,1,………N-1

Solution :-

Question 7

Solution

Dept., of ECE/SJBIT Page 15

Smartworld.asia 16

Digital Signal Processing 10EC52

Question 8

Solution

Dept., of ECE/SJBIT Page 16