DSP Algorithms and

Architecture
COURSE OUTCOME (CO):

CO1: To understand the Discrete-Fourier Transform (DFT) and the FFT

algorithms.
CO2: To learn the design of FIR filters for filtering undesired signal.
CO3: To learn the design of IIR and IIR filters for filtering undesired
signal.
CO4: To analyse the finite word length effects in DSP systems.
CO5: To understand the architectural issues of DSP processors.
 Syllabus

Unit-I Introduction of Digital Signal Processing System, Advantages of

DSP, Discrete-Fourier Transform: Matrix formulation, Properties of DFT,
Linear Convolution using DFT, FFT-Efficient Computation of DFT, radix-2
Decimation-in-Time and Decimation-in-Frequency FFT Algorithms,
Circular addressing mode, Bit-Reversed Addressing Mode.

Unit-II Design of FIR Digital Filters: Advantages/disadvantages of digital

filters, Difference between FIR and IIR fitters, Frequency response of
type1,2,3 and 4 FIR filters. Filter Specifications, Desirability of linear-phase
FIR filters, Impulse response of ideal LP, HP, BP and BS filters, Design of
linear phase FIR Digital Filters using Windows. Structures of FIR filters.
 Design of IIR Digital Filters, Impulse-invariant method, Bilinear
Unit-III transformation method, IIR filter specifications, Specifications of LP
filter, Characteristics of commonly used analog filters (Butterworth),
Structures of IIR filters.
Unit-IV Multirate Signal Processing: decimation, interpolation, sampling rate
conversion by a rational factor, computational requirements, polyphase
decomposition, multistage implementation of sampling rate conversion,
Nyquist filters: half-band filter, uniform DFT filter bank: polyphase
implementation, two-channel QMF bank; subband coding of speech and
audio signals.
Unit-V Characteristics of DSP processors, Evolution of DSP processors, DSP
processors architectures: Von-Neumann, Harvard, and super Harvard
architecture, DSP hardware units: MAC, barrel shifter, address generators
etc., Difference between fixed-point and floating-point DSP processors,
VLIW architecture, Addressing modes, Overview of TMS320C6713 DSP
processor.
SUGGESTED READINGS:

Digital Signal Processing by John Proakis , Dimitris Manolakis

Digital Signal Processing by Alan V. Oppenheim , Ronald W.
Schafer
DSP by Ramesh Babu
S. K. Mitra, “Digital Signal Processing- A Computer based approach”,
Tata McGraw-Hill.
Avatar Singh and S. Srinivasan, “Digital Signal Processing”, Thomson
Learning, 2004.
Tarun Kumar Rawat, “Digital Signal Processing”, Oxford University
Press.
B Venkataramani and M Bhaskar , “Digital Signal Processors”, TMH,
2002
List of Experiments:
Experiments using TMS320C6713 DSP Starter Kit

1) (a) Introduction to the Digital Signal Processing Kit (DSK) and the
Code Composer Studio (CCS).
(b) Sine Wave Generation Using Eight points with DIP Switch
Control.
(c) Generation of sinusoid and Plotting with CCS (sine8_buf).
2) (a) Basic Input and Output Using Polling (loop_poll).
(b) Basic Input and Output Using Interrupts (loop_intr).
(c) Sine Wave Generation Using sin() Function, Reconstruction,
Aliasing, and the Properties of the AIC 23 Codec.
3) Plot the DFT of the sequence given in experiment #5.
4) Design an FIR filter for the specifications given in experiment # 7.
5) Design and IIR filter for the specifications given in experiment # 10.
 Presentation Outline

 Introduction of Digital Signal Processing System

 Advantages of DSP,

 Discrete-Fourier Transform:

 Matrix formulation, Properties of DFT, Linear Convolution

using DFT, FFT-Efficient Computation of DFT, radix-2
Decimation-in-Time and Decimation-in-Frequency FFT
Algorithms, Circular addressing mode, Bit-Reversed
Addressing Mode.
Digital Signal Processing

Advantages
 Greater Accuracy
 Cheaper
 Ease of data storage
 Implementation of sophisticated algorithms.
 Flexibility in configuration
 Applicability of VLF signals
 Time Sharing

Limitations
 Bandwidth Limited by Sampling rate
 Power Consumption
 System Complexity
Applications of DSP
 Telecommunication:- Echo cancellation in telephone network,
Telephone dialling applications, modems, line repeaters, channel
multiplexing, data encryption, video conferencing, cell phone and Fax.
 Consumer Electronics:- Digital Audio/TV, Electronic music
synthesizer, educational toys, FM stereo control Digital Filter.
 Instrumentation and control:- PLL, function generators servo control,
Robot control, process control.
 Image processing:- Image compression, enhancement, Image analysis
and recognition.
 Speech processing:- Speech analysis methods are used in automatic
speech recognition, speaker verification and speaker identification.
 Medical Image Processing
 Military: Reader Signal processing, sonar signal processing navigation,
secure communications.
 Discrete Time Fourier Transform (DTFT):
 DTFT is used for converting a signal from time domain to frequency domain.

where w is continuous function of frequency and X(w) is periodic with period 2π

 The IDTFT is defined by

 Equations 1 and 2 are DTFT pair

 In DTFT, input in time domain is discrete but output in frequency domain
becomes continuous function of frequency, thus it cannot be used for DSP
applications. X(w) is continuous and periodic with period 2π.
 There are infinite values of w in this range and therefore DTFT is not
numerically computable transform and it cannot be processed by digital
computers and digital signal processors. It leads to need of other transform
which is suitable for digital signal processing applications.
Discrete Fourier Transform (DFT)
 The DFT is frequency domain sampling of DTFT
DTFT of sequence x(n) is defined by

DFT

IDFT
Magnitude and Phase of DFT
 DFT

 Magnitude Spectrum

 Phase Spectrum
Q. Compute the 4 point DFT of signal

Sol.
Q. Compute the 4 point DFT of signal

Sol.
Second Method
For k=0, X(k)=undefined so put k=0 in (1)
Q. Compute N point DFT of the signal
Q. Compute 8 point DFT X(k) of Signal
Q. Compute 8 point DFT of following signal and also
sketch its magnitude and phase spectrum.

Sol.
Fig.3 a) magnitude spectrum b) phase spectrum
Second Method
Q. Determine the N-point DFT of following sequence
of length L for N ≥ L

Sol. DTFT is find out `

 k = 1, 2, …, N-1

If L is selected such that N = L, DFT become

If we wish to have better picture, more closely spaced samples of
frequencies are required where
N > L and we can expand x(n) sequence by padding.
N - L zeroes in x(n)
Q. Compute N point DFT of

Sol.
Q. Find N point DFT of following
Q.

Put n = 2m
Q. Determine N point DFT of the sequence

Sol.
n = -1, 0, 1

Where k = 0, 1,… ,N – 1
Q. Compute N point IDFT of

Sol.
Q. Find the 4 point inverse DFT of

Sol.
Q. Compute 4 point DFT of following function.

Sol.
Q. Obtain 4 point DFT of unit impulse signal

Sol.
DFT as Linear Transformation (Matrix formulation)

The DFT can be seen as linear transformations on sequence x(n).

The N point DFT of sequence x(n) is given by:

Consider the twiddle factor which is defined as

n = 0, 1, 2, ........, N - 1
So DFT in matrix form
Q. Determine the 4 points DFT of x(n)={0,1,2,3}
Sol. N=4

k n=0 1 2 3
Using property of periodically

Using symmetry property

Q. Compute the 4 point DFT X(k) of signal
The IDFT
Second Method
Check: for real sequence X(k)= X*(N-k)
Representation of sequence in Circular Form
Circular symmetry: - The periodic sequence is denoted by
The period of is N which means that sequence repeats itself
after N samples. For ease of convenience, it is better to represent
periodic sequence in circular form.
 From above equation we can say that obtained by circular shifting
sequence x(n) by 2 samples. It means is related to x(n) by circular shift.
 The relation of circular shift is represented by index
modulo N

Other notation as

k = no. of samples by which x(n) is delayed

N = N point DFT
In above examples, 4 samples in x(n) so 4 point DFT

Index modulo N converts an index either +ve or –ve in a positive index

in the range 0→N-1. If index value goes beyond 0-N-1 range, then add or
subtract N to restrict in the range 0→N-1.
 Graphical representation
i) Circular plot of sequence x(n)

This is obtained by circularly plotting sequence in anticlockwise

ii) Circular delay: delay by k samples means shift the sequence
circularly in anticlockwise direction by k units
 iii) Circular advance

iv) Circularly folded sequence is plotted in clockwise direction

v) Circular even sequence: if it is symmetric about the point zero on

circle.
E.g. and N=4
vi) Circularly odd sequence: if it is anti symmetric about
origin

E.g. and N=4

 Symmetry

1) Input sequence Plot samples in anticlockwise direction.

2) Circular delay Shift sequence in anticlockwise direction by k samples.

3) Circular advance Shift sequence in clockwise direction by k samples.

4) Circular folding Plot samples in clockwise direction.

5) Circular Even Sequence symmetric about zero point.

6) Circular Odd Sequence anti symmetric about zero point.

 Properties of DFT
Time Domain Frequency Domain

1) Periodicity

2) Linearity

3) Circular convolution

4) Time reversal

5) Circular time shift

6) Circular Frequency shift

7) Complex conjugate

8) Parseval’s theorem

9) Symmetry property
1) Periodicity Property:

If discrete time signal is periodic, its DFT will be periodic.

For all values of n

For all values of k

Proof:
DFT
Second Method
Using IDFT
2) Linearity:-
Proof

DFT of
 3) Circular convolution: The multiplication of 2 DFTs is equivalent to the
circular convolution of their sequences in time domain.

Here indicates circular convolution

Let result of circular convolution of

Proof

IDFT
(A)
Where m,n,l are integers

When m – n – l is multiple of N, then

 (B)

When m – n – l multiple of N is this can be expressed as

Where p is an integer, for simplicity we take it as positive

(c)

We have not considered the second summation of (B) because this summation
in terms of l and now this term is absent in (c).
 4) Time reversal of a sequence
If sequence is circular folded, its DFT is also circularly folded.

Proof
Second Method

Put m = N – n
n=N–m
[Limits of m; n = 0, m = N; n = N-1, m = 1
5) Circular time shift of a sequence
Shifting sequence in time domain by l samples is equivalent to multiplying
sequence in frequency domain by

Proof
 Second Method

For 2nd case

6) Circular Frequency shift of a sequence
Second Method

The multiplication of is equivalent to circular shift of DFT in

frequency domain by l samples.

Proof IDFT
7) Complex Conjugate property
 Circular correlation In general, for complex valued sequences
x(n) and y(n), if

Un-normalized cross relation sequence defined as

8) Parseval’s Theorem:
Proof:
8) Symmetry properties of DFT
 Comparing

Case I When x(n) is real, that is, then its N point DFT is
 Proof

Using complex conjugate property 7

The DFT of a real signal is conjugate symmetry.

Case II: When x(n) is real and even

Since imaginary part is zero, substituting

IDFT can be computed by substituting

then its N point DFT

is also real and even.

Case III: When x(n) is real and odd means

Proof –

x(n) is real so in A and odd so

as cos is even function.

imaginary and odd.

 Case IV: If x(n) is pure imaginary sequence

The DFT of an imaginary signal is conjugate anti symmetric.

10) Duality property:

Exchange X by n
 Use of DFT in linear filtering

Where h(n) is impulse response of the FIR filter

In time domain

In Frequency domain Y(w)=X(w) H(w)

Q.2 Obtain N point DFT of delayed unit impulse
Q.3 The first 5 points of the 8 pts. DFT of a real valued sequence
are {0.25, 0.125 – j 0.3018, 0, 0.125 – j 0.0518, 0} Determine
remaining 3 points.

Sol. Given DFT points are

Given sequence is real valued sequence, according to symmetry properly

Here, N = 8
 Q. The first 5 DFT points of real and even sequence x(n) of length 8
are given below. Determine remaining three points X(k) = {5,1,0,2,3}

Sol. Given DFT points are

This is 8 points DFT, thus N = 8

 Q. Find circular convolution of following 2 sequences

Sol. Four methods to find circular convolution

a) Using formula of CC
b) graphical method
c) Matrix method
d) Using IDFT

a) Using formula circular convolution is given by

 N=4

Put m = 1 in (1)

= 1 + 4 + 4 + 1 = 10
Ans.
b) Graphical Method
C) Matrix Method
 Q. Find the circular convolution of following two sequences

Sol. Circular convolution is given by

m = 0, 1, 2…. N – 1

N = 4 (Modulus is used to see indices in given range)

By matrix method
 Q. Determine the 4 point circular convolution of 2
sequences g(n) and h(n) of length four given by

Sol.
Q. Find circular convolution of following two sequences

Sol. 1st step is padding with zeroes to make length of both sequences same

Q. Find Circular convolution of the followings

Q.

Q.
 Q. Find linear convolution using circular convolution

Linear convolution

Sol. Padding with zeroes

Q. Find circular convolution of following sequences using
linear convolution

Sol. Direct method of Circular Convolution

2nd method

Linear Convolution

Circular convolution
 Q. Find circular convolution.

Sol.

Answer
check:
Q. Find circular convolution using linear convolution.
Linear Filtering of Long Data Sequences

When sequences of data are exceptionally very large and operation of linear
filter to be done, large memory is required to store sequence. Thus, input
sequence must be segmented to fixed size blocks prior to processing. Since
filtering is linear blocks can be processed one at a time and then output blocks
are fitted to form the overall output signal sequence.

There are two methods for filtering of long data sequence

1) Overlap add methods

2) Overlap save methods
 1) Overlap Save Method :

Given: x(n) long data sequence and h(n) of length M

Divide given input sequence into sub-sequences of length L. y(n) length will be
L+M-1.
Linear convolution using circular convolution
a) Divide given input sequence into subsequences of length L.
b) Add M-1 zeroes so that data sequence of length L+M-1 is formed. Each input
section overlaps the preceding section by M-1 samples. To begin the
processing the first M -1 samples of the first section are set to zero.
c) The h(n) in length is increased by padding L-1 zeroes so length become
L+M+1
In this method we are saving previous bits. Let h = 3
 Q. Solve using overlap save method

Sol. Here M = 3, Divide x(n) into segments of equal length L ≥ M and then
append M - 1 = 3 - 1 = 2 zeroes
Output Signal

discard M – 1 bit.
Verification: linear convolution of given seq.
 Ques. Find the linear convolution of

Using overlap save method

Sol.

Output signal
Fig.: Linear Filtering by overlap save map M = 3

Length of y(n) in linear filtering will be L+M+1 so pad M-1 zeros in x(n) and pad
L-1 zeros in h(n)
Length of h(n) = 3, pad M – 1 = zeroes let L = 6 so pad M-1 zeros in x(n)
 Ques. Compute linear convolution of

Using overlap add method

Sol.

Fig.: Linear Filtering by overlap Add Map

Length of y(n) in linear filtering will be L+M+1 so pad M-1 zeros in x(n)
and pad L-1 zeros in h(n)

Length of h(n) = M=3, pad 2 zeros

Length of input block should be

Let L=6 so pad M-1=2 zeros in x(n) and pad L-1 =5 zeros in h(n)
Verification
1) Calculate linear and circular convolution of
x(n) = {1 2 3 4} and h(n) = {1 2 1 1}.

2)Find linear convolution using circular convolution

x(n) = {1 2 3} and h(n) = {1 2}.

3)Determine the 8-point DFT of the sequence

x(n) =cos{(π/2)n}

4)Using Transformation technique find DFT of the sequence

x(n)={1,2,3,4}. transformation technique is MATRIX method

5)For the sequence x(n) = {1,2,3,4} find x((-n+2))4.

6) The first five points of 8 point DFT are (1, 1+j, -j, 2-j, j)
find remaining points.

7)Compute DFT of the sequence x (n) = 2n 0≤n≤4.

8)Compute the N-point DFT for the sequence x (n) = n +1 where N = 8.

9) Calculate IDFT for X(k) = {3, 2+j, 1, 2-j}.

10) Find the IDFT of X(k) = {1, 2, 3, 4}.

11)State and prove periodicity property of DFT.

12)Find circular convolution using linear convolution.

13)The Circular convolution of two sequences x[n] = [1 0 0 0] and
y[n] = [0 1 0 1] is [ 0 1 01]