Digital Signal Processing-Full
Digital Signal Processing-Full
hsqsev2sqxev
ygisxq
Second Edition
About the Author
A. Nagoor Kani is a multifaceted personality with an efficient technical expertise and management skills.
He obtained his BE in EEE from Thiagarajar College of Engineering, Madurai and MS (Electronics and
Control) through Distance Learning program of BITS, Pilani.
He started his career as a self-employed industrialist (1986-1989) and then changed his career to teaching
in 1989. He has worked as lecturer in Dr MGR Engineering College (1989-1990) and as Asst. Professor
in Satyabhama Engineering College (1990-1997). The author started his own coaching centre for BE
students named Institute of Electrical Engineering which was renamed as RBA Tutorials in 2005. The
author started his own companies in 1997. The companies currenly run by him are RBA Engineering
(manufacturing of lab equipments and microprocessor trainer kits), RBA Innovations (involved in developing
projects for engineering students and industries), RBA Tutorials (conducting coaching classes for engineering
and GATE students) and RBA Publications (publishing of engineering books.) His optimistic and innovative
ideas brought up RBA GROUP successfully.
He is an eminent writer and till now he has authored nine engineering books, and his books are very
popular among engineering students. He is known by name through his books in all engineering colleges
in south India and in some colleges in north India.
hsqsev2sqxev
ygisxq
Second Edition
A. Nagoor Kani
Founder, RBA Educational Group
Chennai
McGraw-Hill Offices
New Delhi New York St Louis San Francisco Auckland Bogotá Caracas
Kuala Lumpur Lisbon London Madrid Mexico City Milan Montreal
San Juan Santiago Singapore Sydney Tokyo Toronto
iv
ISBN-13: 9780070086654
ISBN-10: 0070086656
Information contained in this work has been obtained by Tata McGraw-Hill, from sources believed to be reliable.
However, neither Tata McGraw-Hill nor its authors guarantee the accuracy or completeness of any information
published herein, and neither Tata McGraw-Hill nor its authors shall be responsible for any errors, omissions, or
damages arising out of use of this information. This work is published with the understanding that Tata McGraw-Hill
and its authors are supplying information but are not attempting to render engineering or other professional services. If
such services are required, the assistance of an appropriate professional should be sought.
Typeset at Tej Composers, WZ-391, Madipur, New Delhi 110063, and printed at Rajkamal Electric Press, Plot No. 2,
Phase IV, HSIIDC, Kundli, Sonepat, Haryana 131 028
Dedicated to
2.1 Introduction.................................................................................................................................................2. 1
2.2 Discrete Time Signals................................................................................................................................2. 3
2.2.1 Generation of Discrete Time Signals................................................................................................2. 3
2.2.2 Representation of Discrete Time Signals...........................................................................................2. 4
2.2.3 Standard Discrete Time Signals......................................................................................................2. 5
2.3 Sampling of Continuous Time (Analog) Signals..............................................................................................2. 8
2.3.1 Sampling and Aliasing.................................................................................................................. 2. 8
2.4 Classification of Discrete Time Signals..............................................................................................................2.12
2.4.1 Deterministic and Nondeterministic Signals............................................................................................2.12
2.4.2 Periodic and Aperiodic Signals.............................................................................................................2.12
2.4.3 Symmetric (Even) and Antisymmetric (Odd) Signals.............................................................................2.15
2.4.4 Energy and Power Signals.................................................................................................................2.17
2.4.5 Causal, Noncausal and Anticausal Signals...........................................................................................2.19
2.5 Mathematical Operations on Discrete Time Signals............................................................................................2.20
2.5.1 Scaling of Discrete Time Signals........................................................................................................2.20
viii
Chapter 3 : Z - Transform
3.1 Introduction..............................................................................................................................................3. 1
3.2 Region of Convergence............................................................................................................................3. 4
3.3 Properties of Z-Transform...........................................................................................................................3. 11
3.4 Poles and Zeros of Rational Function of z....................................................................................................3. 27
3.4.1 Representation of Poles and Zeros in z-plane..................................................................................3. 28
3.4.2 ROC of Rational Function of z......................................................................................................3. 29
3.4.3 Properties of ROC......................................................................................................................3. 30
3.5 Inverse Z-Transform...................................................................................................................................3. 31
3.5.1 Inverse Z-Transform by Contour Integration or Residue Method......................................................... 3. 31
3.5.2 Inverse Z-Transform by Partial Fraction Expansion Method..............................................................3. 32
3.5.3 Inverse Z-Transform by Power Series Expansion Method................................................................3. 35
3.6 Analysis of LTI Discrete Time System Using Z-Transform.............................................................................. 3. 48
3.6.1 Transfer Function of LTI Discrete Time System.................................................................................3. 48
3.6.2 Impulse Response and Transfer Function........................................................................................3. 49
3.6.3 Response of LTI Discrete Time System Using Z-Transform................................................................3. 49
3.6.4 Convolution and Deconvolution Using Z-Transform..........................................................................3. 50
3.6.5 Stability in z-Domain.......................................................................................................................3. 51
3.7 Relation between Laplace Transform and Z-Transform...................................................................................3. 56
3.7.1 Impulse Train Sampling of Continuous Time Signal...........................................................................3. 56
3.7.2 Transformation From Laplace Transform to Z-Transform................................................................... 3. 57
3.7.3 Relation Between s-Plane and z-Plane...........................................................................................3. 57
x
4.1 Introduction............................................................................................................................................4. 1
4.2 Fourier Series of Discrete Time Signals (Discrete Time Fourier Series)..........................................................4. 2
4.2.1 Frequency Spectrum of Periodic Discrete Time Signals..................................................................4. 3
4.2.2 Properties of Discrete Time Fourier Series.................................................................................... 4. 4
4.3 Fourier Transform of Discrete Time Signals (Discrete Time Fourier Transform)................................................4. 9
4.3.1 Development of Discrete Time Fourier Transform from Discrete Time Fourier Series............................4. 9
4.3.2 Definition of Discrete Time Fourier Transform..................................................................................4. 10
4.3.3 Frequency Spectrum of Discrete Time Signal.................................................................................4. 11
4.3.4 Inverse Discrete Time Fourier Transform.......................................................................................4. 12
4.3.5 Comparison of Fourier Transform of Discrete and Continuous Time Signals..........................................4. 12
4.4 Properties of Discrete Time Fourier Transform..............................................................................................4. 13
4.5 Discrete Time Fourier Transform of Periodic Discrete Time Signals............................................................... 4. 20
4.6 Analysis of LTI Discrete Time System Using Discrete Time Fourier Transform................................................4. 22
4.6.1 Transfer Function of LTI Discrete Time System in Frequency Domain.............................................. 4. 22
4.6.2 Response of LTI Discrete Time System Using Discrete Time Fourier Transform...................................4. 23
4.6.3 Frequency Response of LTI Discrete Time System.........................................................................4. 23
4.6.4 Frequency Response of First Order Discrete Time System...............................................................4. 25
4.6.5 Frequency Response of Second Order Discrete Time System.........................................................4. 31
xi
7.4.1 Relation between analog and digital filter poles in bilinear transformation ................................................ 7. 16
7.4.2 Relation between analog and digital frequency in bilinear transformation ................................................ 7. 17
7.5 Specifications of digital IIR lowpass filter ............................................................................................................ 7. 24
7.6 Design of lowpass digital Butterworth filter ......................................................................................................... 7. 27
7.6.1 Analog Butterworth filter ....................................................................................................................... 7. 27
7.6.2 Poles of Butterworth lowpass filter ....................................................................................................... 7. 28
7.6.3 Transfer function of analog Butterworth lowpass filter ............................................................................ 7. 35
7.6.4 Frequency response of analog lowpass Butterworth filter ..................................................................... 7. 37
7.6.5 Order of the lowpass Butterworth filter ................................................................................................. 7. 37
7.6.6 Cutoff frequency of lowpass Butterworth filter ....................................................................................... 7. 37
7.6.7 Design procedure for lowpass digital Butterworth IIR filter ..................................................................... 7. 38
7.7 Design of lowpass digital Chebyshev filter ........................................................................................................ 7. 40
7.7.1 Transfer function of analog Chebyshev lowpass filter ........................................................................... 7. 42
7.7.2 Order of analog lowpass Chebyshev filter ........................................................................................... 7. 43
7.7.3 Cutoff frequency of analog lowpass Chebyshev filter ........................................................................... 7. 44
7.7.4 Frequency response of analog Chebyshev lowpass filter .................................................................... 7. 44
7.7.5 Design procedure for lowpass digital Chebyshev IIR filter ................................................................... 7. 45
7.8 Frequency transformation .................................................................................................................................. 7. 47
7.8.1 Analog frequency transformation .......................................................................................................... 7. 47
7.8.2 Digital frequency transformation ........................................................................................................... 7. 48
7.9 Summary of Important Concepts ....................................................................................................................... 7. 109
7.10 Short Questions and Answers ........................................................................................................................... 7. 111
7.11 MATLAB Programs .......................................................................................................................................... 7. 121
7.12 Exercises ......................................................................................................................................................... 7. 141
The chapter also presents the methods of obtaining responses of LTI discrete time systems and various
convolution methods. The deconvolution, correlation techniques and the inverse systems are clearly
explained with solved numericals. In addition, the concept of sampling and its importance are dealt with
briefly.
Chapter 3 explains Z-transform and its application to discrete time signals and systems. All the important
properties of Z-transform are presented explicitly. Inverse Z-transform and solution of difference
equations describing the discrete time systems are demonstrated with numerical examples. Also, the
structures for realization of IIR and FIR systems are provided.
Chapter 4 is dedicated to discrete time Fourier series and Fourier transform which forms the basics
for frequency domain analysis of discrete time signals and systems. In the first half of this chapter, the
discrete time Fourier series and the frequency spectrum using discrete time Fourier series are discussed
with relevant examples.
The second half of the chapter details the development of discrete time Fourier transform from discrete
time Fourier series, frequency spectrum, various properties of Fourier transform, and Fourier transform
of some standard discrete time signals. In addition, the computation of frequency responses of LTI
discrete time systems using Fourier transform are also explained with examples. The relation between
Fourier transform and Z-transform of discrete time signals is also discussed in the chapter.
Chapter 5 extends the understanding of the concepts of Discrete time Fourier transform(DTFT) to
DFT (Discrete Fourier transform) and FFT (Fast Fourier Transform). Development of DFT from
DTFT, properties of DFT, relation between DFT and Z-transform, analysis of the LTI systems using
DFT and FFT are extensively discussed.
Chapter 6 focuses on frequency response of FIR filters and characteristics various windows used
for FIR filter design. Also, design of linear phase FIR filters by windowing and frequency sampling
techniques are presented with suitable examples.
Chapter 7 explains the techniques for transforming analog filter to digital filter and the characteristics
of analog Butterworth and Chebyshev filters. Also, design of Butterworth and Chebyshev digital IIR
filters are presented with examples.
Chapter 8 discusses the quantization and representation of digital/binary number systems. The effects
due to finite precision of filter coefficients and products, and various types of overflow in recursive
computations are also discussed with appropriate examples.
Chapter 9 focuses on sampling rate conversion by decimation and interpolation and their effects on
frequency spectrum. Implementation of sampling rate conversion in filters and application of multirate
digital signal processing are also discussed in the chapter.
Chapter 10 is concerned with the estimation of energy spectrum of discrete time signals and power
spectrum of random process. The various nonparametric methods power spectrum estimation and
their performance characteristics are presented.
Chapter 11 focuses on architecture and programming of special purpose processors for digital signal
processing with particular concentration to Texas Instruments digital signal processors TMS320C5x
and TMS320C54x processors.
Chapter 12 provide a brief discussion on some applications of digital signal processing in speech,
musical sound, audio/video, communication and biomedical signals.
The author has taken care to present the concepts of Digital Signal Processing in a simple manner and
hope that the teaching and student community will welcome the book. The readers can feel free to
convey their criticism and suggestions to [email protected] for further improvement of the book.
A.Nagoor Ka ni
Kani
xxi
Acknowledgements
I express my heartful thanks to my wife Ms.C. Gnanaparanjothi Nagoor Kani and my sons
N. Bharath Raj alias Chandrakani Allaudeen and N.Vikram Raj for the support, encouragement and
cooperation they have extended to me throughout my career.
It is my pleasure to acknowledge the contributions to our technical editors Ms.K.Jayashree, Ms.
B.Hemavathy, Ms. S. Pavithra for editing and proofreading of the manuscript, and Ms. A. Selvi, Ms.
M. Faritha for type setting and preparing the layout of the book.
My sincere thanks to all reviewers for their valuable suggestions and comments which helps me to
explore the subject to greater depth.
I am also grateful to Ms.Vibha Mahajan, Mr.Ebi John, Ms. Koyel Ghosh, Mr. P.L.Pandita and
Ms. Sohini Mukherjee of Tata McGraw Hill Education for their concern and care in publishing this
work.
xxii
My special thanks to Ms. Koyel Ghosh of McGraw Hill Education for her care in bringing out this
work at the right time.
I thank all my office staff for their cooperation in carrying out my day-to-day activities.
Finally, a special note of appreciation is due to my sisters, brothers, relatives, friends, students and the
entire teaching community for their overwhelming support and encouragement to my writing.
A. Nagoor Kani
List of Symbols and Abbreviations
Symbols
B - Bandwidth in Hz
E - Energy of a signal
er - Rounding error
j - complex operator, −1
L - Number of segments
xxiv
M - Figure of merit
M - Mantissa
N - Fundamental period
P - Power of a signal
p - Pole
Q - Quality factor
r - Radix or base
S - Sign bit
t - Time in seconds
V - Variabiltiy
Î - Attenuation costant
Wo - Center frequency
s2 - Variance
s2eoi - Steady state output noise power due to input quantization error
* - Convolution operator
z - Integration operator
d
- Differentiation operator
dt
xxvi
Standard/Input/Output Signals
tp - Phase delay
tg - Group delay
F - Fourier transform
H - System operator
Q[ ] - Quantization operations
Z - Z-transform
Abbreviations
BIBO - Bounded Input Bounded Output
DT - Discrete Time
Var - Variance
1.1 Introduction
Digital Signal Processing (DSP) refers to processing of signals by digital systems like Personal
Computers (PC) and systems designed using digital Integrated Circuits (ICs), microprocessors and
microcontrollers. DSP gained popularity in the 1960s. Earlier, DSP systems were limited to general purpose
non-real-time scientific and business applications. The rapid advancement in computers and IC fabrication
technology leads to complete domination of DSP systems in both real-time and non-real-time applications
in all fields of engineering and technology.
The basic components of a DSP system are shown in fig 1.1. The DSP system involves conversion of
analog signal to digital signal, then processing of the digital signal by a digital system and then conversion
of the processed digital signal back to analog signal.
1.2 Signal
Any physical phenomenon that conveys or carries some information can be called a signal. The
music, speech, motion pictures, still photos, heart beat, etc., are examples of signals that we normally encounter
in day-to-day life.
When a signal is defined continuously for any value of an independent variable, it is called an analog
or continuous signal. Most of the signals encountered in science and engineering are analog in nature.
When the dependent variable of an analog signal is time, it is called a continuous time signal and it is denoted
as “x(t)”.
When a signal is defined for discrete intervals of an independent variable, it is called a discrete signal.
When the dependent variable of a discrete signal is time, it is called discrete time signal and it is denoted by
“x(n)”. Most of the discrete signals are either sampled versions of analog signals for processing by digital
systems or output of digital systems.
The quantized and coded version of the discrete time signals are called digital signals. In digital
signals the value of the signal for every discrete time “n” is represented in binary codes. The process of
conversion of a discrete time signal to digital signal involves quantization and coding.
Normally, for binary representation, a standard size of binary is chosen. In m-bit binary representation,
we can have 2m binary codes. The possible range of values of the discrete time signals are usually divided
into 2m steps called quantization levels, and a binary code is attached to each quantization level. The values
of the discrete time signals are approximated by rounding or truncation in order to match the nearest quantization
level.
The ratio of Z -transform of output and input is called transfer function of the discrete time system.
The inverse Z -transform of the system gives the impulse response of the system, which is used to study the
characteristics of a system.
Another important characteristic of any signal is frequency, and for most of the applications the
frequency content of the signal is an important criteria. The frequency range of some of the signals are listed
in table 1.1 and 1.2.
Table 1.1 : Frequency Range of Some Electromagnetic Signals
1.5 Filters
The filters are frequency selective devices. The two major types of digital filters are FIR (Finite Impulse
Response) and IIR (Infinite Impulse Response) filters.
Generally, the filter specification will be a desired frequency response. The inverse Fourier transform
of the frequency response will be the impulse response of the filter, and it will be an infinite duration signal.
The digital filters designed by choosing finite samples of impulse rseponse are called FIR filters, and the
filters designed by considering all the infinite samples are called IIR filters.
Since, an FIR filter is designed from the finite samples of impluse response, the direct design of FIR filter
is possible in which the transfer function of the filter is obtained by taking Z -transform of impulse response.
Note : Mathematically, the filter design is design of transfer function of the filter.
Since, an IIR filter is designed by considering / preserving the infinite samples of impulse response,
the direct design of IIR filter is not possible. Therefore, the IIR filter is designed via analog filter. For
designing IIR filter, first the specifications of IIR filter is transformed to specifications of analog filter using
bilinear or impulse-invariant transformation, then an analog filter transfer function is designed using
Butterworth or Chebychev approximation. Finally the analog filter transfer function is transfered to digital
filter transfer function using the transformation chosen for transforming the specifications.
2. Speech Processing
· Speech compression and decompression to reduce memory requirement of storage systems.
· Speech compression and decompression for effective use of transmission channels.
· Speech recognization for voice operated systems and voice based security systems.
· Speech recognization for conversion of voice to text.
· Speech synthesis for various voice based warnings or annoucements.
5. Power electronics
· The spectrum analysis of the output of coverters and inverters will reveal the harmonics present in
the output, which in turn helps to design suitable filter to eliminate the harmonics.
· The analysis of switching currents and voltages in power devices will help to reduce losses.
6. Image processing
· Image compression and decompression to reduce memory requirement of storage systems.
· Image compression and decompression for effective use of transmission channels.
· Image recognition for security systems.
· Filtering operations on images to extract the features or hidden information.
7. Geology
· The seismic signals are used to determine the magnitude of earthquakes and volcanic eruptions.
· The seismic signals are also used to predict nuclear explosions.
· The seismic noises are also used to predict the movement of earth layers (tectonic plates).
8. Astronomy
· The analysis of light received from a star is used to determine the condition of the star.
· The analysis of images of various celestial bodies gives vital information about them.
2.1 Introduction
In today's world, digital systems are employed for almost every application. The digital systems can
process only discrete signals. This chapter deals with time domain analysis of discrete time signals and
systems. In the first part of this chapter, the generation, representation, classification and mathematical
operations on discrete time signals are discussed in detail. In the second part of this chapter, the representation,
classification and response of discrete time systems are discussed in detail. The concept of LTI systems are
highlighted wherever necessary.
Discrete Signal and Discrete Time Signal
The discrete signal is a function of a discrete independent variable. The independent variable is
divided into uniform intervals and each interval is represented by an integer. The letter "n" is used to denote
the independent variable. The discrete or digital signal is denoted by x(n).
The discrete signal is defined for every integer value of the independent variable "n". The magnitude
(or value) of discrete signal can take any discrete value in the specified range. Here both the value of the
signal and the independent variable are discrete. The discrete signal can be represented by a one-dimensional
array as shown in the following example.
Example :
x(n) = { 2, 4, -1, 3, 3, 4 }
Here the discrete signal x(n) is defined for, n = 0, 1, 2, 3, 4, 5
\ x(0) = 2 ; x(1) = 4 ; x(2) = –1 ; x(3) = 3 ; x(4) = 3 ; x(5) = 4 .
When the independent variable is time t, the discrete signal is called discrete time signal. In discrete
time signal, the time is divided uniformly using the relation t = nT, where T is the sampling time period. (The
sampling time period is the inverse of sampling frequency). The discrete time signal is denoted by x(n) or x(nT).
Chapter 2 - Discrete Time Signals and Systems 2. 2
Since the discrete signals have a sequence of numbers (or values) defined for integer values of the
independent variable, the discrete signals are also known as discrete sequence. In this book, the term sequence
and signal are used synonymously. Also in this book, the discrete signal is referred as discrete time signal.
Digital Signal
The digital signal is same as discrete signal except that the magnitude of the signal is quantized. The
magnitude of the signal can take one of the values in a set of quantized values. Here quantization is necessary
to represent the signal in binary codes.
The generation of a discrete time signal by sampling a continuous time signal and then quantizing the
samples in order to convert the signal to digital signal is shown in the following example.
Let, x(t) = Continuous time signal
T = Sampling time
A typical continuous time signal and the sampling of this continuous time signal at uniform interval
are shown in fig 2.1a and fig 2.1b respectively. The samples of the continuous time signal as a function of
sampling time instants are shown in fig 2.1c. (In fig 2.1c, 1T, 2T, 3T, ....etc., represents sampling time instants
and the value of the samples are functions of this sampling time instants).
x (t) x (t) x (n t)
1.0 1.0 1.0
0.9
0.9 0.9 0.9
0.8 0.8
0.8 0.8 0.8
0 1T 2T 3T 4T 5T 6T 7T t 0 1T 2T 3T 4T 5T 6T 7T t 0 1T 2T 3T 4T 5T 6T 7T t
F ig 2 .1 a . F ig 2 .1 b . F ig 2 .1 c.
F ig 2 .1 : S a m p lin g a co n tin u o us tim e sig n a l to g en era te d iscrete tim e sig na l.
The numbers 0, 2, 4, ...., 2N form a sequence of even numbers and can be expressed as,
x(n) = 2n ; 0 £ n £ N
Chapter 2 - Discrete Time Signals and Systems 2. 4
3. A third method is by uniformly sampling a continuous time signal and using the amplitudes of
the samples to form a sequence.
Let, x(t) = Continuous time signal
Now, Discrete signal, x(nT) = x(t) t = nT ; − ∞ < n < ∞
where, T is the sampling interval
The generation of discrete signal by sampling a continuous time signal is shown in fig 2.1.
2.2.2 Representation of Discrete Time Signals
The discrete time signal can be represented by the following methods.
1. Functional representation
In functional representation, the signal is represented as a mathematical equation, as shown in the
following example. x (n )
x(n) = – 0.5 ; n = – 2 1.5
1.2
= 1.0 ; n = – 1 1.0
= – 1.0 ; n = 0 0.6
= 0.6 ; n = 1
= 1.2 ; n = 2
= 1.5 ; n = 3 −2 −1 0 1 2 3 n
= 0 ; other n −0.5
−1.0
F ig 2.2 : G ra phica l rep resenta tio n of a
2. Graphical representation d iscrete tim e sig na l.
In graphical representation, the signal is represented in a two-dimensional plane. The independent
variable is represented in the horizontal axis and the value of the signal is represented in the vertical axis as
shown in fig 2.2.
3. Tabular representation
In tabular representation, two rows of a table are used to represent a discrete time signal. In the first
row, the independent variable "n" is tabulated and in the second row the value of the signal for each value of
"n" are tabulated as shown in the following table.
n ........... –2 -1 0 1 2 3 ..............
x(n) ........... –0.5 1.0 –1.0 0.6 1.2 1.5 ..............
2. 5 Digital Signal Processing
4. Sequence representation
In sequence representation, the discrete time signal is represented as a one-dimensional array as
shown in the following examples.
An infinite duration discrete time signal with the time origin, n = 0, indicated by the symbol - is represented as,
x(n) = { ..... – 0.5, 1.0, –1.0, 0.6, 1.2, 1.5, ..... }
-
An infinite duration discrete time signal that satisfies the condition x(n) = 0 for n < 0 is represented as,
x(n) = { –1.0, 0.6, 1.2, 1.5, ... } or x(n) = {–1.0, 0.6, 1.2, 1.5, ... }
-
A finite duration discrete time signal with the time origin, n = 0, indicated by the symbol - is represented as,
x(n) = { – 0.5, 1.0, –1.0, 0.6, 1.2, 1.5 }
-
A finite duration discrete time signal that satisfies the condition x(n) = 0 for n < 0 is represented as,
x(n) = { –1.0, –0.6, 1.2, 1.5 } or x(n) = { –1.0, 0.6, 1.2, 1.5}
-
= 0; n < 0 4
3
2
3. Ramp signal 1
Ramp signal, u r ( n ) = n ; n ≥ 0 0 1 2 3 4 5 n
= 0 ;n < 0 F ig 2.5 : R a m p sig na l.
4. Exponential signal
n
Exponential signal, g( n) = a ; n ≥ 0
= 0 ;n < 0
0 1 2 3 4 5 6 n 0 1 2 3 4
F ig 2.6a : D e c re asin g e x po n en tia l sign a l. F ig 2.6b : In cre a sin g ex p o ne n tial sig n al.
F ig 2.6 : E xp o n en tia l sig n a l.
Chapter 2 - Discrete Time Signals and Systems 2. 6
5. Discrete time sinusoidal signal
The discrete time sinusoidal signal may be expressed as,
bg b g
x n = A cos ω 0n + θ ; for n in the range -¥ < n < +¥
xb ng = A sin bω n + θg ; for n in the range -¥ < n < +¥
0
−9 −8 −7 −6 −5 −4 4 5 6 7 8 9
−3 −2 −1 0 1 2 3
n
x (n )
F ig 2 .7 a : D iscrete tim e sin u so id a l sig n a l rep re se n ted
b y e q u a tio n x(n ) = A c o s( ω0 n ).
−6 −5 −4 −3 −2 −1 7 8 9 10 11 12
x (n ) 0 1 2 3 4 5 6 n
1. A discrete time sinusoid is periodic only if its frequency f0 is a rational number, (i.e., ratio of two
integers).
2. Discrete time sinusoids whose frequencies are separated by integer multiples of 2p are identical.
∴ x(n) = A cos[(w 0 + 2pk ) n + q], for k = 0,1,2...........are identical in the interval
-p£w0 £ p and so they are indistinguishable.
Proof :
Conclusion
n n
F ig 2.8 a : T h e d isc rete tim e se q u en c e re presen ted b y the F ig 2.8 b : T h e d isc rete tim e se q u en c e re presen ted b y the
n n
e qu a tio n, x r (n) = a c o s ω0 n for 0 < a < 1 . e qu a tio n, x r (n) = a c o s ω0 n for a > 1 .
F ig 2 .8 : R ea l p a rt o f co m p lex exp o n en tia l sig na l.
The imaginary part of x(n) will give rise to an exponentially increasing sinusoid sequence for a > 1 and
exponentially decreasing sinusoid sequence for 0 < a < 1.
x i (n ) x i (n )
0<a<1 a>1
n n
F0
where, f 0 = = Frequency of discrete sinusoid in cycles/sample
Fs
w0 = 2pf 0= Frequency of discrete sinusoid in radians/sample
Example 2.1
Consider the analog signals, x1(t) = 3 cos 2p(20t) and x2(t) = 3 cos 2p(70t).
Find a sampling frequency so that 70Hz signal is an alias of the 20Hz signal?
Solution
Let, the sampling frequency, Fs = 70 - 20 = 50Hz.
Example 2.2
Let an analog signal, xa(t) = 10 cos 200 pt. If the sampling frequency is 150Hz, find the discrete time signal
x(n). Also find an alias frequency corresponding to Fs = 150 Hz.
Solution
n
x(n) = x a (t) n = 10 cos 200πt n
= 10 cos 200 π ×
t = nT =
Fs t = Fs
Fs
= 10 cos
200π × n
= 10 cos
4π
n = 10 cos 2π −
2π FG
n = 10 cos
2π IJ 1
n = 10 cos 2π n
150 3 3 H3 K 3
We know that the discrete time sinusoids whose frequencies are separated by integer multiples of 2p are
identical.
∴ 10 cos
2π
n = 10 cos
2π FG
+ 2π n = 10 cos
8π IJ 4
n = 10 cos 2π n
3 3 H 3 K 3
4 2π
Now, 10 cos 2π n is an alias of 10 cos n.
3 3
4
Here the frequency of the signal, 10 cos 2π n is,
3
4
f= cycles / sample
3
F 4
We know that, f = ⇒ F = f Fs = × 150 = 200Hz
Fs 3
∴ when, Fs = 150Hz, F = 200Hz is an alias frequency.
2. 11 Digital Signal Processing
Example 2.3
Consider the analog signal, xa(t) = 6 cos50pt + 3 sin 200pt 3 cos100pt .
Determine the minimum sampling frequency and the sampled version of analog signal at this frequency.
Sketch the waveform and show the sampling points. Comment on the result.
Solution
The given analog signal can be written as shown below.
xa(t) = 6 cos50pt + 3 sin 200pt 3 cos100pt = 6 cos 2p F1t + 3 sin 2p F2t 3cos 2p F3t
Where, 2p F1 = 50p ; ÞF1 = 25Hz
2p F2 = 200p ; Þ F2 = 100Hz
2p F3 = 100p ;Þ F3 = 50Hz
The maximum analog frequency in the signal is 100Hz. The sampling frequency should be twice that of
this maximum analog frequency.
i.e., Fs ³ 2 Fmax Þ Fs ³ 2 ´ 100
Let, sampling frequency, Fs = 200Hz
∴ x a (nT) = x a ( t ) t = nT = x a (t) n
t =
Fs
50 πn 200 πn 100 πn πn πn
= 6 cos + 3 sin − 3cos = 6 cos + 3 sin πn − 3 cos
200 200 200 4 2
For integer values of n, sinpn = 0.
πn πn
∴ x a (nT ) = 6 cos
− 3 cos
4 2
The components of analog waveform and the sampling points are shown in fig1.
Comment : In the sampled version of analog signal xa (nT), the component 3 sin 200pt will give always zero
samples when sampled at 200Hz for any value of n. This is the drawback in sampling at Nyquist rate (i.e.,
sampling at Fs = 2Fmax).
1
6 c os 50 πt ; F1 = 25 H z ; T1 = = 0.04 s ec
F1
1
3 sin 200 πt ; F 2 = 100 H z ; T 2 = = 0.01 sec
F2
1
3 c os 100 πt ; F3 = 50 H z ; T3 = = 0.02 sec
F3
0.005
1
0.01 Fs = 200 H z ; T = = 0.005 sec
0.02 Fs
0.04
1 1 1 1
0 n
−1 −1 −1 −1 −1 −1 −1 −1
x (n) = {. . . . . . .2 , 1 , 2, − 1, − 1, 2 , 1 , 2, − 1, − 1, 2 , 1, 2 , − 1 , − 1 , . . . . . . . }
A
F ig 2.1 0 : P erio d ic d iscrete tim e sig n a l.
When a discrete time signal is a sum or product of two periodic signals with fundamental periods N1
and N2, then the discrete time signal will be periodic with period given by LCM of N1 and N2.
Example 2.4
Determine whether following signals are periodic or not. If periodic find the fundamental period.
a) x(n) = cos
FG 5π n + 1IJ b) x(n) = sin
FG n − πIJ c) x(n) = sin
π 2
n
H9 K H9 K 8
j7 πn 3 πn
5πn j
d) x(n) = e 4 e) x(n) = 2cos + 3e 4
3
2. 13 Digital Signal Processing
Solution
∴ N = 4 M1 \ N = 8 M2
Now, N is integer for M1 = 12, 22, 32, 42 ..... Now, N is integer for M2 = 1, 2, 3, 4 .....
2
When M1 = 2 and M2 = 1, we get a common value for N as, N = 8.
F π n + π8 + π8 nI
2
2
For interger M,
When N = 8 ; x(n + N) = sin GH 8 8 4 JK sin (q + 2p M) = sinq
FF π I I Fπ
= sin G G n + 2πnJ + 4 × 2πJ = sin G n
2 2
+ 2πn
IJ
HH 8 K K H8 K
π 2
= sin
n = x(n)
8
\ x(n) is periodic with fundamental period, N = 18 samples.
Chapter 2 - Discrete Time Signals and Systems 2. 14
j7 πn
d) Given that, x(n) = e 4
7 πN
Since, ej2pM = 1, for periodicity should be an integral multiple of 2p.
4
7 πN
Let , = M × 2π,
4
4 8M
∴ N = M × 2π × =
7π 7
Here, N is integer, when M = 7, 14, 21, ......
When M = 7 ; N = 8
\ x(n) is periodic with fundamental period of 8 samples.
3π n
5πn j
e) Given that, x(n) = 2 cos + 3e 4
3
Let , x(n) = x1(n) + x 2 (n)
5πn
where, x1(n) = 2 cos
3
3πn
j
x 2 (n) = 3e 4
5πn j
3 πn
Consider, x1(n) = 2 cos Consider, x 2 (n) = 3 e 4
3
b g
∴ x1 n + N1 = 2 cos
b
5 π n + N1 g j
3π(n +N2 )
3 b g
∴ x 2 n + N2 = 3 e 4
5πN1 6 3πN2 8
Let , = 2πM1 ⇒ N1 = M1 Let , = 2πM2 ⇒ N2 = M2
3 5 4 3
Let, M1 = 5 ; \ N1 = 6 Let, M2 = 3 ; \ N2 = 8
Substitute N1 = 6 in equation (1), Substitute N2 = 8 in equation (2),
b g
∴ x1 n + N1 = 2 cos
FG 5πn + 5π × 6IJ j
FG 3πn + 3π × 8 IJ
H4 4 K
H3 3 K b g
∴ x 2 n + N2 = 3e
F 5πn + 5 × 2πIJ
= 2 cos G j
FG 3πn +3× 2πIJ
H4 K
For integer M,
H3 K For integer M,
= 3e
5πn 3πn
cos(q +2pM) = cosq = 2cos = x1(n) ej(q + 2pM) = ejq j
4 =
3 = 3e x 2 (n)
\ x1(n) is periodic with fundamental period, \ x2(n) is periodic with fundamental period,
N1 = 6 samples. N2 = 8 samples.
Here, x(n) = x1(n) + x2(n), and x1(n) is periodic with period N1 = 6, and x2(n) is periodic with period N2 = 8.
Therefore, x(n) is periodic with period N, where N is LCM of N1 and N2.
The LCM of 6 and 8 is 24.
\ N = 24
\ x(n) is periodic with fundamental period, N = 24.
2. 15 Digital Signal Processing
2 2 2 2
2
1 1
1 1 1 1
−4 −3 −2 −1 0 1 2 3 4 n
−4 −3 −2 −1 0 1 2 3 4 n
−1 −1
−2 −2
x (n) = {1 , 2 , 3 , 1 , 2 , 1 , 3 , 2 , 1} x (n ) = {1, 2, − 2, − 1 , 0 , 1 , 2 , − 2, − 1 }
A
F ig 2.11 a : S y m m e tric (or e v en ) sig na l.
A
F ig 2.11 b : A ntisym m etric (o r o dd ) sig n al.
F ig 2.11 : S y m m etric a nd a ntisym m etric d iscrete tim e sig n al.
A discrete time signal x(n) which is neither even nor odd can be expressed as a sum of even and
odd signal.
Let, x(n) = xe (n) + xo (n)
bg
where, x e n = Even part of x(n)
xo(n) = Odd part of x(n)
Note : If x(n) is even then its odd part will be zero. If x(n) is odd then its even part will be zero.
Now, it can be proved that,
1
Even part, xe (n) = x(n) + x(− n)
2
1
Odd part, xo (n) = x(n) − x(− n)
2
Proof :
Let, x(n) = xe(n) + xo(n) ......(2.8)
1
∴ x e(n) = x(n) + x(− n)
2
On subtracting equation (2.10) from equation (2.8) we get,
1
∴ x o(n) = x(n) − x(− n)
2
Example 2.5
Determine the even and odd parts of the signals.
π
j n
a) x(n) = 3n b) x(n) = 3 e 5 c) x(n) = {2, − 2, 6, − 2}
Solution
a) Given that, x(n) = 3n
∴ x(−n) = 3−n
1 1 n
Even part, x e (n) = [x(n) + x( −n)] = [3 + 3−n ]
2 2
1 1 n
Odd part, x o (n) = [x(n) − x( −n)] = [3 − 3−n ]
2 2
π
j n
b) Given that, x(n) = 3 e 5
π
j n π π
x(n) = 3 e 5 = 3 cos n + j3 sin n
5 5
π
−j n π π
∴ x(−n) = 3 e 5 = 3 cos n − j3 sin n
5 5
1
Even part, x e (n) = [x(n) + x(−n)]
2
=
1 πLM π π π
3 cos n + j3sin n + 3 cos n − j3 sin n =
1 π OP
π
6 cos n = 3 cos n
LM OP
2 5 N 5 5 5 2 5 Q
5 N Q
1
Odd part, x o (n) = [x(n) − x( −n)]
2
=
LM 1 π π π π
3 cos n + j3sin n − 3 cos n + j3sin n
OP
N 2 5 5 5 5 Q
1L π O π
= Mj6 sin nP = j3 sin n
2N 5 Q 5
The energy of a signal may be finite or infinite, and can be applied to complex valued and
real valued signals.
If energy E of a discrete time signal is finite and nonzero, then the discrete time signal is called an
energy signal. The exponential signals are examples of energy signals.
The average power of a discrete time signal x(n) is defined as,
N
1 2 .....(2.12)
Power , P = lim
N→∞ 2N + 1 ∑ x( n)
n =− N
If power P of a discrete time signal is finite and nonzero, then the discrete time signal is called a power
signal. The periodic signals are examples of power signals.
For energy signals, the energy will be finite and average power will be zero. For power signals the
average power is finite and energy will be infinite.
a) x(n) =
FG 1IJ n
u(n) b) x(n) = sin
FG π nIJ c) x(n) = u(n)
H 4K H3 K
Solution
H 4K
F 1I n
+N N
1 2 1 2
Power, P = Lt ∑ x(n) = Lt ∑ (0.25)n
N→∞ 2N + 1 n = −N
N→ ∞ 2N + 1 n = 0
N N
1 1
= Lt ∑ (0.252 )n = Lt ∑ (0.0625)n
N→∞ 2N + 1 n = 0
N→∞ 2N + 1 n = 0
∑ x(n) =
2
∑
+∞
sin2
FG π nIJ = ∑ +∞
3
n = −∞ n = −∞
H3 K n = −∞ 2
Note : Sum of infinite 1's is infinity. Sum of samples of one period of cosinusoidal signal is zero.
N N
1 2 1 πn
Power, P = Lt
N→ ∞
2N + 1
∑ x(n) = Lt
N→∞
2N + 1
∑ sin2
3
n = −N n = −N
2. 19 Digital Signal Processing
1 L
MM ∑ 1 − ∑ cos 23π nOPP
N N
1 n
= Lt
N→∞ 2N + 1 2 N n = −N Q n = −N
= Lt
1 1 L
M1+ 14 +.......+
O
1+31 − 0P
31+ 1+ 11+.......+
N→∞ 2N + 1 MN
2 144 2444 44
N terms
42444
PQ N terms
1 1 1 1
= Lt 2N + 1 = Lt = watts
N→∞ 2N + 1 2 N→∞ 2 2
n = −∞ n =0
+∞
= ∑ u(n) = 1+ 1+ 1 . ........ ∞ = ∞
n =0
1 N
1 N
1 F I
G 3JJ
2
P = Lt ∑ x(n) = Lt ∑ u(n) = Lt
G 1+ 1+ 1+.........+1
N→∞
2N + 1 n = −N
N→∞
2N + 1 n =0
N→∞
2N + 1 H
1444 424444
N + 1 terms K
FG 1 IJ
N 1+ 1
= Lt
1
(N + 1) = Lt
H NK = 1+ ∞ = 1+ 0 = 1 watts
N→∞
2N + 1 N→∞ F 1I 2 + 1 2 + 0 2
N G2 + J
H NK ∞
A discrete time signal is said to be noncausal, if it is defined for either n ≤ 0, or for both n ≤ 0 and
n > 0. Therefore if x(n) is noncausal, then x(n) ≠ 0 for n < 0. A noncausal signal can be converted to causal
signal by multiplying the noncausal signal by a unit step signal, u(n).
When a noncausal discrete time signal is defined only for n ≤ 0, it is called an anticausal signal.
Chapter 2 - Discrete Time Signals and Systems 2. 20
Examples of Causal and Noncausal Signals
123
3
-
3 12
Causal signals
x(n) = {2, 2, 3, 3,.............}
-
x(n) = {1, –1, 2, –2, 3, –3}
123
123
-
12
Anticausal signals
x(n) = {............,2, 2, 3, 3}
-
Noncausal signals
x(n) = {2, 3, 4, 5, 4, 3, 2}
-
x(n) = {......, 2, 3, 4, 5, 4, 3, 2,......}
-
2. Folding
3. Shifting : Right shift (or advance) and left shift (or delay)
4. Addition
5. Multiplication
Amplitude scaling of a discrete time signal by a constant A is accomplished by multiplying the value
of every signal sample by the constant A.
Example :
Let, x(n) = 10 ; n=0 and A = 0.2, When n = 0 ; y(0) = A x(0) = 0.2 ´ 10 = 2.0
There are two ways of time scaling a discrete time signal. They are downsampling and upsampling.
n
In a signal x(n), if n is replaced by , where I is an integer, then it is called upsampling.
I
2. 21 Digital Signal Processing
Example :
If x(n) = bn ; n ³ 0 ; 0 < b < 1, then
x (n ) x 1 (n) x 2 (n)
b
0
1
b0 x 1 (n) = x(2n) b
0
x 2 (n) = x ej
n
2
b
b1
b2 b2
2
b
3
4
b
b 3
b4 b
b5 6 b6
b
0 1 2 3 4 5
0 1 2 3 6 n 0 1 2 3 4 5 6 n
n
F ig 2.12 a : A d isc re te tim e sig n al x (n ). F ig 2.12 b : D o w n sa m p le d sig na l o f x (n). F ig 2.12 c : U p sa m p le d sig n al x (n ).
F ig 2.1 2 : A d iscrete tim e sign a l a n d its tim e sca led versio n .
Example :
Let x(n) = 0.8n ; –2 £ n £ 2. Now the folded signal, x1(n) = x(–n) = –0.8n ; –2 £ n £ 2
x (n ) x 1 (n)
x 1 (n) = x ( −n)
1.6 1.6
0.8 0.8
−2 −1 0 1 2 n −2 −1 0 1 2 n
−0.8 −0.8
−1.6 −1.6
th
rd
d(n) = 1 ; for n = 0
0 m n
= 0 ; for n ¹ 0 F ig 2.1 5 : D elayed u nit im pu lse.
The unit impulse signal delayed by m units of time is denoted as d(n – m).
Now, d(n – m) = 1 ; n = m
= 0 ; n ¹m
2. 23 Digital Signal Processing
Delayed Unit Step Signal x 4 (n)
x 4 (n) = u(n −m )
1
The unit step signal is defined as,
u(n) = 1 ; for n ³ 0 n
m +1
0
m + 2
m + 4
m +3
m
= 0 ; for n < 0 F ig 2.1 6 : D elay ed un it step sig n a l.
The unit step signal delayed by m units of time is denoted as u(n – m).
Now, u(n – m) = 1 ; n ³ m
=0;n<m
A discrete time system is linear if it obeys the principle of superposition and it is time invariant if its
input-output relationship does not change with time. When a discrete time system satisfies the properties of
linearity and time invariance then it is called an LTI system (Linear Time Invariant system).
Impulse Response
When the input to a discrete time system is a unit impulse d(n) then the output is called an impulse
response of the system and is denoted by h(n).
The equation (2.17) is a constant coefficient difference equation, governing the input-output relation
of an LTI discrete time system.
In equation (2.17) the value of "N" gives the order of the system.
If N = 1, the discrete time system is called 1st order system
If N = 2, the discrete time system is called 2nd order system
If N = 3, the discrete time system is called 3rd order system , and so on.
The general difference equation governing 1st order discrete time LTI system is,
y(n) = – a1 y(n – 1) + b0 x(n) + b1 x(n – 1)
The general difference equation governing 2nd order discrete time LTI system is,
y(n) = – a2 y(n – 2) – a1 y(n – 1) + b0 x(n) + b1 x(n – 1) + b2 x(n – 2)
2.6.2 Block Diagram and Signal Flow Graph Representation of Discrete Time System
The discrete time system can be represented diagrammatically by block diagram or signal flow
graph. These diagrammatic representations are useful for physical implementation of discrete time system in
hardware or software.
The basic elements employed in block diagram or signal flow graph are adder, constant multiplier, unit
delay element and unit advance element.
Adder : An adder is used to represent addition of two discrete time signals.
Constant Multiplier : A constant multiplier is used to represent multiplication of a scaling factor
(constant) to a discrete time signal.
Unit Delay Element : A unit delay element is used to represent the delay of samples of a discrete
time signal by one sampling time.
Chapter 2 - Discrete Time Signals and Systems 2. 26
Unit Advance Element : A unit advance element is used to represent the advance of samples of a
discrete time signal by one sampling time.
The symbolic representation of the basic elements of block diagram and signal flow graph are listed in
table 2.1.
Table 2.1 : Basic Elements of Block Diagram and Signal Flow Graph
x1 ( n )
x1 (n ) x1 ( n ) + x 2 ( n )
Adder +
x1 ( n ) + x 2 ( n )
x2 (n)
x2 (n)
x (n ) a x(n ) a
a x (n ) a x(n )
Constant multiplier
x (n ) x (n − 1 ) z −1
z −1 x (n ) x (n − 1 )
Unit delay element
x (n ) x (n + 1 ) z
z x (n ) x (n + 1 )
Unit advance element
Example 2.7
Construct the block diagram and signal flow graph of the discrete time systems whose input-output
relations are described by the following difference equations.
a) y(n) = 0.7 x(n) + 0.7 x(n 1)
b) y(n) = 0.4 y(n 1) + x(n) 3 x(n 2)
c) y(n) = 0.2 y(n 1) + 0.7 x(n) + 0.9 x(n 1)
Solution
a) Given that, y(n) = 0.7 x(n) + 0.7 x(n 1)
The individual terms of the given equation are 0.7 x(n) and 0.7 x(n 1). They are represented by basic
elements as shown below.
2. 27 Digital Signal Processing
Block diagram representation Signal flow graph representation
0.7
x(n) 0.7 0.7 x(n) x(n) 0.7 x(n)
−1
−1
z
0.7 x(n) z 0.7 x(n − 1) 0.7 x(n) 0.7 x(n − 1)
The input to the system is x(n) and the output of the system is y(n). The above elements are connected
as shown below to get the output y(n).
−3 x(n − 2) 0.4 y (n − 1)
x (n) y (n)
x (n) y (n)
−1
z 0.4 −1
−1 −1 z
z z
x (n − 1) y (n − 1) x (n − 1)
−3 y (n − 1)
−1 0.4 y (n − 1)
z −1
0.4 z
x (n − 2)
−3 −3 x(n − 2)
x (n − 2)
The input to the system is x(n) and the output of the system is y(n). The above elements are connected
as shown below to get the output y(n).
x (n) y (n) x (n) 1 1 1 1 1 y (n)
+ +
−1
−1 z
−1 −1
z
z z 0.4
−3
−1
z −1
0.4 z
−3
x(n) x(n)
0.9 x(n − 1)
−1
z
−1
z
0 .9
0.9 x(n − 1)
0.9
x(n − 1) x(n − 1)
y(n)
0.2 y(n − 1)
y(n)
−1
z −1
z
0.2 y(n − 1) y(n − 1) 0.2
0.2
y(n − 1)
The input to the system is x(n) and the output of the system is y(n). The above elements are connected
as shown below to get the output y(n).
−1 −1 −1
z z
−1 z 0.9 0.2 z
0.9 0.2
N M
∴ y(n) + ∑ a m ybn − mg = ∑ bm xbn − mg
m=1 m= 0
N M
.....(2.18)
( or ) ∑ a m ybn − mg = ∑ b m xbn − mg with a o = 1
m= 0 m= 0
The solution of the difference equation (2.18) is the response y(n) of LTI system, which consists of
two parts. In mathematics, the two parts of the solution y(n) are homogeneous solution yh(n) and particular
solution yp(n).
2. 29 Digital Signal Processing
\ Response, y(n) = yh(n) + yp(n) .....(2.19)
The homogeneous solution is the response of the system when there is no input.The particular
solution yp(n) is the solution of difference equation for specific input signal x(n) for n ³ 0.
In signals and systems, the two parts of the solution y(n) are called zero-input response yzi(n) and
zero-state response yzs(n).
\ Response, y(n) = yzi(n) + yzs(n) .....(2.20)
The zero-input response is mainly due to initial conditions (or initial stored energy) in the system.
Hence zero-input response is also called free response or natural response. The zero-input response is given
by homogeneous solution with constants evaluated using initial conditions.
The zero-state response is the response of the system due to input signal and with zero initial
condition. Hence the zero-state response is called forced response.The zero-state response or forced response
is given by the sum of homogeneous solution and particular solution with zero initial conditions.
The homogeneous solution is obtained when x(n) = 0. Therefore the homogeneous solution is the
solution of the equation,
N
∑ a m y( n − m) = 0 .....(2.21)
m= 0
Let us assume that the solution of equation (2.21) is in the form of an exponential.
i.e., y(n) = ln
On substituting y(n) = ln in equation (2.21) we get,
N
∑ a m λn − m = 0
m= 0
On expanding the above equation (by taking a0 = 1), we get,
ln + a1 ln – 1 + a2 ln – 2 + ... + aN – 1 ln – (N – 1) + aN ln – N = 0
ln – N (lN + a1 lN – 1 + a2 lN – 2 + ... + aN – 1 l + aN) = 0
Now, the characteristic polynomial of the system is given by,
lN + a1 lN – 1 + a2 lN – 2 + ... + aN – 1 l + aN = 0
The characteristic polynomial has N roots, which are denoted as l1, l2,...lN.
The roots of the characteristic polynomial may be distinct real roots, repeated real roots or complex.
The assumed solutions for various types of roots are given below.
Distinct Real Roots
Let the roots l1, l2, l3, ... lN be distinct real roots. Now the homogeneous solution will be in the form,
y h ( n) = C1 λn1 + C2 λn2 + C3 λn3 + ...... + C N λnN
where, C1 , C2 , C3 ,......C N are constants that can be evaluated using initial conditions.
Chapter 2 - Discrete Time Signals and Systems 2. 30
Repeated Real Roots
Let one of the real roots l1 repeats p times and the remaining (N – p) roots are distinct real roots. Now,
the homogeneous solution is in the form,
The general form of particular solution for various types of inputs are listed in table 2.2.
Table 2.2 : Particular Solution
y(n) =
FG 4 − 0.8 y(−1)IJ (−0.8) n
+
5
H9 K 9
a) When y(1) = 0
4 5
∴ y(n) = ( −0.8)n + ; for n ≥ 0
9 9
=
LM b
4
g
−0.8 +
n 5 OP
u(n)
N
9 9 Q
b) When y(1) = 2/9
∴ y(n) =
FG 4 − 0.8 × 2IJ (−0.8) n
+
5
=
2.4 5 24
( −0.8)n + = (−0.8)n +
5
H9 9K 9 9 9 90 9
5 12
∴ y(n) = + (−0.8)n ; for n ≥ 0
9 45
=
LM 5 + 12 (−0.8)nOP u(n)
N 9 45 Q
Example 2.9
Determine the response y(n), n ³ 0 of the system described by the second order difference equation,
y(n) 0.2 y(n 1) 0.03 y(n 2) = x(n) + 0.4 x(n 1),
when the input signal is, x(n) = 0.2n u(n) and with initial conditions y( 2) = 0, y( 1) = 0.5.
Solution
Given that, y(n) 0.2 y(n 1) 0.03 y(n 2) = x(n) + 0.4 x(n 1) .....(1)
Homogeneous Solution
The homogeneous equation is the solution of equation (1) when x(n) = 0.
\ y(n) 0.2 y(n 1) 0.03 y(n 2) = 0 .....(2)
n
Put y(n) = l in equation (2). The roots of quadratic,
\ ln 0.2 ln 1 0.03 ln 2 = 0 λ2 − 0.2λ − 0.03 = 0 are,
ln 2 (l2 0.2l 0.03) = 0 0.2 ± 0.22 + 4 × 0.03
λ=
The characteristic equation is, 2
l2 0.2l 0.03 = 0 Þ (l 0.3) (l + 0.1) = 0 0.2 ± 0.4
= = 0.3, − 0.1
\ The roots are, l = 0.3, 0.1 2
The homogeneous solution, yh(n) is given by,
The total response y(n) of the system is given by sum of homogeneous and particular solution.
\ Response, y(n) = yh (n) + yp (n)
= C1 0.3n + C2 (0.1)n + ( 4) 0.2n ; for n ³ 0 .....(6)
To find y(0) and y(1)
When n = 0,
From equation (1) we get,
y(0) 0.2 y(1) 0.03 y(2) = x(0) + 0.4 x(1) .....(7)
Given that, y(1) = 0.5, y(2) = 0
x(n) = 0.2n u(n), \ x(0) = 0.20 = 1
x(1) = 0
On substituting the above conditions in equation (7) we get,
y(0) 0.2 ´ 0.5 0.03 ´ 0 = 1 + 0
\ y(0) = 1.1 .....(8)
When n = 1,
From equation (1) we get,
y(1) 0.2 y(0) 0.03 y(1) = x(1) + 0.4 x(0) .....(9)
We know that, y(0) = 1.1, y(1) = 0.5, y(2) = 0
Given that, x(n) = 0.2n u(n), \ x(0) = 0.20 = 1
x(1) = 0.21 = 0.2
On substituting the above conditions in equation (9) we get,
y(1) 0.2 ´ 1.1 0.03 ´ 0.5 = 0.2 + 0.4 ´ 1
\ y(1) = 0.6 + 0.235 = 0.835 .....(10)
To solve constants C1 and C2
When n = 0,
From equation (6) we get,
y(0) = C1 0.30 + C2 (0.1)0 + (4) 0.20 = C1 + C2 4 .....(11)
From equations (8) and (11) we can write,
C1 + C2 4 = 1.1
\ C1 + C2 = 5.1 .....(12)
2. 35 Digital Signal Processing
When n = 1,
From equation (6) we get,
y(1) = C1 ´ 0.3 + C2 (0.1) + (4) 0.2 = 0.3 C1 0.1C2 0.8 .....(13)
From equations (10) and (13) we can write,
0.3 C1 0.1C2 0.8 = 0.835
\ 0.3 C1 0.1C2 = 1.635 .....(14)
Equation (12) ´ 0.1 Þ 0.1C1 + 0.1C2 = 0.51
Equation (13) Þ 0.3C1 0.1C2 = 1.635
Add 0.4C1 = 2.145
2.145
∴ C1 = = 5.3625
0.4
From equation(12),
C2 = 5.1 C1 = 5.1 5.3625
= 0.2625
Total Response
y(n) = [5.3625(0.3)n 0.2625(0.1)n + (4) 0.2n] u(n) ; for all n
∞
Infinite memory is required
y(n) = ∑ x(n − m)
m= 0
Chapter 2 - Discrete Time Signals and Systems 2. 36
2.8.2 Time Invariant and Time Variant Systems
A system is said to be time invariant if its input-output characteristics do not change with time.
Definition : A relaxed system H is time invariant or shift invariant if and only if
H{x(n)} = y(n) implies that, H{x(n – m)} = y(n – m)
for every input signal x(n) and every time shift m.
i.e., in time invariant systems, if y(n) = H{x(n)} then y(n – m) = H{x(n – m)}.
Alternative Definition for Time Invariance
A system H is time invariant if the response to a shifted (or delayed) version of the input is identical
to a shifted (or delayed) version of the response based on the unshifted (or undelayed) input.
i.e., In a time invariant system, H{x(n - m)} = z-m H{x(n)}; for all values of m .....(2.22)
-m
The operator z represents a signal delay of m samples.
The diagrammatic explanation of the above definition of time invariance is shown in fig 2.19.
Procedure to Test for Time Invariance
1. Delay the input signal by m units of time and determine the response of the system for this
delayed input signal. Let this response be y(n – m).
2. Delay the response of the system for undelayed input by m units of time. Let this delayed
response be yd(n).
3. Check whether y (n – m) = yd(n). If they are equal then the system is time invariant.
Otherwise the system is time variant.
x (n) x (n − m ) y (n − m )
−m
Input signa l
z H
D elayed input R espons e for
D elay S y stem delay ed in put
Example 2.10
Test the following systems for time invariance.
a) y(n) = x(n) + x(n 1) b) y(n) = 2n x(n) c) y(n) = x(n) d) y(n) = x(n) b x(n 1)
Solution
a) Given that, y(n) = x(n) + x(n 1)
Test 1 : Response for delayed input
Let, y(n m) = Response for delayed input.
x(n) y(n − m) = x(n − m) + x(n − m − 1)
−m
x(n − m)
Input signal
z
Delayed input
H Response for
Delay System delayed input
2. 37 Digital Signal Processing
Test 2 : Delayed response
Let, yd(n) = Delayed response.
x(n) y(n) = x(n) + x(n −1) y d (n) = x(n − m ) + x(n − m − 1)
Input sign al
H z
−m
Example 2.11
Test the following systems for time invariance.
M N
a) y(n) = x(n) + B b) y(n) = n x3(n) c) y(n) = bx(n) d) y(n) = ∑
k = 0
bk x(n − k) − ∑
k =1
a k y(n − k)
Chapter 2 - Discrete Time Signals and Systems 2. 38
Solution
a) Given that, y(n) = x(n) + B
Test 1 : Response for delayed input
Let, y(n m) = Response for delayed input.
y (n − m ) = x (n − m ) + B
x (n) x (n − m )
−m
Input signa l
z H R espons e for
D elayed input
D elay S y stem delay ed inp ut
Test 2 : Delayed response
Let, yd(n) = Delayed response.
x (n) y (n) = x(n) + B y d (n) = x (n − m ) + B
H z
−m
Input signa l
z
D elayed input
H R espons e for
D elay S y stem delay ed inp ut
Test 2 : Delayed response
Let, yd(n) = Delayed response.
x(n − m)
x (n) y (n) = b
x(n) y d(n) = b
H
−m
z
Input signa l R espons e for D elayed res ponse
S y stem undelay ed input D elay
Input signa l
H z
−m
T he s ys tem , H is linear if an d only if, H{a 1 x 1(n ) + a 2 x 2 (n)} = a 1 H{x 1 (n)} + a 2 H{x 2 (n)}
Example 2.12
Test the following systems for linearity.
a) y(n) = n x(n) b) y(n) = x(n2) c) y(n) = x2(n) d) y(n) = B x(n) + C
Solution
a) Given that, y(n) = n x(n)
Let H be the system represented by the equation, y(n) = nx(n).
The system H operates on x(n) to produce, y(n).
x(n)
H y (n) = H{x (n)} = n x (n )
x 1 (n)
H y 1 (n ) = H {x 1 (n )} = n x 1 (n)
x 2 (n)
H y 2 (n ) = H {x 2 (n )} = n x 2 (n)
x 3 (n)
H y 3 (n ) = H {x 3 (n )}
\ y3(n) = H{a1 x1(n) + a2 x2(n)} = n[a1 x1(n) + a2 x2(n)] = a1 n x1(n) + a2 n x2(n) .....(2)
The condition to be satisfied for linearity is, y3(n) = a1 y1(n) + a2 y2(n).
From equations (1) and (2) we can say that, y3(n) = a1 y1(n) + a2 y2(n). Hence the system is linear.
x 1 (n)
y 1 (n ) = H {x 1 (n )} = x 1 (n )
2
H
x 2 (n)
y 2 (n ) = H {x 2 (n )} = x 2 (n )
2
H
x 3 (n)
H y 3 (n ) = H {x 3 (n )}
x 2 (n)
y 2 (n ) = H {x 2 (n )} = x 2 (n )
2
H
x 2 (n)
H y 2 (n ) = H{x 2 (n )} = B x 2 (n ) + C
\ y3(n) = H{a1 x1(n) + a2 x2(n)} = B[a1 x1(n) + a2 x2(n)] + C = Ba1 x1(n) + B a2 x2(n) + C .....(2)
The condition to be satisfied for linearity is, y3(n) = a1 y1(n) + a2 y2(n).
From equations (1) and (2) we can say that, y3(n) ¹ a1 y1(n) + a2 y2(n). Hence the system is nonlinear.
Chapter 2 - Discrete Time Signals and Systems 2. 42
Example 2.13
Test the following systems for linearity.
Solution
a) Given that, y(n) = ex(n)
Let, y1(n) and y2(n) be the response of the system H for inputs x1(n) and x2(n) respectively.
x 1 (n) x 1 (n )
H y 1 ( n ) = H { x 1(n )} = e
x 2 (n)
H y 2 ( n ) = H { x 2 ( n )} = e x 2 ( n )
\ y3(n) = H{a1 x1(n) + a2 x2(n)} = e[ a1 x1(n) + a 2 x 2 (n)] = ea1 x1(n) ea 2 x 2 (n) .....(2)
The condition to be satisfied for linearity is, y3(n) = a1 y1(n) + a2 y2(n).
From equations (1) and (2) we can say that, y3(n) ¹ a1 y1(n) + a2 y2(n). Hence the system is nonlinear.
Let, y1(n) and y2(n) be the response of the system H for inputs x1(n) and x2(n) respectively.
x 1 (n)
H y 1 ( n ) = H { x 1(n )} = b x 1 ( n )
x 2 (n) x 2 (n )
H y 2 ( n ) = H { x 2 ( n )} = b
Example 2.14
Test the following systems for linearity.
M N
1
g
a y(n) = 3 x(n) +
x(n − 2)
g
b y(n) = x(n) − 2 x(n − 1) g
c y(n) = ∑
m = 0
bm x(n − m) − ∑
m = 1
cm y(n − m)
Solution
1
a) Given that, y(n) = 3 x(n) +
x(n − 2)
1
Let, H be the system represented by the equation, y(n) = 3x(n) + .
x(n − 2)
The system H operates on x(n) to produce, y(n).
x (n) 1
H y ( n ) = H { x (n )} = 3 x (n ) +
x (n − 2 )
Consider two signals, x1(n) and x2(n).
Let, y1(n) and y2(n) be the response of the system H for inputs x1(n) and x2(n) respectively.
x 1 (n) 1
H y 1( n ) = H { x 1( n )} = 3 x 1(n ) +
x 1( n − 2 )
x 2(n) 1
H y 2 (n ) = H { x 2 ( n )} = 3 x 2 ( n ) +
x 2 (n − 2 )
Chapter 2 - Discrete Time Signals and Systems 2. 44
F
∴ a1 y1(n) + a 2 y 2(n) = a1 3x1(n) +
1 I F
+ a 2 3x 2(n) +
1 I .....(1)
GH x1(n − 2) JK GH x 2(n − 2) JK
Consider a linear combination of inputs, a1 x1(n) + a2 x2(n) = x3(n).
Let, y3(n) be the response for x3(n).
x 3 (n)
H y 3 (n ) = H {x 3 (n )}
1 .....(2)
\ y3(n) = H{a1 x1(n) + a2 x2(n)} = 3[a1 x1(n) + a 2 x 2(n)] +
a1 x1(n − 2) + a 2 x 2(n − 2)
The condition to be satisfied for linearity is, y3(n) = a1 y1(n) + a2 y2(n).
From equations (1) and (2) we can say that, y3(n) ¹ a1 y1(n) + a2 y2(n). Hence the system is nonlinear.
x 2 (n)
H y 2 (n ) = H {x 2 (n )} = x 2 (n ) − 2 x 2 (n − 1)
\ y3(n) = H{a1 x1(n) + a2 x2(n)}= a1 x1(n) + a2 x2(n) 2[a1 x1(n 1) + a2 x2(n 1)]
= a1 x1(n) a1 2 x1(n 1) + a2 x2(n) a2 2 x2(n 1) .....(2)
The condition to be satisfied for linearity is, y3(n) = a1 y1(n) + a2 y2(n).
From equations (1) and (2) we can say that, y3(n) = a1 y1(n) + a2 y2(n). Hence the system is linear.
M N
c) Given that, y(n) = ∑
m=0
bm x(n − m) − ∑
m=1
cm y(n − m)
m x(n − m) −
N
∑ cm y(n − m)
H for the input x(n) |W m=0 m=1
M N
y2(n) = H{x2(n)} = ∑
m =0
bm x 2 (n − m) − ∑
m = 1
cm y 2 (n − m)
2. 45 Digital Signal Processing
F b x (n − m) − c y (n − m)I
M N
∴ a1 y1(n) + a 2 y 2(n) = a1 GH ∑ m =0
m ∑ 1 JK m=1
m 1
F M
+ a G ∑ b x (n − m) − ∑ c y (n − m)J
I N
.....(1)
2 m 2 m 2
H m =0 K m =1
M M N
.....(2)
= a1 ∑ bm x1(n − m) + a 2 ∑ bm x 2 (n − m) − ∑ cm y 3(n − m)
m=0 m=0 m=1
M M N N
= a1 ∑
m = 0
bm x1(n − m) + a 2 ∑
m = 0
bm x 2(n − m) − a1 ∑
m = 1
cm y1(n − m) − a 2 ∑
m = 1
cm y 2(n − m)
F b
M N I F M N I .....(4)
= a1 GH ∑
m = 0
m x1(n − m) − ∑c
m = 1
m y1(n − m) + a 2 JK GH ∑
m = 0
bm x 2(n − m) − ∑
m = 1
cm y 2(n − m)JK
The condition to be satisfied for linearity is, y3(n) = a1 y1(n) + a2 y2(n).
From equations (1) and (4) we can say that the condition for linearity is satisfied. Therefore the system is
linear.
0
When n = 0, y(0) = ∑ x(k)
k = −∞
= ... x(2) + x(1) + x(0) Þ The response at n = 0, i.e., y(0) depends on the
present input x(0) and past inputs x(1), x(2),.....
1
= ... x(2) + x(1) + x(0) + x(1) Þ The response at n = 1, i.e., y(1) depends on the
present input x(1) and past inputs x(0), x(1), x(2),..
From the above analysis we can say that for any value of n, the system output depends on present and
past inputs. Hence the system is causal.
c) Given that, y(n) = b x(n)
When n = 0, y(0) = b x(0) Þ Þ The response at n = 0, i.e., y(0) depends on the present input x(0).
When n = 1, y(1) = b x(1) Þ Þ The response at n = 1, i.e., y(1) depends on the present input x(1).
From the above analysis we can say that the response for any value of n depends on the present input.
Hence the system is causal.
d) Given that, y(n) = n x(n)
When n = 0, y(0) = 0 ´ x(0) Þ The response at n = 0, i.e., y(0) depends on the present input x(0).
When n = 1, y(1) = 1 ´ x(1) Þ The response at n = 1, i.e., y(1) depends on the present input x(1).
When n = 2, y(2) = 2 ´ x(2) Þ The response at n = 2, i.e., y(2) depends on the present input x(2).
From the above analysis we can say that the response for any value of n depends on the present input.
Hence the system is causal.
Example 2.16
Test the causality of the following systems.
a) y(n) = x(n) + 2 x(n + 3) b) y(n) = x(n2) c) y(n) = x(3n) d) y(n) = x(n)
Solution
a) Given that, y(n) = x(n) + 2 x(n + 3)
When n = 0, y(0) = x(0) + 2 x(3) Þ The response at n = 0, i.e., y(0) depends on the
present input x(0) and future input x(3).
2. 47 Digital Signal Processing
When n = 1, y(1) = x(1) + 2 x(4) Þ Þ The response at n = 1, i.e., y(1) depends on the
present input x(1) and future input x(4).
From the above analysis we can say that the response for any value of n depends on present and future
inputs. Hence the system is noncausal.
The term bounded output refers to finite and predictable output for any value of n. Hence if output
y(n) is bounded then there exists a constant My such that |y(n)| £ My and My < ¥ , for all n.
In general, the test for stability of the system is performed by applying specific input. On applying a
bounded input to a system if the output is bounded then the system is said to be BIBO stable.For LTI (Linear
Time Invariant) systems the condition for BIBO stability can be transformed to a condition on impulse
response as shown below.
Condition for Stability of LTI System
The condition for stability of an LTI system is,
+∞
∑ h( n ) < ∞ .....(2.24)
n =−∞
i.e., an LTI system is stable if the impulse response is absolutely summable.
Chapter 2 - Discrete Time Signals and Systems 2. 48
Proof
Let, x(n) = Input to LTI system.
y(n) = Response of LTI system for the input x(n).
Now, by convolution sum formula,
y(n) = x(n) * h(n) = h(n) * x(n) Convolution satisfy
commutative property.
+∞
= ∑
m = −∞
h(m) x( n − m)
+∞ Taking absolute
∴ y(n) = ∑ h(m) x( n − m) value on both sides.
m =−∞
+∞
For linear system the order summation
= ∑ h(m) x( n − m) and absolute value can be interchanged.
m = −∞
+∞
For linear system the order of multiplication
= ∑ h(m) x( n − m)
and absolute value can be interchanged.
m = −∞
+∞
= ∑ h(m) M X If input is bounded, then
|x(n m)| = constant = MX
m = −∞
+∞
= MX ∑ h(m) MX is indepentent of
m =−∞ summation index m.
+∞
= MX ∑ h( n) Change index m to n.
n = −∞
Example 2.17
Test the stability of the following systems.
a) y(n) = cos[x(n)] b) y(n) = x(n 3) c) y(n) = n x(n)
Solution
a) Given that, y(n) = cos [x(n)]
The given system is a nonlinear system, and so the test for stability should be performed for specific inputs.
The value of cos q lies between 1 to +1 for any value of q. Therefore the output y(n) is bounded for any
value of input x(n). Hence the given system is stable.
b) Given that, y(n) = x(n 3)
The given system is a time variant system, and so the test for stability should be performed for specific
inputs.
The operations performed by the system on the input signal are folding and shifting. A bounded input
signal will remain bounded even after folding and shifting. Therefore in the given system, the output will be
bounded as long as input is bounded. Hence the given system is BIBO stable.
c) Given that, y(n) = n x(n)
The given system is a time variant system, and so the test for stability should be performed for specific
inputs.
2. 49 Digital Signal Processing
Case i : If x(n) tends to infinity or constant, as "n" tends to infinity, then y(n) = n x(n) will be infinite as "n"
tends to infinity. So the system is unstable.
Case ii : If x(n) tends to zero as "n" tends to infinity, then y(n) = n x(n) will be zero as "n" tends to infinity.
So the system is stable.
Example 2.18
Determine the range of values of "p" and "q" for the stability of LTI system with impulse response,
h(n) = pn ; n < 0
= qn ; n ≥ 0
Solution
∞
n= 0
n
= ∑p
n=1
−n
+ ∑
n=0
qn
∞ ∞ ∞ ∞ n is always positive.
1 1 n
= ∑
n=1
+
pn n= 0 ∑
qn = ∑
n =1 p
n
+ ∑
n= 0
q
n
∞ F 1I ∞
n |p|0 = 1
= ∑ GH p JK
n=0
− 1+ ∑
n= 0
q
The summation of infinite terms in the above equation converges if, 0 < 1/|p| < 1 and 0 < |q| < 1. Hence
by using infinite geometric series formula,
+∞
1 1 Infinite geometric
∑
|h(n)| =
1
−1+
1 − | q| series sum formula
n = −∞ 1−
p ∞
1
Cn = ∑
= constant 1 − C
n = 0
Therefore, the system is stable if |p| > 1 and |q| < 1. if 0 < C < 1
Example 2.19
Test the stability of LTI systems, whose impulse responses are,
Solution
a) h(n) = 0.2n u(n)
+∞ +∞ ∞ Infinite geometric
∴ ∑ h(n) = ∑ 0.2n u(n) = ∑ 0.2n series sum formula
n= −∞ n = −∞ n= 0
∞
1 1
= = 1. 25 ∑ Cn =
1 − 0.2 n = 0
1− C
+∞ if 0 < C < 1
Since, ∑ h(n) < ∞, system is stable.
n= −∞
Chapter 2 - Discrete Time Signals and Systems 2. 50
b) h(n) = 0.3n u(n) + 2n u(n)
+∞ +∞
∴ ∑ h(n) = ∑ 0.3n u(n) + 2n u(n)
n= −∞ n = −∞ ∞
∞
n
∞
n 1 ∑ Cn = ∞
= ∑ 0.3 + ∑ 2 u(n) =
1 − 0.3
+∞=∞ n = 0
if C > 1
n=0 n= 0
+∞
Since, ∑ h(n) = ∞, system is unstable.
n= −∞
c) h(n) = 4n u(-
-n)
+∞ +∞ 0 +∞
∴ ∑ h(n) = ∑ 4n u( −n) = ∑ 4n = ∑ 4−n
n = −∞ n = −∞ n = −∞ n= 0
∞ ∞ n ∞
=
1
∑ 4n = ∑ GH 4 JK
F 1I = ∑ 0.25 n
=
1
= 1. 3333
n=0 n= 0 n= 0
1 − 0.25
+∞
Since, ∑ h(n) < ∞ , system is stable.
n= −∞
+∞ +∞
∴ ∑ h(n) = ∑ 0.2n u( −n) + 3n u( −n)
n= −∞ n= −∞
0 0 +∞ +∞
= ∑ 0.2n + ∑ 3n = ∑ 0.2−n + ∑ 3−n
n= −∞ n= −∞ n= 0 n=0
∞ ∞ ∞ n ∞ n
= ∑
1
+
1
= ∑
1
∑ GH
F IJ + ∑ FG 1IJ
n=0 0.2n n=0 3n n=0 0.2 K H 3K n=0
∞ ∞
n n 1
= ∑5 +∑ 0.333 = ∞ +
1 − 0.333
=∞
n=0 n= 0
+∞
Since, ∑ h(n) = ∞, system is unstable.
n= −∞
+∞
.....(2.31)
∴ x3 ( q ) = ∑ x1( m) x2 (q − m)
m =−∞
The evaluation of equation (2.31) to determine the value of x3(n) at n = q, involves the following five
steps.
1. Change of index : Change the index n in the sequences x 1 (n) and x 2(n), to get the
sequences x1(m) and x2(m).
2. Folding : Fold x2(m) about m = 0, to obtain x2(-m).
3. Shifting : Shift x2(-m) by q to the right if q is positive, shift x2(-m) by q to the left
if q is negative to obtain x2(q - m).
4. Multiplication : Multiply x1(m) by x2(q - m) to get a product sequence. Let the product
sequence be vq(m). Now, vq(m) = x1(m) × x2(q - m).
5. Summation : Sum all the values of the product sequence vq(m) to obtain the value of
x3(n) at n = q. [i.e., x3(q)].
The above procedure will give the value of x3(n) at a single time instant say n = q. In general, we are
interested in evaluating the values of the sequence x3(n) over all the time instants in the range -¥ < n < ¥ .
Hence the steps 3, 4 and 5 given above must be repeated, for all possible time shifts in the range
-¥ < n < ¥ .
Convolution of finite duration sequences
In convolution of finite duration sequences it is possible to predict the length of resultant sequence.
If the sequence x1(n) has N1 samples and sequence x2(n) has N2 samples then the output sequence
x3(n) will be a finite duration sequence consisting of "N1+N2–1" samples.
i.e., if, Length of x1(n) = N1
Length of x2(n) = N2
then, Length of x3(n) = N1 + N2 – 1
In the convolution of finite duration sequences it is possible to predict the start and end of the
resultant sequence. If x1(n) starts at n = n1 and x2(n) starts at n = n2 then, the initial value of n for x3(n) is
"n = n1 + n2". The value of x1(n) for n < n1 and the value of x2(n) for n < n2 are then assumed to be zero.The final
value of n for x3(n) is "n = (n1 + n2) + (N1 + N2 – 2)".
i.e., if, x1(n) start at n = n1
x2(n) start at n = n2
then, x3(n) start at n = n1 + n2
and x3(n) end at n = (n1 + n2) + (N1 + N2 – 1) – 1
= (n1 + n2) + (N1 + N2 – 2)
In equation (2.32) each product x(m) d(n – m) is an impulse and the summation of impulses gives the
sequence x(n).
From equation (2.32) we know that the signal x(n) can be expressed as a summation of impulses,
+∞
.....(2.35)
i.e., x(n) = ∑
m = −∞
x(m) δ(n − m)
y(n) = H
|RS ∑
+∞
x(m) δ(n − m)
|UV .....(2.36)
|T
m = −∞ |W
The system H is a function of n and not a function of m. Hence by linearity property the equation
(2.36) can be written as,
+∞
.....(2.37)
y(n) = ∑
m = −∞
x(m) H {δ(n − m)}
Let the response of the LTI system to the unit impulse input d(n) be denoted by h(n),
\ h(n) = H{d(n)}
Then by time invariance property the response of the system to the delayed unit impulse input
d(n m) is given by,
h(n m) = H{d(n m)} .....(2.38)
Using equation (2.38), the equation (2.37) can be expressed as,
+∞
y( n) = ∑
m = −∞
x( m) h(n − m)
The above equation represents the convolution of input x(n) with the impulse response h(n) to yield
the output y(n). Hence it is proved that the response y(n) of LTI discrete time system for an
arbitrary input x(n) is given by convolution of input x(n) with impulse response h(n) of the system.
+∞
∴ y2(n − m) = ∑
q = −∞
x1( q) x2(n − q − m) .....(2.43)
+∞ +∞
= ∑
p = −∞
∑
m = −∞
x1( m) x 2(p− m) x 3 (n − p) Using equation (2.41)
+∞ +∞
= ∑
m = −∞
x1(m) ∑
p = −∞
x 2 (p − m) x 3(n − p) .....(2.44)
Let, p m = q when p = ¥ , q = p m = ¥ m = ¥
\p=q+m when p = +¥ , q = p m = +¥ m = +¥
On replacing (p m) by q, and p by (q + m) in the equation (2.44) we get,
+∞ +∞
LHS = ∑ x1( m) ∑ x 2( q) x 3 ( n − q − m)
m = −∞ q = −∞
+∞
= ∑ x1( m) y2 ( n − m) Using equation (2.43)
m = −∞
= x1 (n) * y2(n)
= x1(n) * [x2(n) * x3(n)] Using equation (2.42)
= RHS
Chapter 2 - Discrete Time Signals and Systems 2. 56
Proof of Distributive Property :
Consider the discrete time signals x1(n), x2(n) and x3(n). By distributive property we can write,
x1 (n) * [x2(n) + x3(n)] = [x1(n) * x2 (n)] + [x1(n) * x3 (n)]
LHS RHS
LHS = x1(n) * [x2(n) + x3(n)]
= x1(n) * x4(n) x4(n) = x2(n) + x3(n)
+∞
= ∑
m = −∞
x1( m) x 4(n − m) m is a dummy variable used for convolution operation.
+∞
x4(n m) = x2(n m) + x3(n m)
= ∑
m = −∞
x1( m) [x 2( n − m) + x 3(n − m)]
+∞ +∞
= ∑
m = −∞
x1( m) x 2(n − m) + ∑
m = −∞
x1( m) x 3(n − m)
h 2 (n)
Example 2.20
Determine the impulse response for the cascade of two LTI systems having impulse responses,
n n
h1(n) =
FG 2IJ u(n) and h2 (n) =
FG 1IJ u(n).
H 5K H 5K
Solution
Let h(n) be the impulse response of cascade system. Now h(n) is given by convolution of h1(n) and h2(n).
+∞
\ h(n) = h1(n) * h2(n) = ∑
m = −∞
h1(m) h2 (n − m)
Example 2.21
Determine the overall impulse response of the interconnected discrete time systems shown below,
a) b)
n n
h1(n) =
FG 1IJ u(n); h2 (n) =
FG 1IJ u(n); h1(n) = an u(n) ; h2 (n) = δ(n − 1) ; h3 (n) = δ(n − 2)
H 3K H 2K
n
F 1I
h (n) = G J u(n)
3
H 5K
Solution
a) The given system can be redrawn as shown below.
h1(n)
y(n)
+
x(n)
h1(n)
+ h 3 (n)
h2 (n)
The above system can be reduced to single equivalent system as shown below.
y1(n)
h1(n)
y(n)
x(n) h1(n) + [(h1(n) + h2 (n)) ∗ h 3 (n)] y(n)
x(n)
+ ⇒
⇓
h1(n) + h2 (n) h 3 (n)
x(n) h(n) y(n)
The product of h1(m) h3(n m) will be nonzero in the range 0 £ m £ n. Therefore the summation index in
the above equation can be changed to m = 0 to n.
n
∴ h1(n) ∗ h3(n) = ∑ h (m) h (n
m = 0
1 3 − m)
n m n − m n m n −m
∑ FGH 3IJK FGH 5IJK ∑ FGH 3IJK FGH 5IJK FGH 5IJK
1 1 1 1 1
= =
m = 0 m = 0
n n m n n m
=
FG 1IJ ∑ FG 1IJ 5m =
FG 1IJ ∑ FG 5IJ
H 5K H 3K
m = 0
H 5K H 3K
m = 0
2. 59 Digital Signal Processing
n +1
FG 5IJ − 1 n Using finite geometric series sum formula.
F 1I H 3 K
∴ h (n) ∗ h (n) = G J
1 3
H 5K 5 − 1 Finite geometric series
3
n sum formula
FG 5IJ 5 − 1
n LM 3 FG 5IJ 5 − 3 OP
n n N
CN+1 − 1
1I H 3 K 3
F
=G J
F 1I
H 5K 5 − 3 = GH 5JK ∑ Cm =
C −1
3
MN 2 H 3K 3 2 PQ m = 0
n n n n n
=
FG 1IJ
5 FG 5IJ − 3 FG 1IJ = 5 FG 1IJ − 3 FG 1IJ ; for n ≥ 0
H 5K
2 H 3 K 2 H 5K 2 H 3K 2 H 5K
n n
5 F 1I 3 F 1I
= G J u(n) − G J u(n) ; for all n
2 H 3K 2 H 5K
The product of h2(m) and h3(nm) will be nonzero in the range 0 £ m £ n. Therefore the summation index
in the above equation can be change to m = 0 to n.
n
∴ h2 (n) ∗ h3 (n) = ∑
m = 0
h2 (m) h3(n − m)
n m n − m n m n −m
= ∑
FG 1IJ FG 1IJ = ∑
FG 1IJ FG 1IJ FG 1IJ Finite geometric series
m = 0
H 2K H 5 K m = 0
H 2K H 5K H 5K sum formula
n m n m N
FG 1IJ n
F 1I FG 1IJ ∑ FG 5IJ n
CN+1 − 1
=
H 5K ∑ GH 2JK 5 m
=
H 5K H 2K ∑
m = 0
Cm =
C −1
m = 0 m = 0
n + 1
n
FG 5IJ − 1
= GHF 51IJK H 2K Using finite geometric series sum formula.
5
−1
2
n
F 5I 5
=
FG 1IJ GH 2JK 2 − 1 = FG 1IJ LM 2 FG 5IJ 5 − 2 OP
n n n
H 5K 5 − 2 H 5K MN 3 H 2K 2 3 PQ
2
n n n n n
= G J G J − 32 FGH 51IJK = 35 FGH 21IJK − 32 FGH 51IJK
5 F 1I F 5 I
3 H 5K H 2K
for n ≥ 0
n n
5 F 1I
= G J u(n) − 32 FGH 51IJK u(n) for all n
3 H 2K
Now, the overall impulse response h(n) is given by,
=
LM 7 FG 1IJ − 13 FG 1IJ + 5 FG 1IJ OP u(n)
n n n
MN 2 H 3K 6 H 5K 3 H 2K PQ
Chapter 2 - Discrete Time Signals and Systems 2. 60
b) The given system can be reduced to single equivalent system as shown below.
h1(n) ∗ h 2 (n)
x(n) y(n)
+
h3 (n) ∗ h1(n)
⇓
x(n) [h1(n) ∗ h2 (n)] + [h 3 (n) ∗ h1(n)] y(n)
⇓
x(n) h(n) y(n)
∞
= ∑
m = −∞
h2 (m) h1(n − m) Using commutative property.
∞ ∞
= ∑
m = −∞
δ(m − 1) a(n − m) = ∑
m = −∞
δ(m − 1) an a −m
∞
=a n
∑
m = −∞
δ(m − 1) a −m
The product of d(m 1) and am in the above equation will be nonzero only when m = 1.
∞ ∞
= ∑
m = −∞
δ(m − 2) a (n − m) = ∑
m = −∞
δ(m − 2) an a −m
∞
=a n
∑ δ(m − 2) a −m
m = −∞
The product of d(m 2) and am in the above equation will be nonzero only when m = 2.
Let x1(n) and x2(n) be the input sequences and x3(n) be the output sequence.
1. Change the index "n" of input sequences to "m" to get x1(m) and x2(m).
2. Sketch the graphical representation of the input sequences x1(m) and x2(m).
3. Let us fold x 2 (m) to get x 2(–m). Sketch the graphical representation of the folded
sequence x2(–m).
4. Shift the folded sequence x2(–m) to the left graphically so that the product of x1(m) and
shifted x2(–m) gives only one nonzero sample. Now multiply x1(m) and shifted x2(–m) to get
a product sequence, and then sum up the samples of product sequence, which is the first
sample of output sequence.
5. To get the next sample of output sequence, shift x2(–m) of previous step to one position right
and multiply the shifted sequence with x1(m) to get a product sequence. Now the sum of the
samples of product sequence gives the second sample of output sequence.
2. To get subsequent samples of output sequence, the step 5 is repeated until we get a nonzero
product sequence.
Method 2: Tabular Method
The tabular method is same as that of graphical method, except that the tabular representation of the
sequences are employed instead of graphical representation. In tabular method, every input sequence, folded
and shifted sequence is represented by a row in a table.
Method 3: Matrix Method
Let x1(n) and x2(n) be the input sequences and x3(n) be the output sequence. In matrix method one of
the sequences is represented as a row and the other as a column as shown below.
Multiply each column element with row elements and fill up the matrix array.
Now the sum of the diagonal elements gives the samples of output sequence x3(n). (The sum of the
diagonal elements are shown below for reference).
x 2 (0) x 2 (1) x 2 (2) x 2 (3)
......
Example 2.22
Determine the response of the LTI system whose input x(n) and impulse response h(n) are given by,
x(n) = {1, 2, 0.5, 1} and h(n) = {1, 2, 1, 1}
- -
Solution
The response y(n) of the system is given by convolution of x(n) and h(n).
+∞
y(n) = x(n) ∗ h(n) = ∑
m = −∞
x(m) h(n − m)
x (m ) h (m ) h ( −m )
2 2 2
1 1 1 1 1 1
0.5
0 1 2 3 m −1 0 1 2 m −2 −1 0 1 m
−1 −1
F ig 1 : In p u t sequ e n ce. F ig 2 : Im p u lse resp o n se . F ig 3 : F o ld ed im p ulse respo nse.
The computation of each sample using the above equation are graphically shown in fig 4 to fig 10. The
graphical representation of output sequence is shown in fig 11.
2. 63 Digital Signal Processing
+∞ +∞ +∞
When n = −1 ; y(−1) = ∑
m = −∞
x(m) h( −1 − m) = ∑
m = −∞
x(m) h−1(m) = ∑
m = −∞
v −1(m)
h −1 (m ) x (m ) v −1 (m )
2
X 2 ⇒
1 1 1 1 1
0.5
−3 −2 −1 0 m 0 1 2 3 m −3 −2 −1 0 1 2 3 m
T he s um of pro du c t s e qu en c e v −1(m )
−1 F ig 4 : C o m p u ta tio n of y ( −1 ).
g iv e s y ( −1 ). ∴ y ( −1) = 1
+∞ +∞ +∞
When n = 0 ; y(0) = ∑
m = −∞
x(m) h(0 − m) = ∑
m = −∞
x(m) h0 (m) = ∑
m = −∞
v 0 (m)
h 0 (m ) x (m ) v 0 (m )
2 2 2
X 2 ⇒
1 1 1 1
0.5
−2 −1 0 1 m 0 1 2 3 m −2 −1 0 1 2 3 m
T h e s u m o f p rod uc t s eq ue nc e v 0 ( m )
−1 F ig 5 : C o m p u ta tion of y (0 ).
giv es y(0 ) . ∴ y (0) = 2 + 2 = 4
+∞ +∞ +∞
When n = 1 ; y(1) = ∑
m = −∞
x(m) h(1 − m) = ∑
m = −∞
x(m) h1(m) = ∑
m = −∞
v1(m)
h 1 (m ) x (m ) v 1 (m )
4
X ⇒
2 2
1 1 1 1 1
0.5 0.5
−1 0 1 2 m 0 1 2 3 m −1 0 1 2 3 m
−1 T he s um of pro du c t s e qu en c e v 1 (m )
F ig 6 : C o m p u ta tio n of y (1 ).
g iv e s y (1). ∴ y(1 ) = 1 + 4 + 0.5 = 5 .5
+∞ +∞ +∞
When n = 2 ; y(2) = ∑
m = −∞
x(m) h(2 − m) = ∑
m = −∞
x(m) h2 (m) = ∑
m = −∞
v 2 (m)
h 2 (m ) x (m ) v 2 (m )
X ⇒
2 2
2
1 1 1 1 1 1
0.5
0 1 2 3 m 0 1 2 3 m 0 1 2 3 m
−1
−1 T he s um of pro du c t s e qu en ce v 2 (m )
F ig 7 : C o m p u ta tio n of y (2 ). g iv e s y (2). ∴ y (2 ) = −1 + 2 + 1 + 1 = 3
Chapter 2 - Discrete Time Signals and Systems 2. 64
+∞ +∞ +∞
When n = 3 ; y(3) = ∑
m = −∞
x(m) h(3 − m) = ∑
m = −∞
x(m) h3 (m) = ∑
m = −∞
v 3 (m)
h 3 (m ) x (m ) v 3 (m )
X ⇒
2 2
2
1 1 1 1
0.5 0.5
1 2 3 4 m 2 m
0 0 1 3 0 1 2 3 4 m
−1
−2
F ig 8 : C o m p u ta tio n of y (3 ). T he su m o f pro du ct s e qu en ce v 3 (m )
giv es y (3). ∴ y (3) = −2 + 0.5 + 2 = 0 .5
+∞ +∞ +∞
When n = 4 ; y(4) = ∑
m = −∞
x(m) h(4 − m) = ∑
m = −∞
x(m) h4 (m) = ∑
m = −∞
v 4 (m)
h 4 (m ) x (m ) v 4 (m )
2 X ⇒
2
1 1
1 1 1
0.5
0 1 2 3 4 5 m
−1
0 1 2 3 m 0 1 2 3 4 5 m
−0.5
T h e s u m o f p rod uc t s eq ue nc e v 4 (m )
F ig 9 : C o m p u ta tio n of y (4 ).
give s y(4 ). ∴ y (4 ) = −0 .5 + 1 = 0 .5
+∞ +∞ +∞
When n = 5 ; y(5) = ∑
m = −∞
x(m) h(5 − m) = ∑
m = −∞
x(m ) h5 (m) = ∑
m = −∞
v 5 (m)
h 5 (m ) x (m ) v 5 (m )
2 X 2
⇒
1 1 1 1
0.5
0 1 2 3 4 5 6 m 0 1 2 3 m 0 1 2 3 4 5 6 m
−1
−1
F ig 1 0 : C o m p u ta tio n of y (5 ). T h e s um of p rod uc t s eq ue nc e v 5 (m )
g ive s y(5 ). ∴ y (5 ) = −1
y (n )
The output sequence, y(n) = {1, 4, 5.5, 3, 0.5, 0.5, − 1
A
} 5.5
1
0.5 0.5
−2 −1 0 1 2 3 4 5 6 7 n
−1
F ig 11 : G ra ph ica l rep resen ta tio n of y (n ).
2. 65 Digital Signal Processing
Method 2 : Tabular Method
The given sequences and the shifted sequences can be represented in the tabular array as shown below.
m 3 2 1 0 1 2 3 4 5 6
x(m) 1 2 0.5 1
h(m) 1 2 1 1
h(m) 1 1 2 1
h(1 m) = h1(m) 1 1 2 1
h(0 m) = h0(m) 1 1 2 1
h(1 m) = h1(m) 1 1 2 1
h(2 m) = h2(m) 1 1 2 1
h(3 m) = h3(m) 1 1 2 1
h(4 m) = h4(m) 1 1 2 1
h(5 m) = h5(m) 1 1 2 1
Each sample of y(n) is computed using the convolution formula,
+∞ +∞
y(n) = ∑ x(m) h(n − m)
m = −∞
= ∑ x(m) h (m),
m = −∞
n where hn (m) = h(n − m)
To determine a sample of y(n) at n = q, multiply the sequence x(m) and hq(m) to get a product sequence
(i.e., multiply the corresponding elements of the row x(m) and hq(m)). The sum of all the samples of the product
sequence gives y(q).
3
When n = −1 ; y( −1) = ∑
m = −3
x(m) h −1(m) Q The product is valid only for m = −3 to + 3.
h(n) h(n)
x(n) 1 2 1 −1 x(n) 1 2 1 −1
1 1 2 1 −1
1 1 ×1 1 ×2 1 ×1 1 × (−1)
2 2 4 2 −2
2 2 ×1 2×2 2 ×1 2 ×(−1) ⇒
0.5 0.5 1 0.5 −0.5
0.5 0.5 × 1 0.5 × 2 0.5 × 1 0.5 × (−1)
1 1 2 1 −1
1 1 ×1 1×2 1 ×1 1 × (−1)
Example 2.23
Determine the output y(n) of a relaxed LTI system with impulse response,
h(n) = an u(n) ; where |a| < 1 and
When input is a unit step sequence, i.e., x(n) = u(n).
Solution
The graphical representation of x(n) and h(n) after replacing n by m are shown below. Also the sequence
x(m) is folded to get x(m).
h (m ) x (m ) x ( −m )
1 1 1
a
2
a
3
a
0 1 2 3 m 0 1 2 3 m −3 −2 −1 0 m
F ig 1 : Im p u lse resp o n se. F ig 2 : Im p u lse sequ en ce. F ig 3 : F o ld ed inp u t sequ en ce.
Here both h(m) and x(m) are infinite duration sequences starting at n = 0. Hence the output sequence y(n)
will also be an infinite duration sequence starting at n = 0.
By convolution formula,
∞ ∞
y(n) = ∑ h(m) x(n − m) = ∑ h(m) x (m) ;
m = −∞ m =0
n where xn (m) = x(n − m)
The computation of some samples of y(n) using the above equation are graphically shown below.
2. 67 Digital Signal Processing
∞ ∞ ∞
When n = 0 ; y(0) = ∑
m = 0
h(m) x(0 − m) = ∑
m = 0
h(m) x 0 (m) = ∑
m = 0
v 0 (m)
h (m ) x 0 (m ) v 0 (m )
1 1 1
a
a
2
X ⇒
3
a
0 1 2 3 m −3 −2 −1 m 0 1 2
0 1 m
F ig 4 : C o m p u ta tio n of y (0 ). y (0) = 1
∞ ∞ ∞
When n = 1 ; y(1) = ∑
m = 0
h(m) x(1 − m) = ∑
m = 0
h(m) x 1(m) = ∑
m = 0
v1(m)
h (m ) x 1 (m ) v 1 (m )
1 1 1
a a
a
2 X ⇒
3
a
0 1 2 3 m −2 −1 m
0 1 −1 0 1 2 m
y (1) = 1 + a
F ig 5 : C o m p u ta tio n of y (1 ).
∞ ∞ ∞
When n = 2 ; y(2) = ∑
m = 0
h(m) x(2 − m) = ∑
m = 0
h(m) x 2 (m) = ∑
m = 0
v 2 (m)
h (m ) x 2 (m ) v 2 (m )
1 1 1
a a
2
a ⇒ a
2
a
3 X
0 1 2 3 m −1 0 1 2 m 0 1 2 3 m
2
y(2) = 1 + a +a
F ig 6 : C o m p u ta tio n of y (2 ).
Solving similarly for other values of n, we can write y(n) for any value of n as shown below.
n
y(n) = 1 + a + a 2 +......+ an = ∑a
p=0
p
; for n ≥ 0
y (n )
3
1+a+a +a
2
1 + a + a2
1+a
0 1 2 3 m
F ig 7 : G ra ph ica l rep rese n ta tio n o f y (n).
Chapter 2 - Discrete Time Signals and Systems 2. 68
3 3 3 3
2 2 2 2
1 1 1 1
0 1 2 3 n −4 −3 −2 −1 0 1 2 3 4 5 6 7 n
F ig 2.2 4 a : F in ite d u ra tio n seq u en c e x(n ). F ig 2.2 4 b : P erio d ic e xten sio n o f x (n ).
F ig 2.2 4 : A fin ite d u ra tion seq ue n ce a n d its p erio d ic e xten sio n .
Let us delay the periodic sequence xp(n) by two units of time as shown in fig 2.25(a). (For delay the
sequence is shifted right). Let us denote one period of this delayed sequence by x1(n). One period of the
delayed sequence is shown in fig 2.25(b).
x p (n −2 )
x 1 (n ) x1 (n) = xp ((n − 2))4
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
−2 −1 0 1 2 3 4 5 6 7 8 9 n 0 1 2 3 n
F ig 2 .2 5 a: x p (n ) d e la y ed b y tw o un its o f tim e. F ig 2 .2 5 b: O ne period of x p (n −2 ).
F ig 2 .2 5 : D elay ed versio n o f x p (n).
The sequence x1(n) can be represented by xp(n – 2, (mod 4)), or xp((n – 2))4, where mod 4 indicates that
the sequence repeats after 4 samples. The relation between the original sequence x(n) and one period of the
delayed sequence x1(n) are shown below.
x (1) = 2 x 1 (1) = 4
3 1 ⇒2 4 ⇒1 3
x (n) 4 3 2
x (2) = 3 x (0) = 1 x 1 (2) = 1 x 1 (n) x 1 (0) = 3
R otate x p(n) antic loc kw ise tw o tim es to get x 1(n)
= x p ((n − 2)) 4
x (3) = 4 x 1 (3) = 2
F ig 2.2 6 a: C ircu la r rep rese n ta tio n o f x (n). F ig 2.2 6 b: C ircu la r rep rese n ta tio n o f x 1 (n ).
F ig 2.2 6 : C ircu la r rep rese n ta tio n o f a sig n a l a nd its dela yed version .
Let us advance the periodic sequence xp(n) by three units of time as shown in fig 2.27(a). Let us denote
one period of this advanced sequence by x2(n). One period of the advanced sequence is shown in fig 2.27(b).
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
−3 −2 −1 0 1 2 3 4 5 6 7 8 n 0 1 2 3 n
F ig 2 .2 7 a: x p (n ) a d v an c ed by th ree u n its o f tim e. F ig 2 .2 7 b: O ne p e rio d of x p (n + 3 ).
F ig 2 .2 7 : A d va n c ed v ersion of x p (n ).
The sequence x2(n) can be represented by xp(n + 3, (mod 4)) or xp((n + 3))4, where mod 4 indicates that the
sequence repeats after 4 samples. The relation between the original sequence x(n) and one period of the
advanced sequence x2(n) are shown below.
x2(n) = xp(n + 3, (mod 4)) = xp((n + 3))4
\ When n = 0; x2(0) = xp((0 + 3))4 = xp((3))4 = x(3) = 4
When n = 1; x2(1) = xp((1 + 3))4 = xp((4))4 = x(0) = 1
When n = 2; x2(2) = xp((2 + 3))4 = xp((5))4 = x(1) = 2
When n = 3; x2(3) = xp((3 + 3))4 = xp((6))4 = x(2) = 3
The periodic sequences xp(n) and x2(n) can be represented as points on a circle as shown in fig 2.28.
From fig 2.28 we can say that x2(n) is simply xp(n) shifted circularly by three units in time where clockwise
direction has been selected for left shift or advance.
2 3 4 1
x (1) = 2 x 2 (1) = 1
3 1 4 2 ⇒1 3 ⇒2 4
x p (n) 4 1 2 3 x 2 (n)
x (2) = 3 x (0) = 1 x 2 (2) = 2 x 2 (0) = 4
R otate x p(n) cloc k w is e three tim es to get x 2(n)
x (3) = 4 x 2 (3) = 3
F ig 2.2 8 a: C ircu la r rep rese nta tio n o f x (n). F ig 2.2 8 b: C ircu la r rep rese nta tio n o f x 2 (n ).
F ig 2.2 8 : C ircu la r rep rese nta tio n o f a sig n a l a n d its ad v a nced versio n.
Chapter 2 - Discrete Time Signals and Systems 2. 70
Thus we conclude that a circular shift of an N-point sequence is equivalent to a linear shift of its
periodic extension and viceversa. If a nonperiodic N-point sequence is represented on the circumference of
a circle then it becomes a periodic sequence of periodicity N. When the sequence is shifted circularly, the
samples repeat after N shifts. This is similar to modulo-N operation. Hence, in general, the circular shift may
be represented by the index mod-N. Let x(n) be an N-point sequence represented on a circle and x¢(n) be its
circularly shifted sequence by m units of time.
Now, x¢(n) = x(n – m, mod N) º x((n – m))N ..... (2.53)
When m is positive, the equation (2.53) represents delayed sequence and when m is negative, the
equation (2.53) represents advanced sequence.
1
3
3
MMx M(2) x (1M)
2 2 x 2 ( 0)
M
..... x 2 ( 4)
M
x (3)
2
M
PP × MM M PP = MM M PP
MMx (N − 2) x ( N − 3) x2 ( N − 4) ..... x 2 ( 0) x ( N − 1) P
MM M PP MM M PP
2 2 2
MNx (N − 1) x ( N − 2) x 2 ( N − 3) ..... x 2 (1) x (0)
PP Mx (N − 2)P M x ( N − 2)P
1 3
2 2 2 Q MNx (N − 1) PQ MN x ( N − 1) PQ
1 3
Example 2.24
Perform circular convolution of the two sequences, x1(n) = {2, 1, 2, 1} and x2(n)= {1, 2, 3, 4}
- -
Solution
Method 1:Graphical Method of Computing Circular Convolution
Let x3(n) be the sequence obtained by circular convolution of x1(n) and x2(n).
The circular convolution of x1(n) and x2(n) is given by,
N − 1 N − 1
x3(n) = ∑
m = 0
x1(m) x 2((n − m))N = ∑ x (m) x
m = 0
1 2,n (m)
where x 2,n (m) = x 2((n − m))N and m is the dummy variable used for convolution.
The index n in the given sequences are changed to m and each sequence is represented as points on a
circle as shown below. The folded sequence x2(m) and circularly shifted sequences x2(n m) are also represented
on the circle.
x 1 (1) = 1 x 2 (1) = 2 x 2 (3) = 4
F ig 1 . F ig 2 . F ig 3 .
4 1 2 3
2 3 4 1
F ig 4 : C ircula rly sh ifted seq u en c es x 2 ( −m ) fo r n = 0 , 1 , 2 , 3 .
Chapter 2 - Discrete Time Signals and Systems 2. 74
The given sequences are 4-point sequences . \ N = 4.
Each sample of x3(n) is given by sum of the samples of product sequence defined by the equation,
3 3
x3 (n) = ∑
m = 0
x1(m) x 2,n (m) = ∑
m = 0
vn (m) ; where vn (m) = x1(m) x 2,n (m) .....(1)
Using the above equation (1), graphical method of computing each sample of x3(n) are shown in fig 5 to fig 8.
3 3 3
When n = 0 ; x 3 (0) = ∑
m = 0
x1(m) x 2 ((0 − m))4 = ∑
m = 0
x1(m) x 2,0 (m) = ∑
m = 0
v 0 (m)
1 4 1 ×4 = 4
2 x 1 (m ) 2 X 3 x 2, 0 (m ) 1 ⇒2 × 3 = 6 v 0 (m ) 2 ×1 = 2
−1 2 −1 × 2 = −2
T he su m o f sa m p les of v 0 (m ) giv es x 3 (0)
F ig 5: C o m p u ta tio n of x 3 (0 ). ∴ x (0 ) = 2 + 4 + 6 − 2 = 1 0
3
3 3 3
When n = 1 ; x 3 (1) = ∑
m = 0
x1(m) x 2 ((1 − m))4 = ∑
m = 0
x1(m) x 2,1(m) = ∑
m = 0
v1(m)
1 1 1 ×1 = 1
x 1 (m ) x 2, 1 (m ) ⇒ v 1 (m )
2 2 X 4 2 2 ×4 = 8 2 ×2 = 4
−1 3 −1 × 3 = −3
T he su m o f sa m ples of v 1 (m ) giv es x 3 (1)
F ig 6: C o m p u ta tio n of x 3 (1 ). ∴ x (1 ) = 4 + 1 + 8 − 3 = 1 0
3
3 3 3
When n = 2 ; x 3 (2) = ∑
m = 0
x1(m) x 2 ((2 − m))4 = ∑
m = 0
x1(m) x 2,2 (m) = ∑
m = 0
v 2 (m)
1 2 1 ×2 = 2
2 x 1 (m ) 2 X 1 x 2 , 2 (m ) 3 ⇒ 2 ×1 = 2 v 2 (m ) 2 ×3 = 6
−1 4 −1 × 4 = −4
T h e s u m o f s a m p le s of v 2 (m ) giv es x 3 (2)
F ig 7 : C o m p u ta tio n of x 3 (2 ). ∴ x 3 (2) = 6 + 2 + 2 − 4 = 6
3 3 3
When n = 3 ; x 3 (3) = ∑
m = 0
x1(m) x 2 ((3 − m))4 = ∑
m = 0
x1(m) x 2,3 (m) = ∑
m = 0
v 3 (m)
1 3 1 ×3 = 3
2 x 1 (m ) 2 X 2 x 2, 3 (m ) 4 ⇒ 2 ×2 = 4 v 3 (m ) 2 ×4 = 8
−1 1 −1 × 1 = −1
The index n in the given sequences are changed to m and then, the given sequences can be represented
in the tabular array as shown below. Here the shifted sequences x2, n(m) are periodically extended with a
periodicity of N = 4. Let x3(n) be the sequence obtained by convolution of x1(n) and x2(n). Each sample of x3(n) is
given by the equation,
N − 1 N − 1
x 3 (n) = ∑
m = 0
x1(m) x 2((n − m))N = ∑
m = 0
x1(m) x 2,n (m), where x 2,n (m) = x 2((n − m))N
x1(m) 2 1 2 1
x2(m) 1 2 3 4
x2((m))4 = x2,0(m) 4 3 2 1 4 3 2
To determine a sample of x3(n) at n = q, multiply the sequence, x1(m) and x 2,q (m), to get a product
sequence x1(m) x 2,q (m). [i.e., multiply the corresponding elements of the row x1(m) and x2, q(m)]. The sum of all
the samples of the product sequence gives x3(q).
3
When n = 0 ; x 3(0) = ∑
m =0
x1(m) x 2,0 (m)
= x1(0) x 2,0 (0) + x1(1) x 2,0 (1) + x1(2) x 2,0 (2) + x1(3) x 2,0 (3)
= 2 × 1 + 1 × 4 + 2 × 3 + (−1) × 2 = 2 + 4 + 6 − 2 = 10
The samples of x3(n) for other values of n are calculated as shown for n = 0.
3
When n = 1; x3(1) = ∑
m =0
x1(m) x 2,1(m) = 4 + 1 + 8 − 3 = 10
3
When n = 2; x 3(2) = ∑
m =0
x1(m) x 2,2(m) = 6 + 2 + 2 − 4 = 6
3
When n = 3; x3 (3) = ∑
m =0
x1(m) x 2,3 (m) = 8 + 3 + 4 − 1 = 14
l
∴ x3 (n) = 10, 10, 6, 14 q
A
Method 3 : Circular Convolution Using Matrices
The sequence x1(n) can be arranged as a column vector of order N ´ 1 and using the samples of x2(n) the
N ´ N matrix is formed as shown below. The product of the two matrices gives the sequence x3(n).
LMx (0)
2 x 2(3) x 2(2) x 2(1)OP LMx (0)OP
1 LMx (0)OP
3
MMx (1)
2 x 2 (0) x 2(3) x (2) P
2 MMx (1) PP
1
= MMx (1) PP
3
x (3) P
MMxx ((32))
2 x 2(1)
x 2(2)
x 2 (0)
x 2(1)
2
x (0)PQ
P MMxx ((32))PP
1
MMxx ((32)) PP
3
N2 2 N Q
1 N Q
3
Chapter 2 - Discrete Time Signals and Systems 2. 76
Example 2.25
Perform the circular convolution of the two sequences x1(n) and x2(n), where,
l
x1(n) = 0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6 q
-
l
x 2(n) = 0.1, 0.3, 0.5, 0.7, 0.9, 1.1, 1.3, 1.5 q
-
Solution
Let x3(n) be the result of the circular convolution of x1(n) and x2(n). The given sequences consists of eight
samples. Then x3(n) will also have 8 samples.
The sequences are represented in the tabular array as shown below after replacing n by m. The sequence
x2(m) is folded and shifted.
m 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7
x2((m))8 = x2,0(m) 1.5 1.3 1.1 0.9 0.7 0.5 0.3 0.1 1.5 1.3 1.1 0.9 0.7 0.5 0.3
x2((1 m))8 = x2,1(m) 1.5 1.3 1.1 0.9 0.7 0.5 0.3 0.1 1.5 1.3 1.1 0.9 0.7 0.5
x2((2 m))8 = x2,2(m) 1.5 1.3 1.1 0.9 0.7 0.5 0.3 0.1 1.5 1.3 1.1 0.9 0.7
x2((3 m))8 = x2,3(m) 1.5 1.3 1.1 0.9 0.7 0.5 0.3 0.1 1.5 1.3 1.1 0.9
x2((4 m))8 = x2,4(m) 1.5 1.3 1.1 0.9 0.7 0.5 0.3 0.1 1.5 1.3 1.1
x2((5 m))8 = x2,5(m) 1.5 1.3 1.1 0.9 0.7 0.5 0.3 0.1 1.5 1.3
x2((6 m))8 = x2,6(m) 1.5 1.3 1.1 0.9 0.7 0.5 0.3 0.1 1.5
x2((7 m))8 = x2,7(m) 1.5 1.3 1.1 0.9 0.7 0.5 0.3 0.1
7 7
x 3 (n) =
m =0
∑ x1(m) x 2 ((n − m))8 = ∑
m =0
x1(m) x 2,n (m) ; where x 2,n (m) = x 2 ((n − m))8
7 7
When n = 2; x3 (2) = ∑ x (m) x ((2 − m))
m=0
1 2 8 = ∑ x (m) x
m =0
1 2,2 (m) = 6.48
7 7
When n = 3; x3(3) = ∑ x (m) x ((3 − m))
m =0
1 2 8 = ∑ x (m) x
m =0
1 2,3 (m) = 6.64
7 7
When n = 4; x3 (4) = ∑ x (m) x ((4 − m))
m =0
1 2 8 = ∑
m=0
x1(m) x 2,4 (m) = 6.48
7 7
When n = 5; x3 (5) = ∑
m=0
x1(m) x 2((5 − m))8 = ∑
m=0
x1(m) x 2,5(m) = 6.00
7 7
When n = 6; x3(6) = ∑
m=0
x1(m) x 2 ((6 − m))8 = ∑ x (m) x
m =0
1 2,6 (m) = 5.20
7 7
When n = 7; x3(7) = ∑
m=0
x1(m) x 2 ((7 − m))8 = ∑ x (m) x
m =0
1 2,7 (m) = 4.08
lA
∴ x3(n) = 5.20, 6.00, 6.48, 6.64, 6.48, 6.00, 5.20, 4.08 q
Example 2.26
Find the linear and circular convolution of the sequences, x(n) = 1, 0.5 l q l q
and h(n) = 0.5, 1 .
A A
Solution
Linear Convolution by Tabular Array
∞
Let , y(n) = x(n) * h(n) = ∑
m = −∞
x(m) h(n − m) ; where m is a dummy variable for convolution.
Since both x(n) and h(n) starts at n = 0, the output sequence y(n) will also start at n = 0.
Since the length of x(n) and h(n) is 2, the length of y(n) is 2 + 2 1 = 3.
Let us change the index n to m in x(n) and h(n). The sequences x(m) and h(m) are represented in the
tabular array as shown below.
∞ 1
When n = 0 ; y(0) = ∑
m = −∞
x(m) h( −m) = ∑ x(m) h (m) = x(−1) h (−1) + x(0) h (0) + x(1) h (1)
m = −1
0 0 0 0
∞ 2
When n = 2 ; y(2) = ∑
m = −∞
x(m) h(2 − m) = ∑
m= 0
x(m) h2(m) = 0 + 0.5 + 0 = 0.5
l
∴ y(n) = 0.5, 1.25, 0.5 q
A
Circular Convolution by Tabular Array
N− 1
Let, y(n) = x(n) ∗ h(n) =
m=0
∑ x(m) h((n − m)) N ; where m is a dummy variable for convolution.
The index n in the sequences are changed to m and the sequences are represented in the tabular array as
shown below. The shifted sequence hn(m) is periodically extended with periodicity N = 2.
Note : The boldfaced number is the sample obtained by periodic extension.
m 1 0 1
x(m) 1 0.5
h(m) 0.5 1
h((m))2 = h0(m) 1 0.5 1
h((1 m))2 = h1(m) 1 0.5
N − 1 1
When n = 0 ; y(0) = ∑
m= 0
x(m) h((0 − m))2 = ∑ x(m) h (m)
m = 0
0
The sequence x(n) starts at n = 0 and h(n) starts at n = 1. Hence y(n) will start at n = 0 + (1) = 1.
The length of x(n) is 4 and the length of h(n) is 5. Hence the length of y(n) is (4 + 5 1) = 8. Also y(n) ends at
n = 0 + (1) + (4 + 5 2) = 6.
Let us change the index n to m in x(n) and h(n). The sequences x(m) and h(m) are represented on the
tabular array as shown below. Let us fold h(m) to get h(m) and shift h(m) to perform convolution operation.
Note : The unfilled boxes in the table are considered as zeros.
m 4 3 2 1 0 1 2 3 4 5 6 7
x(m) 1 1 2 2
h(m) 0.5 1 1 2 0.75
h(m) 0.75 2 1 1 0.5
h(1 m) = h1(m) 0.75 2 1 1 0.5
h(0 m) = h0(m) 0.75 2 1 1 0.5
h(1 m) = h1(m) 0.75 2 1 1 0.5
h(2 m) = h2(m) 0.75 2 1 1 0.5
h(3 m) = h3(m) 0.75 2 1 1 0.5
h(4 m) = h4(m) 0.75 2 1 1 0.5
h(5 m) = h5(m) 0.75 2 1 1 0.5
h(6 m) = h6(m) 0.75 2 1 1 0.5
Each sample of y(n) is given by summation of the product sequence, x(m) h(n m). To determine a
sample of y(n) at n = q, multiply the sequence x(m) and hq(m) to get a product sequence [i.e., multiply the
corresponding elements of the row x(m) and hq(m)]. The sum of all the samples of the product sequence gives
y(q).
+∞ +∞
i. e. , y(n) = ∑ x(m) h(n − m) = ∑ x(m) h (m)
m = −∞ m = −∞
n
3
When n = −1 ; y(−1) = ∑
m = −4
x(m) h−1(m)
= x(4) h1(4) + x(3) h1(3) + x(2) h1(2) + x(1) h1(1) + x(0) h1(0)
+ x(1) h1(1) + x(2) h1(2) + x(3) h1(3)
= 0 + 0 + 0 + 0 + (0.5) + 0 + 0 + 0 = 0.5
The samples of y(n) for other values of n are calculated as shown for n = 1.
3
When n = 0 ; y(0) = ∑
m = −3
x(m) h0 (m) = 0 + 0 + 0 + (−1) + 0.5 + 0 + 0 = −0.5
3
When n = 1 ; y(1) = ∑
m = −2
x(m) h1(m) = 0 + 0 + 1+ 1+ 1+ 0 = 3
3
When n = 2 ; y(2) = ∑
m = −1
x(m) h2 (m) = 0 + (−2) + ( −1) + 2 + ( −1) = −2
Chapter 2 - Discrete Time Signals and Systems 2. 80
4
When n = 3 ; y(3) = ∑
m= 0
x(m) h3(m) = −0.75 + 2 + (−2) + (−2) + 0 = −2.75
5
When n = 4 ; y(4) = ∑
m= 0
x(m) h4 (m) = 0 + 0.75 + 4 + 2 + 0 + 0 = 6.75
6
When n = 5 ; y(5) = ∑
m= 0
x(m) h5(m) = 0 + 0 + 1.5 + (−4) + 0 + 0 + 0 = −2. 5
7
When n = 6 ; y(6) = ∑
m= 0
x(m) h6 (m) = 0 + 0 + 0 + (−1.5) + 0 + 0 + 0 + 0 = −1.5
Note : The boldfaced numbers are samples obtained by periodic extension of the sequences.
m 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7
x(m) 0 1 1 2 2 0 0 0
h(m) 0.5 1 1 2 0.75 0 0 0
h(m) 0 0 0 0.75 2 1 1 0.5
h((1 m))8 = h1(m) 0 0 0 0.75 2 1 1 0.5 0 0 0 0.75 2 1 1
h((0 m))8 = h0(m) 0 0 0 0.75 2 1 1 0.5 0 0 0 0.75 2 1
h((1 m))8 = h1(m) 0 0 0 0.75 2 1 1 0.5 0 0 0 0.75 2
h((2 m))8 = h2(m) 0 0 0 0.75 2 1 1 0.5 0 0 0 0.75
h((3 m))8 = h3(m) 0 0 0 0.75 2 1 1 0.5 0 0 0
h((4 m))8 = h4(m) 0 0 0 0.75 2 1 1 0.5 0 0
h((5 m))8 = h5(m) 0 0 0 0.75 2 1 1 0.5 0
h((6 m))8 = h6(m) 0 0 0.75 2 1 1 0.5 0 0 0 0.75 2 1 1 0.5
Let y(n) be the sequence obtained by circular convolution of x(n) and h(n).
Now, each sample of y(n) is given by,
6 6
y(n) = ∑
m = −1
x(m) h((n − m))8 = ∑
m = −1
x(m) hn (m) ; where hn (m) = h((n − m))8
2. 81 Digital Signal Processing
To determine a sample of y(n) at n = q, multiply the sequence x(m) and hq(m) to get a product sequence
x(m) hq(m), [i.e., multiply the corresponding elements of the row x(m) and hq(m)]. The sum of all the samples of the
product sequence gives y(q).
6
When n = −1 ; y(−1) = ∑
m = −1
x(m) h−1(n) = x( −1) h−1( −1) + x(0) h−1(0) + x(1) h−1(1) + x(2) h−1(2)
The samples of y(n) for other values of n are calculated as shown for n = 1.
6
When n = 0 ; y(0) = ∑ x(m) h0m = 0 + (−1) + 0.5 + 0 + 0 + 0 + 0 + 0 = −0.5
m = −1
6
When n = 1 ; y(1) = ∑ x(m) h1m = 0 + 1+ 1+ 1+ 0 + 0 + 0 + 0 = 3
m = −1
6
When n = 2 ; y(2) = ∑ x(m) h2m = 0 + (−2) + (−1) + 2 + (−1) + 0 + 0 + 0 = −2
m = −1
6
When n = 3 ; y(3) = ∑ x(m) h3m = 0 + (−0.75) + 2 + (−2) + (−2) + 0 + 0 + 0 = −2.75
m = −1
6
When n = 4 ; y(4) = ∑ x(m) h4m = 0 + 0 + 0.75 + 4 + 2 + 0 + 0 + 0 = 6.75
m = −1
6
When n = 5 ; y(5) = ∑ x(m) h5m = 0 + 0 + 0 + 1.5 + (−4) + 0 + 0 + 0 = −2.5
m = −1
6
When n = 6 ; y(6) = ∑ x(m) h6m = 0 + 0 + 0 + 0 + (−1. 5) + 0 + 0 + 0 = −1.5
m = −1
Note : 1. Since circular convolution is periodic, the convolution is performed for any one period.
2. It can be observed that the results of both the methods are same.
1. The entire sequence should be available before convolution can be carried out. This makes long
delay in getting the output.
The above problems can be overcome in the sectioned convolutions. In this technique the larger
sequence is sectioned (or splitted) into the size of smaller sequence. Then the linear convolution of each
section of longer sequence and the smaller sequence is performed. The output sequences obtained from the
convolutions of all the sections are combined to get the overall output sequence. There are two methods of
sectioned convolutions. They are overlap add method and overlap save method.
Chapter 2 - Discrete Time Signals and Systems 2. 82
2.11.1 Overlap Add Method
In the overlap add method, the longer sequence is divided into smaller sequences. Then linear
convolution of each section of longer sequence and smaller sequence is performed. The overall output
sequence is obtained by combining the output of the sectioned convolution.
Let, N1 = Length of longer sequence
N2 = Length of smaller sequence
Let the longer sequence be divided into sections of size N3 samples.
Note : Normally the longer sequence is divided into sections of size same as that of smaller sequence.
N3 + N2 −1
N3 N2 −1
N3 + N2 −1
N2 −1 N 3 − ( N 2 − 1) N2 −1
N3 + N2 − 1
N2 − 1 N 3 − ( N 2 − 1) N2 −1
O v erlapped region
N3 + N2 −1
N2 −1 N 3 − ( N 2 − 1) N2 −1
N3 + N2 −1
N2 −1 N 3 − ( N 2 − 1)
A ppended
w ith zero
F ig 2 .3 1 : A p p en d ing o f sec tio n s o f in pu t seq u en c e
in m eth o d 1 o f o ve rlap sa ve m e th o d .
N3 + N2 −1
N2 −1 N 3 − ( N 2 − 1) N2 −1
N3 + N2 −1
N2 −1 N 3 − ( N 2 − 1) N2 −1
N3 + N2 − 1
N2 −1 N3
O v erlapped region
N3 + N2 −1
N 3 −( N 2 − 1) N2 −1 N2 −1
A ppended
w ith zero
N3 + N2 −1
N 3 −( N 2 − 1) N2 −1 N2 −1
N3 + N2 −1
N3 N2 −1
N3 + N2 −1
N3 N2 −1
N3 + N2 −1
N2 −1 N 3 − ( N 2 − 1) N2 −1
N3 + N2 −1
N2 − 1 N 3 −( N 2 − 1 ) N2 −1
O v erlapped region
Example 2.28
Perform the linear convolution of the following sequences by a) Overlap add method, and b) Overlap
save method.
Solution
a) Overlap Add Method
In this method the longer sequence is sectioned into sequences of size equal to smaller sequence. Here
x(n) is a longer sequence when compared to h(n). Hence x(n) is sectioned into sequences of size equal to h(n).
Here linear convolution of each section is performed between two sequences each consisting of 2
samples. Hence each convolution output will consists of 2 + 2 1 = 3 samples. The convolution of each section
is performed by tabular method as shown below.
Note :
1. Here N1 = 8, N2 = 2, N3 = 2. \ (N2 1) = 2 1 = 1 and (N2 + N3 1) = 2 + 2 1 = 3
2. The unfilled boxes in the tables are considered as zero.
3. For convenience of convolution operation the index n is replaced by m in x1(n), x2(n), x3(n), x4(n) and h(n).
2. 85 Digital Signal Processing
Convolution of Section 1
+∞
m 1 0 1 2
y1(n) = x1(n) ∗ h(n) = ∑ x (m) h(n − m)
m = −∞
1
+∞
x1(m) 1 1
= ∑ x (m) h (m) ;
1 n n = 0, 1, 2
h(m) 1 1 m = −∞
where hn (m) = h(n − m)
h(m) = ho(m) 1 1
h(1 m) = h1(m) 1 1
When n = 0 ; y1(0) = ∑ x1(m ) h0 (m) = 0 − 1+ 0 = − 1
h(2 m) = h2(m) 1 1
When n = 1 ; y1(1) = ∑ x (m) h (m) = 1+ 1 = 2 1 1
x2(m) 2 2 +∞
h(m) 1 1
= ∑ x (m) h (m)
m = −∞
2 n ; n = 2, 3, 4
Convolution of Section 3
m 1 0 1 2 3 4 5 6
x3(m) 3 3
h(m) 1 1
h(m) 1 1
h(4 m) = h4(m) 1 1
h(5 m) = h5(m) 1 1
h(6 m) = h6(m) 1 1
+∞ +∞
y3(n) = x3(n) ∗ h(n) = ∑ x (m) h(n − m) = ∑ x (m) h (m)
m = −∞
3
m = −∞
3 n ; n = 4, 5, 6
Convolution of Section 4
m 1 0 1 2 3 4 5 6 7 8
x4(m) 4 4
h(m) 1 1
h(m) 1 1
h(6 m) = h6(m) 1 1
h(7 m) = h7(m) 1 1
h(8 m) = h8(m) 1 1
Chapter 2 - Discrete Time Signals and Systems 2. 86
+∞ +∞
y 4 (n) = x 4 (n) ∗ h(n) = ∑x
m = −∞
4 (m) h(n − m) = ∑ x (m) h (m)
m = −∞
4 n ; n = 6, 7, 8
∑ x (m) h (m) = 0 − 4 + 0 = −4
When n = 6 ; y 4 (6) = 4 6
Convolution of Section 2
m 2 1 0 1 2 3 4
x2(m) 2 2 3
h(m) 1 1 0
h(m) 0 1 1
h((2 m))3 = h2(m) 0 1 1 0 1
h((3 m))3 = h3(m) 0 1 1 0
h((4 m))3 = h4(m) 0 1 1
mf 4
y 2(n) = x 2(n) ∗ h(n) = ∑
m = mi
x 2(m) h((n − m))N = ∑ x (m) h (m) ;
m = 2
2 n n = 2, 3, 4
Convolution of Section 3
mf 6
y 3(n) = x 3 (n) ∗ h(n) = ∑ x (m) h((n − m))
m = mi
3 N = ∑ x (m) h (m) ;
m = 4
3 n n = 4, 5, 6
Convolution of section 4
m 2 1 0 1 2 3 4 5 6 7 8
x4(m) 4 4 0
h(m) 1 1 0
h(m) 0 1 1
h((6 m))3 = h6(m) 0 1 1 0 1
h((7 m))3 = h7(m) 0 1 1 0
h((8 m))3 = h8(m) 0 1 1
mf 8
y 4 (n) = x 4 (n) ∗ h(n) = ∑ x (m) h((n − m))
m = mi
4 N = ∑ x (m) h (m) ; n = 6, 7, 8
m = 6
4 n
∑ x (m) h (m) = −4 + 0 + 0 = −4
When n = 6 ; y 4 (6) = 4 6
It can be observed that the last sample in an output sequence overlaps with the first sample of next output
sequence. In overlap save method the overall output is obtained by combining the outputs of the convolution
of all sections. While combining the outputs, the overlapped first sample of every output sequence is discarded
and the remaining samples are simply saved as samples of y(n) as shown in the following table.
n 0 1 2 3 4 5 6 7 8
y1(n) 1 2 3
y2(n) 1 4 5
y3(n) 1 6 7
y4(n) 4 8 4
y(n) * 2 3 4 5 6 7 8 4
Note : Here y(n) is linear convolution of x(n) and h(n). It can be observed that the results of both the methods
are same, except the first N2 1 samples.
2. 89 Digital Signal Processing
Method 2
In method 2, the overlapping samples are placed at the end of the section.Each section of longer
sequence is converted to 3-sample sequence, using the samples of original longer sequence as shown below.
It can be observed that the last sample of x1(n) is placed as overlapping sample at the end of x2(n). The last
sample of x2(n) is placed as overlapping sample at the end of x3(n). The last sample of x3(n) is placed as
overlapping sample at the end of x4(n). Since there is no previous section for x1(n), the overlapping sample of
x1(n) is taken as zero.
= 1 ; n = 1 = 2 ; n = 3 = 3 ; n=5 = 4 ; n = 7
= 0; n=2 = 1 ; n = 4 = 2 ; n = 6 = 3 ; n = 8
Now perform circular convolution of each section with h(n). The output sequence obtained from circular
convolution will have three samples. The circular convolution of each section is performed by tabular method as
shown below.
m 2 1 0 1 2 3 4
x2(m) 2 2 1
h(m) 1 1 0
h(m) 0 1 1
h((2 m))3 = h2(m) 0 1 1 0 1
h((3 m))3 = h3(m) 0 1 1 0
h((4 m))3 = h4(m) 0 1 1
Chapter 2 - Discrete Time Signals and Systems 2. 90
mf 4
y 2 (n) = x 2(n) ∗ h(n) = ∑ x (m) h((n − m))
m = mi
2 N = ∑ x (m) h (m); n = 2,
m = 2
2 n 3, 4,
Convolution of Section 3
m 2 1 0 1 2 3 4 5 6
x3(m) 3 3 2
h(m) 1 1 0
h(m) 0 1 1
h((4 m))3 = h4(m) 0 1 1 0 1
h((5 m))3 = h5(m) 0 1 1 0
h((6 m))3 = h6(m) 0 1 1
mf 6
y3(n) = x3 (n) ∗ h(n) = ∑ x (m) h((n − m))
m = mi
3 N = ∑ x (m) h (m) ;
m = 4
3 n n = 4, 5, 6
Convolution of Section 4
m 2 1 0 1 2 3 4 5 6 7 8
x4(m) 4 4 3
h(m) 1 1 0
h(m) 0 1 1
h((6 m))3 = h6(m) 0 1 1 0 1
h((7 m))3 = h7(m) 0 1 1 0
h((8 m))3 = h8(m) 0 1 1
mf 8
y 4 (n) = x 4 (n) ∗ h(n) = ∑ x (m) h((n − m))
m = mi
4 N = ∑ x (m) h (m) ; n = 6, 7, 8
m = 6
4 n
∑
When n = 6 ; y 4 (6) = x 4 (m) h6 (m) = −4 + 0 − 3 = −7
When n = 7 ; y (7) = ∑ x (m) h (m) =
4 4 7 4+4+0 = 8
When n = 8 ; y (8) = ∑ x (m) h (m) =
4 4 8 0 − 4 + 3 = −1
2. 91 Digital Signal Processing
To Combine the Output of the Convolution of Each Section
It can be observed that the last sample in an output sequence overlaps with the first sample of next output
sequence. In overlap save method the overall output is obtained by combining the outputs of the convolution of
all sections. While combining the outputs, the overlapped last sample of every output sequence is discarded and
the remaining samples are simply saved as samples of y(n) as shown in the following table.
n 0 1 2 3 4 5 6 7 8
Note :
y1(n) 1 2 1
Here y(n) is linear convolution
y2(n) 3 4 1 of x(n) and h(n). It can be
y3(n) 5 6 1 observed that the results of both
the methods are same except the
y4(n) 7 8 1 last N21 samples.
y(n) 1 2 3 4 5 6 7 8 *
Example 2.29
Perform the linear convolution of the following sequences by a) Overlap add method and b) Overlap
save method.
Solution
a) Overlap Add Method
In this method the longer sequence is sectioned into sequences of size equal to smaller sequence. Here
x(n) is a longer sequence when compared to h(n). Hence x(n) is sectioned into sequences of size equal to h(n).
Given that x(n) = {1, 2, 3, 1, 2, 3, 4, 5, 6}. Let x(n) can be sectioned into three sequences, each
consisting of three samples of x(n) as shown below.
Let y1(n), y2(n) and y3(n) be the output of linear convolution of x1(n), x2(n) and x3(n) with h(n) respectively.
m 2 1 0 1 2 3 4
+∞
h(m) 2 1 1 +∞
h(m) = h0(m) 1 1 2
= ∑ x (m) h (m)
m = −∞
1 n
Convolution of Section 2
m 2 1 0 1 2 3 4 5 6 7
x2(m) 1 2 3
h(m) 2 1 1
h(m) = h0(m) 1 1 2
h(3 m) = h3(m) 1 1 2
h(4 m) = h4(m) 1 1 2
h(5 m) = h5(m) 1 1 2
h(6 m) = h6(m) 1 1 2
h(7 m) = h7(m) 1 1 2
∞ ∞
y 2(n) = x 2(n) ∗ h(n) = ∑ x (m) h(n − m) = ∑ x (m) h (m); n = 3, 4, 5, 6, 7
m = −∞
2
m = −∞
2 n
∑ x (m) h (m) = 0 + 0 − 2 + 0 + 0 = 2
When n = 3 ; y 2 (3) = 2 3
m 4 3 2 1 0 1 2 3 4
x1(m) 1 2 3 1 2
h(m) 2 1 1 0 0
h((m))5 = h0(m) 0 0 1 1 2 0 0 1 1
h((1 m))5 = h1(m) 0 0 1 1 2 0 0 1
h((2 m))5 = h2(m) 0 0 1 1 2 0 0
h((3 m))5 = h3(m) 0 0 1 1 2 0
h((4 m))5 = h4(m) 0 0 1 1 2
mf 4
y1(n) = x1(n) ∗ h(n) = ∑ x (m) h((n − m))
m = mi
1 N = ∑ x (m) h (m); n = 0, 1, 2, 3, 4
m = 0
1 n
Convolution of Section 2
m 4 3 2 1 0 1 2 3 4 5 6 7
x2(m) 1 2 3 4 5
h(m) 2 1 1 0 0
h(m) = h0(m) 0 0 1 1 2
h((3 m))5 = h3(m) 0 0 1 1 2 0 0 1 1
h((4 m))5 = h4(m) 0 0 1 1 2 0 0 1
h((5 m))5 = h5(m) 0 0 1 1 2 0 0
h((6 m))5 = h6(m) 0 0 1 1 2 0
h((7 m))5 = h7(m) 0 0 1 1 2
mf 7
y 2 (n) = x 2(n) ∗ h(n) = ∑ x (m) h((n − m))
m = mi
2 N = ∑ x (m) h (m); n = 3, 4, 5, 6, 7
m = 3
2 n
∑
When n = 3 ; y 2 (3) = x 2(m) h3 (m) = −2 + 0 + 0 4 + 5 = 1
When n = 4 ; y 2(4) =∑ x (m) h (m) = −1 − 4 + 0 + 0 5 = −10
2 4
Convolution of Section 3
m 4 3 2 1 0 1 2 3 4 5 6 7 8 9 10
x3(m) 4 5 6 0 0
h(m) 2 1 1 0 0
h(m) = h0(m) 0 0 1 1 2
h((6 m))5 = h6(m) 0 0 1 1 2 0 0 1 1
h((7 m))5 = h7(m) 0 0 1 1 2 0 0 1
h((8 m))5 = h8(m) 0 0 1 1 2 0 0
h((9 m))5 = h9(m) 0 0 1 1 2 0
h((10 m))5 = h10(m) 0 0 1 1 2
mf 10
y3 (n) = x 3(n) ∗ h(n) = ∑ x (m) h((n − m))
m = mi
3 N = ∑ x (m) h (m)
m = 6
3 n ; n = 6, 7, 8, 9, 10
\ y(n) = x(n) * h(n) = {*, *, 7, 1, 8, 7, 7, 17, 13, 1, 6}
Note : Here y(n) is linear convolution of x(n) and h(n). It can be observed that the results of both the
methods are same except the first N2 1 samples.
Let h(n) be the impulse response of a system and h¢(n) be the impulse response of inverse system. Let
us connect the system and its inverse in cascade as shown in fig 2.36.
Identity sy s tem
H H
-1
y (n)
x(n) h(n) h ’(n) w (n) = x(n)
2.12.2 Deconvolution
In an LTI system the response y(n) is given by convolution of input x(n) and impulse response h(n).
i.e., y(n) = x(n) * h(n)
The process of recovering the input from the response of a system is called deconvolution. (or the
process of recovering x(n) from x(n) * h(n) is called deconvolution).
When the response y(n) and impulse response h(n) are available, then the input x(n) can be computed
using the equation (2.64).
x(n) =
1 LM n −1
y(n) − ∑ x(m) h(n − m)
OP .....(2.64)
h(0) MN m= 0 PQ
Proof :
Let x(n) and h(n) be finite duration sequences starting from n = 0. Consider the matrix method
of convolution of x(n) and h(n) shown below.
y(0)
y( n) = x(0) h(0) ⇒ x(0) =
h(0)
y(1) − x(0) h(1)
y(1) = x(1) h(0)+ x(0) h(1) ⇒ x(1) =
h(0)
y(2) − x(0) h(2) − x(1) h(1)
y(2) = x(2) h(0)+ x(1) h(1)+ x(0) h(2) ⇒ x(2) =
h(0)
y(3) − x(0) h(3) − x(1) h(2) − x(2) h(1)
y(3) = x(3) h(0)+ x(2) h(1)+ x(1) h(2)+ x(0) h(3) ⇒ x(3) =
h(0)
and so on.
From the above analysis, in general for any value of n, the x(n) is given by,
Solution
n
Given that, y(n) = ∑ x(m)
m=0
0
When n = 0; y(0) = ∑ x(m) = x(0)
m =0
1
When n = 1; y(1) =
m=0
∑ x(m) = x(0) + x(1) = y(0) + x(1)
2
When n = 2; y(2) = ∑
m =0
x(m) = x(0) + x(1) + x(2) = y(1) + x(2)
3
When n = 3; y(3) = ∑
m=0
x(m) = x(0) + x(1) + x(2) + x(3) = y(2) + x(3)
and so on,
x(0) = y(0) ; x(1) = y(1) y(0) ; x(2) = y(2) y(1) ; x(3) = y(3) y(2) and so on,
In general for any value of n, the signal x(n) can be written as,
2. 99 Digital Signal Processing
Example 2.31
When a discrete time system is excited by an input x(n), the response is y(n) = { 2, 5, 11, 17, 13, 12 }
--
If the impulse response of the system is h(n) = { 2, 1, 3 }, then what will be the input to the system?
-
Solution
Let N1 be number of samples in x(n) and N2 be number of samples in h(n), then the number of samples N3
in y(n) is given by,
N3 = N1 + N2 1
\ N1 = N3 N2 + 1 = 6 3 + 1 = 4 samples
Therefore x(n) is 4 sample sequence.
Each sample of x(n) is given by,
The evaluation of equation (2.68) to determine the value of rxy(m) at m = q involves the following three
steps.
1. Shifting : Shift y(n) by q times to the right if q is positive, shift y(n) by q times to the
left if q is negative to obtain y(n - q).
2. Multiplication : Multiply x(n) by y(n - q) to get a product sequence. Let the product
sequence be vq(n). Now, vq(n) = x(n) × y(n - q).
3. Summation : Sum all the values of the product sequence vq(n) to obtain the value of
rxy(m) at m = q. [i.e., rxy(q)].
The above procedure will give the value rxy(m) at a single time instant say m = q. In general we are
interested in evaluating the values of the sequence rxy(m) over all the time instants in the range -¥ < m < ¥ .
Hence the steps 1, 2 and 3 given above must be repeated, for all possible time shifts in the range -¥ < m < ¥ .
In the correlation of finite duration sequences it is possible to predict the start and end of the resultant
sequence. If x(n) is N-point sequence and starts at n = n1 and if y(n) is N2-point sequence and starts at n = n2 then,
the initial value of m = mi for rxy(m) is mi = n1 – (n2 + N2 – 1). The value of x(n) for n < n1 and the value of y(n) for
n < n2 are then assumed to be zero.The final value of m = mf for rxy(m) is mf = mi + (N1+N2– 2).
The correlation operation involves all the steps in convolution operation except the folding.
Hence it can be proved that the convolution of x(n) and folded sequence y(-n) will generate the crosscorrelation
sequence rxy(m).
i.e., r (m) = x(n) * y(-n) .....(2.69)
xy
The procedure given above can be used for computing autocorrelation of x(n). For computing
autocorrelation using equation (2.68) replace y(n – q) by x(n – q). Similarly when equation (2.69) is used,
replace y(–n) by x(–n).
The autocorrelation of N-point sequence x(n) will give 2N –1 point autocorrelation sequence.
If x(n) starts at n = nx then initial value of m = mi for rxx(m) is mi = – (N –1). The final value of m = mf for rxx(m)
is mf = mi + (2N–2).
2. 101 Digital Signal Processing
Properties of Correlation
1. The crosscorrelation sequence rxy(m) is simply a folded version of ryx(m),
i.e., rxy(m) = ryx(-m)
Similarly for autocorrelation sequence,
rxx(m) = rxx(-m)
Hence autocorrelation is an even function.
2. The crosscorrelation sequence satisfies the condition,
From the above equations we infer that the crosscorrelation sequence and autocorrelation
sequences attain their respective maximum values at zero shift/lag.
3. Using the maximum value of crosscorrelation sequence, the normalized crosscorrelation sequence
is defined as,
rxy (m)
ρxy (m) ≤
rxx (0) ryy (0)
Using the maximum value of autocorrelation sequence, the normalized autocorrelation sequence
is defined as,
rxx (m)
ρxx (m) ≤
rxx ( 0)
Multiply each column element with row elements and fill up the matrix array.
Now the sum of the diagonal elements gives the samples of output sequence rxy(m). (The sum of the
diagonal elements are shown below for reference).
:
:
rxy(0) = ..... + x(0) y(0) + .....
rxy(1) = ..... + x(1) y(0) + x(0 ) y(-1) + .....
rxy(2) = ..... + x(2) y(0) + x(1) y(-1) + x(0) y(-2) + .....
rxy(3) = ..... + x(3) y(0) + x(2) y(-1) + x(1) y(-2) + x(0) y(-3) + .....
:
:
Example 2.32
Perform crosscorrelation of the sequences, x(n) = {1, 1, 2, 2} and y(n) = {1, 0.5, 1}.
Solution
Let rxy(m) be the crosscorrelation sequence obtained by crosscorrelation of x(n) and y(n).
The crosscorrelation sequence rxy(m) is given by,
+∞
rxy = ∑ x(n) y(n − m)
n = −∞
x (n ) y (n )
2 2
1 1 1 1
0.5
0 1 2 3 n 0 1 2 n
F ig 1. F ig 2.
The 6 samples of rxy(m) are computed using the equation,
+∞ +∞
rxy (m) = ∑
n = −∞
x(n) y(n − m) = ∑
n = −∞
x(n) y m (n) ; where y m (n) = y(n − m)
The computation of each sample of rxy(n) using the above equation are graphically shown in fig 3 to fig 8.
The graphical representation of output sequence is shown in fig 9.
+∞ +∞ +∞
When m = −2 ; rxy ( −2) = ∑
n = −∞
x(n) y(n − ( −2)) = ∑
n = −∞
x(n) y −2 (n) = ∑
n = −∞
v − 2 (n)
x (n ) y −2 (n) v −2 (n)
2 2
X ⇒
1 1 1 1 1
0.5
0 1 2 3 n −2 −1 0 n −2 −1 0 1 2 3 n
T he su m o f pro du ct s eq ue n ce
v −2 (n ) giv es rxy ( −2)
F ig 3 : C o m p uta tio n o f r x y ( −2).
∴ rxy ( −2) = 0 + 0 + 1 + 0 + 0 + 0 = 1
+∞ +∞ +∞
When m = −1 ; rxy (−1) = ∑
n = −∞
x(n) y(n − ( −1)) = ∑
n = −∞
x(n) y −1(n) = ∑
n = −∞
v − 1(n)
x (n ) y −1 (n) v −1 (n )
2 2
X ⇒ 1
1 1 1 1
0.5 0.5
0 1 2 3 n −1 0 1 n −1 0 1 2 3 n
T he s um of pro du c t s e qu en c e
v −1(n ) g iv e s rx y ( −1 )
F ig 4 : C om p u ta tio n of rx y ( −1 ).
∴ rxy ( −1) = 0 + 0 .5 + 1 + 0 + 0 = 1 .5
Chapter 2 - Discrete Time Signals and Systems 2. 104
+∞ +∞ +∞
When m = 0 ; rxy (0) = ∑ x(n) y(n) = ∑ x(n) y 0 (n) = ∑ v 0 (n)
n = −∞ n = −∞ n = −∞
x (n ) y 0 (n ) v 0 (n )
2 2 2
X ⇒ 1
1 1 1 1
0.5 0.5
0 1 2 3 n 0 1 2 n 0 1 2 3 n
T he su m o f pro du ct s eq u en ce
x (n ) y 1 (n ) v 1 (n )
2 2 2
X ⇒
1 1 1 1 1 1
0.5
0 1 2 3 n 0 1 2 3 n 0 1 2 3 n
T he su m o f pro du ct s eq u en ce
F ig 6 : C o m p u ta tio n of rxy (1 ). v 1 (n) giv es rxy (1 )
∴ rx y (1 ) = 0 + 1 + 1 + 2 = 4
+∞ +∞ +∞
When m = 2 ; rxy (2) = ∑
n = −∞
x(n) y(n − 2) = ∑
n = −∞
x(n) y 2 (n) = ∑
n = −∞
v 2 (n)
x (n ) y 2 (n ) v 2 (n )
2 2 2
X ⇒ 1
1 1 1 1
0.5
0 1 2 3 n 0 1 2 3 4 n 0 1 2 3 4 n
T he su m o f pro du ct s eq u en ce
F ig 7 : C o m pu ta tio n o f rx y (2). v 2 (n ) giv es rx y (2 )
∴ rx y (2 ) = 0 + 0 + 2 + 1 + 0 = 3
+∞ +∞ +∞
When m = 3 ; rxy (3) = ∑
n = −∞
x(n) y(n − 3) = ∑
n = −∞
x(n) y 3(n) = ∑
n = −∞
v 3(n)
x (n ) y 3 (n ) v 3 (n )
2 2
X ⇒ 2
1 1 1 1
0.5
0 1 2 3 n 0 1 2 3 4 5 n 0 1 2 3 4 5 n
T he su m o f pro du ct s eq u en ce
F ig 8 : C o m p uta tio n o f rxy (3 ). v 3 (n ) giv es rx y (3 )
∴ rx y (3) = 0 + 0 + 0 + 2 + 0 + 0 = 2
2. 105 Digital Signal Processing
The crosscorrelation sequence, rxy(m) = {1, 1.5, 3.5, 4, 3, 2}
-
r x y (m )
4
3.5
3
2
1.5
1
−2 −1 0 1 2 3 m
F ig 9 : G ra p h ic a l rep resenta tio n o f rxy (m ).
Method 2: Tabular Method
The given sequences and the shifted sequences can be represented in the tabular array as shown below.
n 2 1 0 1 2 3 4 5
x(n) 1 1 2 2
y(n) 1 0.5 1
y(n (2)) = y2(n) 1 0.5 1
y(n (1)) = y1(n) 1 0.5 1
y(n) = y0(n) 1 0.5 1
y(n 1) = y1(n) 1 0.5 1
y(n 2) = y2(n) 1 0.5 1
y(n 3) = y3(n) 1 0.5 1
To determine a sample of rxy(m) at m = q, multiply the sequence x(n) and yq(n) to get a product sequence
[i.e., multiply the corresponding elements of the row x(n) and yq(n)]. The sum of all the samples of the product
sequence gives rxy(q).
3
When m = −2 ; rxy (−2) = ∑
n = −2
x(n) y −2(n) = 0 + 0 + 1+ 0 + 0 + 0 = 1
3
When m = −1 ; rxy (−1) = ∑ x(n) y
n = −1
−1(n) = 0 + 0.5 + 1+ 0 + 0 = 1.5
3
When m = 0 ; rxy (0) = ∑ x(n) y
n =0
0 (n) = 1+ 0.5 + 2 + 0 = 3.5
3
When m = 1 ; rxy (1) = ∑
n=0
x(n) y1(n) = 0 + 1+ 1+ 2 =4
4
When m = 2 ; rxy (2) = ∑ x(n) y (n)
n =0
2 = 0 + 0 + 2 + 1+ 0 =3
5
When m = 3 ; rxy (3) = ∑ x(n) y (n)
n=0
3 = 0 +0 + 0 + 2+ 0 +0 = 2
y ( −n ) y ( −n )
x (n) 1 0.5 1 x (n) 1 0.5 1
1 1 ×1 1 × 0.5 1 ×1 1 1 0.5 1
1 1 ×1 1 × 0.5 1 ×1 ⇒ 1 1 0.5 1
2 2 ×1 2 × 0.5 2 ×1 2 2 1 2
2 2 ×1 2 × 0.5 2 ×1 2 2 1 2
Example 2.33
Determine the autocorrelation sequence for x(n) = {1, 2, 3, 4}.
Solution
Let, rxx(m) be the autocorrelation sequence.
The autocorrelation sequence rxx(m) is given by,
+∞
rxx (m) = ∑
n = −∞
x(n) x(n − m)
n 3 2 1 0 1 2 3 4 5 6
x(n) 1 2 3 4
x(n (3)) = x3(n) 1 2 3 4
x(n (2)) = x2(n) 1 2 3 4
x(n (1)) = x1(n) 1 2 3 4
x(n) = x0(n) 1 2 3 4
x(n 1) = x1(n) 1 2 3 4
x(n 2) = x2(n) 1 2 3 4
x(n 3) = x3(n) 1 2 3 4
2. 107 Digital Signal Processing
Each sample of rxx(m) is given by,
+∞ +∞
rxx (m) = ∑
n = −∞
x(n) x(n − m) = ∑
n = −∞
x(n) xm (n) ; where xm (n) = x(n − m)
To determine a sample of rxx(m) at m = q, multiply the sequence x(n) and xq(n) to get a product sequence
[i.e., multiply the corresponding elements of the row x(n) and xq(n)]. The sum of all the samples of the product
sequence gives rxx(q).
3
W hen m = − 3 ; rxx ( − 3) = ∑
n = −3
x(n) x − 3 (n ) = 0 + 0 + 0 + 4 + 0 + 0 + 0 = 4
3
W hen m = − 2 ; rxx ( − 2) = ∑
n = −2
x(n) x − 2 (n ) = 0 + 0 + 3 + 8 + 0 + 0 = 11
3
W hen m = − 1 ; rxx ( − 1 ) = ∑
n = −1
x(n) x − 1(n ) = 0 + 2 + 6 + 12 + 0 = 20
3
W hen m = 0 ; rxx ( 0 ) = ∑
n = 0
x(n) x 0 (n ) = 1 + 4 + 9 + 16 = 30
4
W hen m = 1 ; rxx (1 ) = ∑
n = 0
x(n) x 1(n ) = 0 + 2 + 6 + 12 + 0 = 20
5
W hen m = 2 ; rxx ( 2) = ∑
n = 0
x(n) x 2 (n ) = 0 + 0 + 3 + 8 + 0 + 0 = 11
6
W hen m = 3 ; rxx (3) = ∑
n = 0
x(n) x 3 (n ) = 0 + 0 + 0 + 4 + 0 + 0 + 0 = 4
The output sequence obtained by circular correlation is also periodic sequence with periodicity of N
samples. Hence this correlation is also called periodic correlation. The circular correlation is defined for
periodic sequences. But circular correlation can be performed with non-periodic sequences by periodically
extending them.The circular correlation of two sequences requires that, at least one of the sequences should
be periodic. Hence it is sufficient if one of the sequences is periodically extended in order to perform circular
correlation.
Chapter 2 - Discrete Time Signals and Systems 2. 108
The circular correlation of finite duration sequences can be performed only if both the sequences
consists of same number of samples. If the sequences have different number of samples, then convert the
smaller size sequence to the size of larger size sequence by appending zeros.
In the equation (2.70), the sequence x(n) is unshifted and the sequence y*(n) is circularly shifted by
m units of time for correlation operation. The same results can be obtained if the sequence y*(n) is unshifted
and the sequence x(n) is circularly shifted opposite to that of earlier case by m units of time, hence the circular
correlation operation can also be expressed as,
N−1
rxy ( m) = ∑ x(( n + m))
n=0
N y* (n) .....(2.72)
Circular correlation basically involves the same three steps as that for correlation, namely shifting one
of the sequence, multiplying the two sequences and finally summing the values of product sequence. The
difference between the two is that in circular correlation the shifting (rotating) operations are performed in a
circular fashion by computing the index of one of the sequences by modulo-N operation. In correlation, there
is no modulo-N operation.
2.14.1 Procedure for Evaluating Circular Correlation
Let, x(n) and y(n) be periodic discrete time sequences with periodicity of N-samples. If x(n) and y(n)
are non-periodic then convert the sequences to N-sample sequence and periodically extend the sequence
y(n) with periodicity of N-samples.
Now the circular correlation of x(n) and y(n) will produce a periodic sequence rxy ( m) with periodicity
of N-samples. The samples of one period of rxy ( m) can be computed using the equation (2.70).
The evaluation of equation (2.73) to determine the value of rxy ( m) at m = q involves the following
four steps.
1. Conjugation : Take conjugate of y(n) to get y*(n). If y(n) is a real sequence then y*(n)
will be same as y(n). Represent the samples of one period of the sequences
x(n) and y*(n) on circles.
2. Rotation : Rotate y*(n) by q times in anticlockwise if q is positive, rotate y*(n) by
q times in clockwise if q is negative to obtain y*((n – q))N.
3. Multiplication : Multiply x(n) by y*((n – q))N to get a product sequence. Let the product
sequence be vq(m). Now, vq(m) = x(n) × y*((n – q))N.
4. Summation : Sum up the samples of one period of the product sequence vq(m) to
obtain the value of rxy ( m) at m = q. [i.e., rxy (q ) ].
The above procedure will give the value of rxy ( m) at a single time instant say m = q. In general, we are
interested in evaluating the values of the sequence rxy ( m) in the range 0 < m < N - 1. Hence the steps 2 ,
3 and 4 given above must be repeated, for all possible time shifts in the range 0 < m < N - 1.
2. 109 Digital Signal Processing
4. The sum of all the samples of the product sequence gives the sample rxy (q ) [i.e., rxy ( m) at m = q].
The above procedure is repeated for all possible values of m to get the sequence rxy ( m).
Method 2 : Using Tabular Array
Let x(n) and y(n) be the given real sequences. Let rxy ( m) be the sequence obtained by circular
correlation of x(n) and y(n). The following procedure can be used to get a sample of rxy ( m) at m = q.
1. Represent the sequences x(n) and y(n) as two rows of tabular array.
2. Periodically extend y(n). Here the periodicity is N, where N is the length of the given sequences.
3. Shift the sequence y(n), q times to get the sequence y((n – q))N. If q is positive then shift the
sequence to the right and if q is negative then shift the sequence to the left.
4. The sample of rxy (q ) at m = q is given by,
N−1 N−1
rxy (q) = ∑ x(n) y((n − q)) N = ∑ x(n) yq ( n)
n=0 n=0
where, yq (n) = y((n − q)) N
Determine the product sequence x(n)yq(n) for one period.
5. The sum of all the samples of the product sequence gives the sample rxy (q ) [i.e., rxy ( m)
at m = q].
The above procedure is repeated for all possible values of m to get the sequence rxy ( m).
Method 3: Using Matrices
Let x(n) and y(n) be the given N-point sequences. The circular correlation of x(n) and y(n) yields
another N-point sequence rxy ( m).
Chapter 2 - Discrete Time Signals and Systems 2. 110
In this method an N ´ N matrix is formed using the sequence y(n) as shown below. The sequence x(n)
is arranged as a column vector (column matrix) of order N ´ 1. The product of the two matrices gives the
resultant sequence rxy ( m).
L r (0) O
OP LM xx((10)) OP MM r (1) PP
xy
LMy(0) y(1) y ( 2) ..... y( N − 1) y( N )
xy
MMy(N) y( 0) y (1) ..... y ( N − 2) y( N − 1) P MM P M r ( 2) P
x( 2) P
MMy(MN − 1) y( N ) y(0) ..... y ( N − 3) y( N − 2) P
P × M
M M PP = MM M PP xy
MMy(2)
M M M M PP M M P MM M PP
y (3) y (4) ..... y( 0) y(1)
P MMx(N − 2)PP M r (N − 2)P
MNy(1) y( 2) y( 3) ..... y( N ) y( 0) PQ MNx(N − 1) PQ MM r (N − 1) PP xy
N Q xy
Example 2.34
Perform circular correlation of the two sequences, x(n) = {1, 1, 2, 1} and y(n)= {2, 3, 1, 1}
- -
Solution
Method 1:Graphical Method of Computing Circular Correlation
The given sequences are represented as points on circles as shown in fig 1 and 2.
x (1) = 1 y (1) = 3
x (3) = 1 y (3) = 1
F ig 1. F ig 2.
3 2 1 1
1 1 3 2
F ig 3 : C ircu la rly sh ifted seq u e nces y (n -m ), for m = 0 , 1 , 2, 3 .
Let rxy (m) be the sequence obtained by circular correlation of x(n) and y(n). The given sequences are 4
sample sequences and so N = 4. Each sample of rxy (m) is given by the equation,
N − 1 N − 1
rxy (m) = ∑
n = 0
x(n) y((n − m))N = ∑
n = 0
x(n) y m (n), where y m (n) = y((n − m))N
Using the above equation, graphical method of computing each sample of rxy (m) are shown in fig 4 to fig 7.
3 3 3
When m = 0 ; rxy (0) = ∑
n = 0
x(n) y((n − 0))4 = ∑
n = 0
x(n) y 0 (n) = ∑ v (n)
n = 0
0
1 3 1 ×3 = 3
y 0 ( n)
2 x (n) 1 X 1 2 ⇒ 2 ×1 = 2 v 0 (n) 1 ×2 = 2
1 1 1 ×1 = 1
1 2 1 ×2 = 2
2 x (n) 1 X 3 y 1( n) 1 ⇒ 2 ×3 = 6 v 1( n) 1 ×1 = 1
1 1 1 ×1 = 1
3 3 3
When m = 2 ; rxy (2) = ∑ x(n) y((n − 2))
n = 0
4 = ∑ x(n) y (n) = ∑ v (n)
n = 0
2
n = 0
2
1 1 1×1 = 1
2 x (n) 1 X 2 y 2 (n) 1 ⇒ 2 ×2 = 4 v 2 ( n) 1 ×1 = 1
1 3 1 ×3 = 3
T he su m o f sa m ples of v 2 (n) g iv e s rxy (2)
F ig 6 : C o m pu ta tio n o f rxy (2 ).
∴ rxy (2) = 1 + 1 + 4 + 3 = 9
3 3 3
When m = 3 ; rxy (3) = ∑ x(n) y((n − 3))
n = 0
4 = ∑ x(n) y (n) = ∑ v (n)
n = 0
3
n = 0
3
1 1 1 ×1 = 1
1 2 1 ×2 = 2
The given sequences are represented in the tabular array as shown below. Here the shifted sequences
ym(n) are periodically extended with a periodicity of N = 4. Let rxy (m) be the sequence obtained by circular
correlation of x(n) and y(n). Each sample of rxy (m) is given by the equation,
N − 1 N − 1
rxy (m) = ∑
n = 0
x(n) y((n − m))N = ∑
n = 0
x(n) y m (n), where y m (n) = y((n − m))N
n 0 1 2 3 4 5 6
x(n) 1 1 2 1
y(n) 2 3 1 1
To determine a sample of rxy (m) at m = q, multiply the sequence, x(n) and y q (n), to get a product sequence
x(n) xq(n) [i.e., multiply the corresponding elements of the row x(n) and yq(n)]. The sum of all the samples of the
product sequence gives rxy (m).
3
When m = 0 ; rxy (0) = ∑ x(n) y
n=0
0 (n)
The samples of rxy (m) for other values of m are calculated as shown for m = 0.
3
When m = 1; rxy (1) = ∑
n=0
x(n) y1(n) = 1 + 2 + 6 + 1 = 10
3
When m = 2; rxy (2) = ∑ x(n) y 2(n) = 1 + 1 + 4 + 3 = 9
n =0
3
When m = 3; rxy (3) = ∑
n =0
x(n) y3(n) = 3 + 1 + 2 + 2 = 8
l
∴ rxy (m) = 8, 10, 9, 8 q
A
Method 3 : Circular Correlation Using Matrices
The sequence rxy (m) can be arranged as a column vector of order N ´ 1 and using the samples of y(n) the
N ´ N matrix is formed as shown below. The product of the two matrices gives the sequence rxy (m).
(3) PQ
N N Q Nr
xy
Q2.2 Perform multiplication of discrete time signals, x1(n) = {2, 2, 1, 2} and x2(n) = {–2, –1, 3, 2}.
Solution
Q2.4 What are the basic elements used to construct the block diagram of discrete time system?
The basic elements used to construct the block diagram of discrete time system are adder, constant
multiplier and unit delay element.
x 1 (n) x 1(n ) + x 2 (n ) x 1 (n) ax 1 (n) x (n) x (n − 1)
−1
+ a z
x 2 (n)
Q2.10 Perform the circular convolution of the two sequences x1(n) = {1, 2, 3} and x2(n) = {4, 5, 6}.
Solution
Let x3(n) be the sequence obtained from circular convolution of x1(n) and x2(n). The sequence
x1(n) can be arranged as a column vector of order 3 ´1 and using the samples of x2(n) a 3 ´ 3 matrix
is formed as shown below. The product of two matrices gives the sequence x3(n).
LMx (0)
2 x2 (2) x 2 (1) OP LMx (0)OP LMx (0)OP
1 3 LM4 6 5 OP LM1OP LM31OP
⇒
MMNxx (1)
2
2 (2)
x2 (0) x 2 (2)
x2 (1)
P Mx (1)P = MMNxx (1)
1
x (0) PQ MN x (2) PQ
2 1
3
P
(2) PQ
3
MMN56 4 6
5
P M2P = MMN2831PPQ
4PQ MN 3PQ
1 1 ×1 1 ×4 1 ×2 1 1 4 2
⇒
2 2 ×1 2 ×4 2 ×2 2 2 8 4
Solution
Let rxx ( m) be the sequence obtained from circular autocorrelation of x(n). The sequence x(n) can
be arranged as a column vector of order 4´1 and again by using the samples of x(n) a 4´4 matrix
is formed as shown below. The product of two matrices gives the sequence rxx ( m) .
LMx(0) x(1) x(2) x(3) OP LMx(0)OP LMr xx (0) OP LM1 2 3 OP LM1OP LM 30OP
4
MMx(3)
x(2)
x(0)
x(3)
x(1)
x(0)
x(2)
x(1)
PP MMx(1) P = MMrr
x(2) P
xx (1)
xx (2) P
P ⇒ MM43 1
4
2
1
3
2
PP MM23PP = MM 2422PP
MNx(1) x(2) x(3) x(0) PQ MNx(3)PQ MNr xx (3) PQ MN2 3 4 1 PQ MN4PQ MN 24PQ
\ rxx ( m) = {30, 24, 22, 24 }
Q2.20 What is the difference between circular crosscorrelation and circular autocorrelation?
Circular crosscorrelation operation is circular correlation of two different sequences, whereas
circular autocorrelation is circular correlation of a sequence with itself.
Program 2.2
Write a MATLAB program to generate the standard discrete time signals exponential
and sinusoidal signals.
OUTPUT
The output waveforms of program 2.2 are shown in fig P2.2.
Program 2.3
Write a MATLAB program to find the even and odd parts of the signal x(n)=0.8n.
%To find the even and odd parts of the signal, x(n)= 0.8^n
subplot(2,2,1);stem(n,x1);
xlabel(n);ylabel(x1(n));title(signal x(n));
subplot(2,2,2);stem(n,x2);
xlabel(n);ylabel(x2(n));title(signal x(-n));
subplot(2,2,3);stem(n,xe);
xlabel(n);ylabel(xe(n));title(even part of x(n));
subplot(2,2,4);stem(n,xo);
xlabel(n);ylabel(xo(n));title(odd part of x(n));
Program 2.4
Write a MATLAB program to perform amplitude scaling and time shift on the
signal x(n) = 1+n; for n = 0 to 2.
function x = y(n)
x=(1.0 + n).*(n>=0 & n<=2);
2. 121 Digital Signal Processing
Note: The above program should be stored as a separate file in the current
working directory
OUTPUT
The input and output waveforms of program 2.4 are shown in fig P2.4.
Program 2.5
Write a MATLAB program to perform convolution of the following two discrete
time signals.
x1(n)=1; 1<n<10 x2(n)=1; 2<n<10
%******************Program to perform convolution of two signals
%******************x1(N)=1; n= 1 to 10 and x2(n)=1; n= 2 to 10
subplot(3,1,2);stem(n,x2);
xlabel(n);ylabel(x2(n));
title(signal x2(n));
subplot(3,1,3);stem(n1,x3);
xlabel(n);ylabel(x3(n));
title(signal, x3(n) =
x1(n)*x2(n));
OUTPUT
F ig P 2 .5 : O u tp u t w av efo rm s o f pro g ra m 2 .5.
The input and output waveforms of
program 2.5 are shown in fig P2.5.
2.18 Exercises
I. Fill in the blanks with appropriate words
1. A signal x(n) may be shifted in time by m units by replacing the independent variable n by _______.
2. The _______ of a signal x(n) is performed by changing the sign of the time base n.
3. If the average power of a signal is finite then it is called _______.
4. The smallest value of N for which x(n + N) = x(n) is true is called _______.
5. In a discrete time signal x(n), if x(n) = x(–n) then it is called _______ signal.
6. In a discrete time signal x(n), if x(–n) = –x(n) then it is called _______ signal.
7. The output of the system with zero input is called _______.
8. A discrete time system is _______ if it obeys the principle of superposition.
9. A discrete time system is _______ if its input-output relationship do not change with time.
10. The response of an LTI system is given by _______ of input and impulse response.
11. If the output of a system depends only on present input then it is called _______.
12. A system is said to be _______ if the output does not depends on future inputs and outputs.
13. An LTI system is causal if and only if its impulse response is _______ for negative values of n.
14. When a system output at any time n depends on past output values, it is called _______ system.
15. An N-point sequence is called _______ if it is symmetric about point zero on the circle.
16. An N-point sequence is called _______ if it is antisymmetric about point zero on the circle.
17. The _______ is called aperiodic convolution.
18. The _______ is called periodic convolution.
19. Appending zeros to a sequence in order to increase its length is called _______.
20. The two methods of sectioned convolutions are _______ and _______method.
2. 123 Digital Signal Processing
21. In _______ method of sectioned convolution, overlapped samples of output sequences are _______.
22. In _______ method, the overlapped samples in one of the output sequences are discarded.
23. The correlation of two different discrete time sequences is called _______ .
24. The cascade of a system and its inverse is _______.
25. The process of recovering the input from the response of a system is called ______ .
Answers
1. n – m 8. linear 15. even 22. overlap save
2. folding 9. time invariant 16. odd 23. cross correlation
3. power signal 10. convolution 17. linear convolution 24. identity system
4. fundamental period 11. memoryless or static 18. circular convolution 25. deconvolution
5. symmetric 12. causal 19. zero padding
6. antisymmetric 13. zero 20. overlap add, overlap save
7. natural response 14. recursive 21. overlap add, added
a) x(n) =
FG 1 IJ n
b) x(n) = −
FG 1 IJ n
c) x(n) =
FG 1 IJ −n
d) x(n) =
FG −1IJ −n
H 4K H 4K H 4K H4K
2. The process of conversion of continuous time signal into discrete time signal is known as,
a) aliasing b) sampling c) convolution d) none of the above
3. If Fs is sampling frequency then the relation between analog frequency F and digital frequency f is,
F F F 2F
a) f = b) f = s c) f = d) f =
2Fs F Fs Fs
4. If Fs is sampling frequency then the highest analog frequency that can be uniquely represented in its
sampled version of discrete time signal is,
Fs 1
a) b) 2Fs c) Fs d)
2 Fs
5. The sampling frequency of the following analog signal, x(t) = 4 sin150pt + 2 cos50pt should be,
a) greater than 75 Hz b) greater than 150 Hz c) less than 150 Hz d) greater than 50 Hz
6. Which of the following signal is the example for deterministic signal?
a) step b) ramp c) exponential d) all of the above
7. For energy signals, the energy will be finite and the average power will be,
a) infinite b) finite c) zero d) cannot be defined
n
8. In a signal x(n), if 'n' is replaced by , then it is called,
3
a) upsampling b) folded version c) downsampling d) shifted version
9. The unit step signal u(n) delayed by 3 units of time is denoted as,
a) u(n + 3) = 1; n ≥ 3 b) u(3 − n) = 1; n ≥ 3 c) u(n − 3) = 1; n ≥ 3 d) u(3n) = 1; n > 3
= 0; n < 3 = 0; n < 3 = 0; n < 3 = 0; n < 3
2. 125 Digital Signal Processing
10. The zero input response (or) natural response is mainly due to,
a) Initial stored energy in the system b) Initial conditions in the system
c) Specific input signal d) both a and b
11. If x(n) = an u(n) is the input signal, then the particular solution yp(n) will be,
a) Kn an u(n) b) K an u(n)
c) K1 an u(n) + K2 an u(n) d) K a–n u(n)
12. The discrete time system, y(n) = x(n–3) – 4x(n–10) is a,
a) dynamic system b) memoryless system c) time varying system d) none of the above
13. An LTI discrete time system is causal if and only if,
a) h(n) ¹ 0 for n < 0 b) h(n) = 0 for n < 0 c) h(n) ¹ ¥ for n < 0 d) h(n) ¹ 0 for n > 0
14. Which of the following system is causal?
a) h(n) = n
FG 1 IJ n
u(n + 1) b) y(n) = x2(n) – x(n+1) c) y(n) = x(–n) +x(2n–1) d) h(n) = n
FG 1 IJ n
u(n)
H 2K H 2K
15. An LTI system is stable, if the impulse response is,
∞ ∞ ∞
a) ∑ h(n) = 0 b) ∑ h(n) < ∞ c) ∑ h(n) ≠ 0 d) either a or b
n= −∞ n= −∞ n= −∞
a) y 1
nej b) 1 y n
n
bg c) ny(n) d) n –1y(n)
22. For a system y(n) = x(n–3) the impulse response of the system and the inverse system will be ––––––
and –––––– respectively.
a) h(n) = d(n + 3), x(n) = y(n – 3) b) h( n) = δ(3n), x(n) = y n ej
3
c) h(n) = d(n – 3), x(n) = y(n + 3) d) h(n) = d(n + 3), x(n) = y(3n)
Chapter 2 - Discrete Time Signals and Systems 2. 126
23. The circular correlation rx 1 x 2 (q) of the sequence x1(n) and x2(n) of length 'N' can be defined by the
equation,
∞ N −1
a) ∑ x1(n) x2 (n − q) b) ∑ x1(n) x∗2 (n − q)
n= −∞ n=0
N −1 ∞
c) ∑ x1(n) x∗2 b(n − q)gN d) ∑ x1(n) x∗2 b(n − q)gN
n=0 n=−∞
Answers
1. b 6. d 11. b 16. a 21. b
2. b 7. c 12. a 17. b 22. c
3. c 8. a 13. b 18. c 23. c
4. a 9. c 14. d 19. c 24. b
5. b 10. a 15. d 20. a 25. d
a) x(n) = sin
5π
n+6
FG IJ
b) x(n) = sin
7n
+π
FG IJ
c) x(n) = cos
4πn FG IJ
8 H K 3 H K 12 H K
d) x(n) = cos
π 2
n
FG IJ
e) x(n) = e j9 n f) x(n) = 4 sin
3πn
+ 5 cos
3πn
32 H K 2 4
E2.2 Determine the even and odd parts of the signals.
π
1 −j n
a) x(n) = 2n b) x(n) = 8e 6 l
c) x(n) = 6, 4, 2, 2 q
a
A
E2.3 a) Consider the analog signal x(t) = 2 sin80pt. If the sampling frequency is 60 Hz, find the sampled
version of discrete time signal x(n). Also find an alias frequency corresponding to Fs = 60 Hz.
b) Consider the analog signals, x1 (t) = 4 cos2π (30t) and x2 (t) = 4 cos 2π (5t). Find a sampling
frequency so that 30 Hz signal is an alias of 5 Hz signal.
c) Consider the analog signal, x(t) = 3 sin40π t − sin100π t + 2cos 50π t. Determine the minimum
sampling frequency and the sampled version of analog signal at this frequency. Sketch the
waveform and show the sampling points. Comment on the result.
E2.4 Determine whether the following signals are energy or power signals.
a) x(n) =
FG 5 IJ n
u( n)
FG
b) x(n) = cos
3π IJ
n
H 9K H 4 K c) x(n) = u(2n) d) x(n) = 2 u(3 – n)
E2.5 Construct the block diagram and signal flow graph of the discrete time systems whose input-
output relations are described by the following difference equations.
a) y(n) = 2y(n – 1) + 2.1 x(n – 1) + 0.5 x(n – 2)
b) y(n) = 1.6 x(n –2) + 0.7 x(n) + 3y(n – 1) + 0.3y(n – 2)
E2.6 Determine the response of the discrete time systems governed by the following difference equations.
a) y(n) = 0.1y(n – 1) + x(n – 1) + 0.7x(n) ; x(n) = 2–n u(n) ; y(–1) = –1
b) y(n) + 2.1y(n – 1) + 0.2y(n – 2) = x(n) + 0.56x(n –1) ; x(n) = u(n) ; y(–2) = 1; y(–1) = –3
Chapter 2 - Discrete Time Signals and Systems 2. 128
E2.7 Test the following systems for time invariance.
a) y(n) = x(n + 1) + x(n + 2) b) y(n) = nax(n) c) y(n) = x2(n + 2) + C d) y(n) = (n –1) x2(n) + C
E2.8 Test the following systems for linearity.
a) y(n) = x2(n) + x3(n – 1) b) y(n) = bx(n + 2) + nex(n) c) y(n) = a x(n) + b x( n)
1 N M
d) y(n) = x(n) + e) y(n) = ∑b m x( n + m) + ∑ c m y( n + m)
x(n) m= −1 m=0
h(n) =
R|S( −4a) n
; n≥0
|T 2b −n
; n<0
E2.12 a) Determine the impulse response for the cascade of two LTI systems having impulse responses,
h1 (n) =
FG 1 IJ n
u(n) and h2 (n) = d(n − 3) h2 (n)
H7 K x (n )
b) Determine the overall impulse response + y (n )
of the interconnected discrete time
system shown in fig E2.12.
h1(n) + h 3 (n)
F ig E 2 .1 2.
Take, h1 (n) =
FG 1 IJ n
u(n) ; h2 (n) =
FG 1 IJ n
u(n) ; h3 (n) =
FG 1 IJ n
u(n)
H 3K H6K H 9K
E2.13 Determine the response of an LTI system whose impulse response h(n) and input x(n) are given by,
l
a) h( n) = 1, 4, 1, −2, 1 q , l
x( n) = 1, 3, 5, −1, −2 q
A A
b) h( n) =
RS1 ; 0≤n≤2
, x( n) = a n u( n); a <1
T0 ; n≥3
E2.14 Perform circular convolution of the two sequences,
l
a) x1 ( n) = 1, 2, −1, 1 ; q l
x2 ( n) = 2, 4, 6, 8 q
b) x ( n) = l0,
1 0.6, −1, 15
., 2 ; q x ( n) = l−2,
2 3, 0.2, 0.7, 0.8 q
E2.15 The input x(n) and impulse response h(n) of an LTI system are given by,
l
x(n) = −1, 1, −1, 1, −1, 1 ; q l
h(n) = −0.5, 0.5, −1, 0.5, −1, −2 q
A A
Find the response of the system using a) Linear convolution, b) Circular convolution.
E2.16 Perform linear convolution of the following sequences by,
a) Overlap add method b) Overlap save method
l
x( n) = 1, −1, 2, 1, −1, 2, +1, −1, +2 q ; l
h( n) = 2, 3, −1 q
2. 129 Digital Signal Processing
E2.17 Perform crosscorrelation of the sequences,
l
x( n) = −1, 2 3, −4, ; q l
h( n) = 2, −1, −3, q
A A
E2.18 Determine the autocorrelation sequence for x(n) = 1, 4, 3, −5, 2 . l q
A
E2.19 Find the inverse system for the following discrete time system,
n
y(n) = ∑ c p x(p − 2) ; for n ≥ 0
p =0
E2.20 A discrete time system is excited by an input x(n), and the response is, y(n) = 4, 3, 6, 7.5, 3, 30, − 8 . m r
A
l
If the impulse response of the system is h(n) = 2, 4, −2 , then what will be the input to the system? q
A
E2.21 Perform circular correlation of the sequence, x(n) = −1, 1, 2, 6 and y(n) = 4, −2, −1, 2 . l q l q
Answers
E2.1 a) periodic; N=16 b) nonperiodic c) periodic; N=6 d) periodic; N=32 e) nonperiodic. f) periodic; N=8
π
E2.2 a) xe ( n) =
1 −2n
a + a2n b) xe ( n) = 8 cos n l q
c) x e ( n) = 1, 1, 2, 6, 2, 1, 1
2 6 A
x (n) = l−1, − 1, − 2, 0, 2, 1, 1q
1 π o
xo (n) = a −2n − a 2n
2
xo (n) = − j8 sin n
6
A
4πn
E2.3 a) x( n) = 2 sin ; Alias frequency = 100Hz b) Fs = 25Hz
3
2 πn πn
c) Fs,min = 100 Hz ; x( nT) = 3sin + 2 cos (sin πn = 0, for integer n)
5 2
The component sin100pt will give always zero samples when
sampled at 100Hz for any value of n (Refer fig E2.3c).
E2.4 a) E = 1.435J ; P = 0 ; Energy signal.
b) E = ¥ ; P = 0.5W ; Power signal.
c) E = ¥ ; P = 0.25W ; Power signal.
d) E = ¥ ; P=2W ; Power signal.
E2.5 a)
x (n ) 2.1x(n −1) y (n ) F ig E 2 .3 c : S a m p lin g p o ints.
−1 2.1
z + +
)
)
−1
−2
(n
x (n
2y
F ig E 2 .5 a.1 : B lo ck −1
0.5
−1
z z
0.5 2
d ia g ra m . x (n ) −1
1 z 2.1 1 1 1 y (n )
−1 −1
z 0.5 2 z
F ig E 2 .5 a.2 : S ig n al flow grap h .
Chapter 2 - Discrete Time Signals and Systems 2. 130
E2.5 b)
x (n ) y (n ) x (n ) 1 0.7 1 1 y (n )
0.7 + +
−1 3 −1
z z
−1 −1
z + 3 z
0.
6
3
1.
−1
−1 z
z
−1
z 1.6 0.3 z
−1
E2.6
LM
a) y(n) = −2.775(0.1) n + 3.375
FG 1 IJ OP u(n)
n
b) y(n) = 0.47 − 0.02 ( −0.1) n + 6.65 ( −2) n u(n)
MN H 2 K PQ
E2.7 a) c) Time invariant b) d) Time variant
E2.8 a) e) Linear b) c) d) Nonlinear
E2.9 a) b) c) d) e) Noncausal
E2.10 a) c) d) e) Stable system b) Unstable system
1 1
E2.11 For stability, 0 < a < and 0 < b <
4 2
FG 1 IJ ( n − 3) LM F 1 I n
FG IJ + FG 3 IJ FG 1IJ OP u(n)
3 1
n n
E2.12 a) h( n) =
H 7K u(n − 3) b) h( n) = 4
MN GH 6 JK −
H K H 2 K H 3K PQ
2 9
n
E2.13 a) y( n) = l1, 7, 18, 20, −6, −16, 5, 3, −2 q b) y( n) = ∑ ak ; for n = 0, 1, 2
A k =0
n
= ∑ a k ; for n > 2
k = n−2
E2.14 a) x3 ( n) = 8, −6, 4, 14 l q l
b) x3 ( n) = 6.08, −0.55, 6.4, −4.28, 0.72 q
A A
E2.15 l
y( n) = 0.5, −1, 2, −2.5, 3.5, −1.5, 1, −0.5, −0.5, 1, −2 q
A
l
E2.16 a) Overlap add method : y( n) = 2, 1, 0, 9, −1, 0, 9, −1, 0, 7, −2 q
b) Overlap save method : y( n) = l*, *, 0, 9, −1, 0, 9, −1, 0, 7, −2q
E2.17 r ( m) = l3, −5, −13, 13, 10, −8q
xy
A
1
E2.18 r ( m) = l2, 3, − 11, − 9, 55, − 9, − 11, 3, 2q
xx E2.19 x( n) = [ y( n + 2) − y( n + 1)] ; for n ≥ −1
cn + 2
A with initial condition x( −2) = y(0)
E2.20 l
x( n) = 2, −2.5, 10, −18.75, 49 q E2.21 rxy (m) = 4, −8, −1, 29 l q
A
Solution for Exercise Problems E2. 1
Digital Signal Processing - A. Nagoor Kani Chapter 2 - Discrete Time Signals and Systems
E2.1. Determine whether the following signals are periodic or not. If periodic, find the fundamental period.
a) x(n) = sin
FG 5π n + 6IJ
H8 K
Solution
b g
Now, x n + N = sin
FG 5π bn + Ng + 6IJ = sin FG 5πn + 6 + 5πN IJ
H8 K H8 8 K
5πN
Since sin (q + 2pM) = sin q, for periodicity, should be integral multiple of 2p.
8
5πN
Let, = M × 2π , M and N are integers.
8
8 16
∴ N = M × 2π × = M
5π 5
16
N = M , if M = 5, 10, 15, 20 ..... N will be a integer.
5
When M = 5 , N = 16.
b
x n + N = sing FG 5π n + 6 + 5π × 16IJ = sin FG 5π n + 6 + 10πIJ = sinFG 5π n + 6IJ = x(n).
H8 8 K H8 K H8 K
\ x(n) is periodic.
b) x(n) = sin
FG 7n + π IJ
H3 K
Solution
b g
x n + N = sin
FG 7(n + N) + πIJ = cos
FG 7n + π + 7NIJ
H 3 K H3 3 K
7N
Since cos (q + 2pM) = cos q, for periodicity, should be equal to integral multiple of 2p.
3
7N 2π × 3 6π
Let, = M × 2π ⇒ N = M = M
3 7 7
Here, N cannot be an integer for any integer value of M, and so, x(n) will not be periodic.
c ) x(n) = cos
FG 4π n IJ
H 12 K
Solution
bg FG π nIJ
x n = cos
H3 K
F π I F nπ + Nπ IJ
xbn + Ng = cos G (n + N)J = cos G
H3 K H 3 3 K
Nπ
= 2πM ⇒ N = 6M
3
For M = 1, 2, 3, ..... N will be integer.
For M = 1, N = 6.
\ x(n) is periodic.
d) x(n) = cos
FG π n IJ
2
H 32 K
Solution
∴ N = 8 M1 \ N = 32 M2
Now, N is integer for M1 = 12, 22, 32, 42 ..... Now, N is integer for M2 = 1, 2, 3, 4 .....
F π n + π32 + π32 nI 2
When N = 32 ; x(n + N) = cos GH 32 32 16 JK 2
FF π I I
= cosG G n + 2πnJ + 16 × 2πJ
2
H H 32 K K
Fπ
= cosG n + 2πnJ
I 2
H 32 K For integer M,
π 2 cos(q + 2pM) = cosq
= cos n = x(n)
32
\ x(n) is periodic with fundamental period, N = 32 samples.
e) x(n) = e j9n
Solution
b g
x n + N = e j9(n+N) = e j9n . e j9N
Since, e j2 πM = 1
2π
Let, b9Ng = M × 2π ⇒ N=
9
M
3πn 3πn
f) Given that, x(n) = 4 sin + 5 cos
2 4
Solution
3πn 3πn
Let, x1(n) = 4 sin Let, x2 (n) = 5 cos
2 4
b g
∴ x1 n + N1 = 4 sin
b
3 π n + N1 g b g
∴ x 2 n + N2 = 5 cos
b
3 π n + N2 g
2 4
= 4 sin
FG 3πn + 3πN IJ 1 .....(1) = 5 cos
FG 3πn + 3πN IJ 2 .....(2)
H2 2 K H4 4 K
3πN1 4 3πN2 8
Let, = 2πM1 ⇒ N1 = M1 Let, = 2πM2 ⇒ N2 = M2
2 3 4 3
Let, M1 = 3 ; \ N1 = 4 Let, M2 = 3 ; \ N2 = 8
Solution for Exercise Problems E2. 3
substitute N1 = 4 in equation (1), substitute N2 = 8 in equation (2),
b
∴ x1 n + N1 = 4 sin g FG 3πn + 3π × 4IJ FG 3πn + 3π × 8IJ
H2 2 K b g
∴ x 2 n + N2 = 5 cos
H4 4 K
F 3πn + 3 × 2πIJ
= 4 sin G F 3πn + 3 × 2πIJ
H2 K = 5 cos G
For integer M, For integer M, H4 K
sin(q + 2pM) = sinq 3πn cos(q + 2pM) = cosq 3πn
= 4 sin = x1(n) = 5 cos = x 2 (n)
2 4
\ x1(n) is periodic with fundamental period, N1 = 4 samples. \ x2(n) is periodic with fundamental period, N2 = 8 samples.
Here, x(n) = x1(n) + x2(n), and x(n) is periodic with period N1 = 4, and x2(n) is periodic with period N2 = 8.
1
a) x(n) = ⇒ x(n) = a −2n
a 2n
Solution
1
x(−n) = ⇒ x(−n) = a 2n
a −2n
Even part of the signal,
1 1 −2n
xe (n) = x(n) + x(−n) = a + a2n
2 2
Odd part of the signal is,
1 1
x0 (n) = x(n) − x(−n) = a −2n − a 2n
2 2
π
−j n
b) x(n) = 8 e 6
Solution
x(n) = 8 e
π
−j n
6
= 8 cos
LM π π
n − j sin n
OP
N 6 6 Q
x( −n) = 8 e
π
− j ( − n)
6 = 8 cos
LM π π
n + j sin n
OP
N 6 6 Q
xe (n) =
LM1 π π π OP π π
× 8 cos n − j sin n + cos n + j sin n = 8 cos n
N2 6 6 6 Q 6 6
1 L π π π π O π
x (n) = × 8 Mcos n − j sin n − cos n − j sin nP = − j8 sin n
0
2 N 6 6 6 6 Q 6
l
c) x(n) = 6, 4, 2, 2 q
A
Solution
l
Given that, x(n) = 6, 4, 2, 2 q
A
x(0) = 6, x(1) = 4, x(2) = 2, x(3) = 2
l
x( −n) = 2, 2, 4, 6 q
A
x(0) = 6; x( −1) = 4; x(−2) = 2; x( −3) = 2
E2. 4 DSP, Chapter 2 -Discrete Time Signals and Systems
1 1
Even part, x e (n) =
2
b
x(n) + x( −n) g Odd part, x 0 (n) =
2
b
x(n) − x( −n) g
at n = –3 ; x(n) + x(–n) = 0 + 2 = 2 n = –3 ; x(n) – x(–n) = 0 – 2 = –2
n = –2 ; 0+2 = 2 n = –2 ; = 0 – 2 = –2
n = –1 ; 0+4 = 4 n = –1 ; = 0 – 4 = –4
n= 0; 6 + 6 = 12 n= 0; = 6–6 = 0
n= 1; 4+0 = 4 n= 1; = 4–0 = 4
n= 2; 2+0 = 2 n= 2; = 2–0 = 2
n= 3; 2+0 = 2 n= 3; = 2–0 = 2
1 1
xe (n) = x(n) + x( −n) x0 (n) = x(n) − x( −n)
2 2
l
xe (n) = 1, 1, 2, 6, 2, 1, 1 q l
x0 (n) = −1, − 1, − 2 , 0, 2, 1, 1 q
A A
E2.3. a) Consider the analog signal x(t) = 2sin80pt. If the sampling frequency is 60 Hz, find the sampled version of
discrete time signal x(n). Also find an alias frequency corresponding to Fs = 60 Hz.
Solution
x(n) = x( t) n
t = nT =
Fs
F 5
Also, f = ⇒ F = fFs = × 60 = 100
Fs 3
b) Consider the analog signals x1(t) = 4 cos 2p (30t), x2(t) = 4 cos 2p (5t). Find a sampling frequency so that
30 Hz signal is an alias of 5 Hz signal.
Solution
Determine the minimum sampling frequency and the sampled version of analog signal at this frequency. Sketch the
waveform and show the sampling points.Comment on the result.
Solution
x(t) = 3 sin 40πt − sin100 πt + 2 cos 50πt ≡ x(t) = 3 sin 2πF1t − sin 2πF2 t + 2cos 2πF3 t
40 100 50
∴ F1 = = 20 Hz ; F2 = = 50 Hz ; F3 = = 25 Hz
2 2 2
Solution for Exercise Problems E2. 5
The maximum analog frequency in the signal is 50 Hz.
The minimum sampling frequency should be twice that of this maximum analog frequency.
Fs ≥ 2 Fmax ⇒ Fs ≥ 2 × 50
Let, Fs = 100Hz
∴ x(nT) = x(t) n
t=nT=
Fs
n n n 2πn π
x(nT) = 3 sin 40π × − sin 100π + 2cos 50π × = 3 sin − sin πn + 2 cos n
100 100 100 5 2
sin πn = 0, for integer values of n.
2πn πn
∴ x(nT) = 3 sin + 2cos
5 2
3 sin 40πt
1
⇒ F1 = 20 Hz, T1 = = 0.05 sec
20
sin 100πt
2cos 50πt
⇒ F3 = 25 Hz, T3 = 0.04
Fs = 100 Hz
Ts = 0.01sec
In the analog signal x(nT), the component sin 100pt will give always zero samples when sampled at 100Hz for any value of n.
This is the drawback in sampling at nyquist rate, which is Fs = 2 Fmax.
E2.4. Determine whether the following signals are energy or power signals.
a) x(n) =
FG 5 IJ n
u(n)
H 9K
Solution
x(n) =
FG 5 IJ u(n)
n
for all n.
H 9K
∴ x(n) = (0.55)n ; n ≥ 0
+∞ ∞ ∞ ∞
2
2 n
∑ d(0.55) i = ∑ b0. 302g
2 n
Energy, E = ∑
n = −∞
x(n) = ∑
n=0
(0.55)n =
n= 0 n= 0
∞
1
∴ E= ∑ (0.302)
n= 0
n
=
1 − 0.302
= 1. 43 Joules
N
1 2
Power, P = Lt
N→∞ 2N + 1
∑ x(n)
n = −N
N N
1 n 1
= Lt
N→∞ 2N + 1
∑ d(0.55) i 2
= Lt
N→∞
∑
2N + 1 n = 0
(0.302)n
n= 0
1 (0.302)N+1 − 1 1 0−1
= Lt = × =0
N→ ∞ 2N + 1 0.302 − 1 ∞ −0.698
P is zero and E is finite.
So x(n) is energy signal.
E2. 6 DSP, Chapter 2 -Discrete Time Signals and Systems
3π 1 + cos 2θ
b) x(n) = cos n cos2 θ =
4 2
Solution
F 1+ cos 2 × 3π n I
∑ GG 4 J
+∞ +∞ 2 +∞
2 3π
Energy, E = ∑ x(n) = ∑ cos JJ n =
n = −∞ GH
n= −∞ 2 4
K n = −∞
F 1I F 3π I
+∞
1 F 3π I 1 +∞ +∞
= G J ∑ G 1 + cos
H 2K H nJ =
2 K 2 GH
∑ 1 + ∑ cos 2 nJK = 2 b∞ + 0g = ∞ n
n = −∞ n = −∞ n = −∞
Power, P = Lt
1 1 N
n = −N
1 1 L O
= Lt M11+414+2144
2N + 1 2 MN
N→ ∞
.....31 + 1 + 11+44
1 + 12.....
44+ 31 + 0P
N termsPQ N terms
1 1 1
= Lt × 2N + 1 = = 0.5
N→ ∞ 2N + 1 2 2
Since P is finite and E is infinite, x(n) is power signal.
3π
It can be shown that cos n is periodic and sum of samples of one period of periodic cosine signal is zero.
2
cos
3π
b
n + N = cos
3πn 3πN
g+
FG IJ 3π 3π
2 2 2 H K n = 0 ; cos
2
n=1 n = 4 ; cos
2
n=1
3 πN 3π 3π
Let, = 2 πM n = 1 ; cos n=0 n = 5 ; cos n=0
2 2 2
4M 3π 3π
∴ N= n = 2 ; cos n = −1 n = 6 ; cos n = −1
3 2 2
Let, M = 3, Now, N = 4 3π 3π
n = 3 ; cos n=0 n = 7 ; cos n=0
2 2
3π
∴ cos n is periodic with
2
period 4 samples.
c) x(n) = u(2n)
Solution
+∞ ∞
2
E = ∑ x(n) = ∑ u(2n) 2
= ∑ u(n) = 1+ 1+ 1+ 1 ..... ∞ = ∞
n = −∞ n= 0 n = even
N N
1 2 1 1
P =
N→∞
Lt
2N + 1 ∑
n = −N
x(n) = Lt
N→∞ 2N + 1 ∑ u(2n)
n= 0
2
= Lt
N→∞
= 1+ 1+......+1
2N + 1 144244 3
N
1+ terms
2
N
FG 1 + 1IJ 1 1
+
1
= Lt
1
1+
N
=
FG IJ Lt
H N 2K = 2 ∞ = 2 =
1
.
N→∞ (2N + 1) 2 H K N→∞ F 1I
NG 2 + J 2+
1 2 4
H NK ∞
Since P is finite, E is infinite, x(n) is power signal.
d ) x(n) = 2 u(3 − n)
Solution
+∞ −3 −3
∑ b2 u(3 − n)g
2 2
E = ∑ x(n) = = ∑ 4 .......1 + 1 + 1 = ∞
14 4244 3 u (3 −n )
n = −∞ n = −∞ n = −∞ inf inite terms
+N −3
1 2 1
P =
N→∞
Lt
(2N + 1) ∑
n = −N
x(n) = Lt
N→∞ (2N + 1) ∑ 4 u(3 − n)
n=N
1 4
= Lt 4 1+ 1+ 1......+1 = Lt N− 2 n −3 −2 −1 0
N→∞ (2N + 1) 1442443 N→∞ (2N + 1)
N − 2 terms
Solution for Exercise Problems E2. 7
N × 4 1−
2 FG IJ 4 1−
FG 2 IJ
∴ P = Lt
N H K =
H ∞ 4
= =2
K
N→∞
N 2+
1 FG IJ 2+
1 2
N H K ∞
Solution
x (n − 1) 2.1 x (n −1)
−1
z 2.1
x (n − 1 )
x (n − 1 )
0.5 x (n − 2)
−1
z z
−1
0.5
x (n − 2) 0.5 0.5 x (n − 2) x (n − 2)
y (n )
y (n )
2 y(n −1 )
−1
z z
−1
y (n − 1)
2
2 y(n −1 )
−1
−2
−1 −1
(n
z
x(n
z 2
2y
0.5
0 .5
−1 −1
z 0.5 2 z
Solution
B lo c k D ia gra m S ig n a l F lo w G ra p h
0.7
x (n ) 0.7 0.7x(n) x (n ) 0.7x(n)
x (n )
x (n )
−1 −1 1.6 x (n −2)
z z
1.6
−1
−1
z
z
x (n −2 )
x (n − 2 ) 1.6 1.6 x (n − 2)
E2. 8 DSP, Chapter 2 -Discrete Time Signals and Systems
B loc k D ia gra m S ign a l F lo w G ra p h
y (n ) 3 y(n −1 ) y (n )
−1
z
−1 3
z
3 y(n − 1 ) y (n −1 )
y (n − 1 )
3
−1
z
−1 z
0.3
0.3 y (n − 2 )
y (n −2 )
0.3
0 .3
6
1.
−1
−1 z
z
−1 −1
z 1.6 0.3 z
E2.6. Determine the response of the discrete time systems governed by the following difference equations.
Solution
Homogeneous solution
When the input is zero the equation (1) can be written as,
ln – 0.1 l(n – 1) = 0
Particular solution
H 2K H 2K
Using the above values for x(n) and y(n) in equation(1) we get,
K
FG 1IJ u(n) − 0.1KFG 1IJ
n (n −1)
u(n − 1) = 0.7 ×
FG 1IJ u(n) + FG 1IJ
n n −1
u(n − 1) .....(4)
H 2K H 2K H 2K H 2K
To determine the value of ‘K’ evaluate equation(4) for n = 1.
K
FG 1IJ u(1) − 0.1KFG 1IJ u(0) = 0.7FG 1IJ u(1) + FG 1IJ u(0)
1 0 1 0
H 2K H 2K H 2K H 2K
1.35
0.5K − 0.1K = 0.35 + 1 ⇒ 0.4K = 1.35 ⇒ K= = 3.375
0.4
Solution for Exercise Problems E2. 9
\ The particular solution yp(n) is given by,
y p (n) = K
FG 1IJ u(n) = 3.375 × FG 1IJ u(n)
n n
.....(5)
H 2K H 2K
Total response
LM
y(n) = C(0.1)n + 3.375 ×
FG 1IJ OP u(n)
n
(or) y(n) = C(0.1)n + 3.375
FG 1IJ n
; for n ≥ 0 .....(6)
MN H 2 K PQ H 2K
At n = 0, from equation (1) we get,
y(0) − 0.1y(−1) = 0.7 x(0) + x( −1) .....(7)
\ y(0) = 0.6
MN H 2 K PQ
b) y(n) + 2.1 y(n – 1) + 0.2 y(n –2) = x(n) + 0.56 x(n – 1) ; x(n) = u(n) ; y(–2) = 1 ; y(–1) = –3.
Solution
y(n) + 2.1 y(n – 1) + 0.2 y(n – 2) = x(n) + 0.56 x(n – 1) .....(1)
Homogeneous Solution
\ ln + 2.1 ln – 1 + 0.2 ln – 2 = 0
λ2 + 2 .1 λ + 0.2 = 0 ⇒ bλ + 0.1g bλ + 2g = 0
\ The roots are, l1 = –0.1, l2= –2.
b g + C b−2g
yh (n) = C1 −0.1
n
2
n
for n ≥ 0
= C b −0.1g + C b −2g
n n .....(3)
1 2 u(n)
E2. 10 DSP, Chapter 2 -Discrete Time Signals and Systems
Particular Solution
Using the above values for x(n) and y(n) in equation(1) we get,
K u(n) + 2.1 K u(n –1) + 0.2 K u(n –2) = u(n) + 0.56 u(n –1) .....(5)
1.56
3.3K = 1. 56 ⇒ K= = 0.47
3.3
\ yp(n) = 0.47 u(n)
\ Total response,
y(n) = yh(n) + yp(n)
y(n) = [C1(–0.1)n + C2(–2)n + 0.47] u(n)
y(n) = C1(–0.1)n + C2(–2)n + 0.47 for n ³ 0. .....(6)
At n = 0 from equation (1) we get,
y(0) + 2.1 y(–1) +0.2 y(–2) = x(0) + 0.56 x(–1) .....(7)
Given, y(–1) = –3, Also, x(n) = u(n)
y(–2) = 1 \ x(0) = 1 and x(–1) = 0.
On substituting the above values in equation (7),
y(0) + 2.1 (–3) + 0.2 (1) = 1 + 0.
y(0) – 6.3 + 0.2 = 1 Þ y(0) – 6.1 = 1
\ y(0) = 1 + 6.1 = 7.1
At n = 1 from equation (1) we get,
y(1) + 2.1 y(0) + 0.2 y(–1) = x(1) + 0.56 x(0)
We know that, y(0) = 7.1 , x(0) = 1
y(–1) = –3 , x(1) = 1
\ y(1) + 2.1 (7.1) + 0.2 (–3) = 1 + 0.56 Þ y(1) + 14.31 = 1.56
\ y(1) = 1.56 – 14.31 = –12.75
Put n = 0 and y(0) = 7.1 in eqaution(6).
y(0) = C1(–0.1)0 + C2(–2)0 + 0.47
7.1 = C1 + C2 + 0.47
\ C1 + C2 = 7.1 – 0.47
\ C1 + C2 = 6.63 .....(8)
Put n= 1 and y(1) = –12.75 in equation(6).
y(1) = C1(–0.1)1 + C2(–2)1 + 0.47
–12.75 = –0.1C1 – 2 C2 + 0.47
0.1C1 + 2C2 = 12.75 + 0.47
\ 0.1C1 + 2 C2 = 13.22 .....(9)
1.9 C1 = –0.04
−0.04
C1 = = − 0.02
1. 9
∴ C2 = 6.63 − C1 = 6.63 + 0.02 = 6.65
\ y(n) = –0.02 (–0.1)n + 6.65 (–2)n + 0.47, for n ³ 0.
= [0.47 – 0.02 (–0.1)n + 6.65 (–2)n] u(n).
Solution for Exercise Problems E2. 11
E2.7. Test the following systems for time invariance.
a) y(n) = x(n + 1) + x(n + 2)
Solution
Given that, y(n) = H {x(n)} = x(n + 1) + x(n + 2)
Response for Delayed Input
y(n –m) = H {x(n – m)} = x(n –m + 1) + x(n – m + 2)
Response for Unshifted Input
y(n) = H {x(n)} = x(n + 1) + x(n + 2)
Delayed Response
l q
y d (n) = z −m H x(n) = z −m x(n + 1) + x(n + 2) = z −m x(n + 1) + z −m x(n + 2)
= x(n − m + 1) + x(n − m + 2)
l q
y d (n) = z −m H x(n) = z −m n a x(n) = n a x(n − m)
l q
y d (n) = z −m H x(n) = z −m x 2 (n + 2) + C = z −m x 2 (n + 2) + C = x 2 (n − m + 2) + C
l q
y d (n) = z −m H x(n) = z −m (n − 1) x 2 (n) + C = (n − 1) x 2 (n − m) + C.
y (n) = H lx (n)q = b x (n + 2) + ne
2 2 2
x 2 ( n)
m r
∴ y 3 (n) = H x 3 (n) = b x 3 (n + 2) + ne x 3 (n)
Solution
Let ‘H ’ be the system.
l q
∴ y(n) = H x(n) = a x(n) + b x(n)
l q
∴ y1(n) = H x1(n) = a x1(n) + b x1(n)
y (n) = H lx (n)q = a
2 2 x 2 (n) + b x 2 (n)
Solution
Let ‘H ’ be the system.
1
∴ y(n) = H x(n) = x(n) +l q x(n)
a1 a2
∴ a1 y1(n) + a 2 y 2 (n) = a1 x1(n) + + a 2 x 2 (n) + .....(1)
x1(n) x 2 (n)
1 1
m
∴ y 3 (n) = H x 3 (n) = x 3 (n) + r x 3 (n)
= a1x1(n) + a 2 x 2 (n) +
a1x1(n) + a 2 x 2 (n)
.....(2)
N M
e) y(n) = ∑b
m = −1
m x(n + m) + ∑c
m =0
m y(n + m)
Solution
N M
∴ y(n) = H x(n) = l q ∑b m x(n + m) + ∑c m y(n + m)
m = −1 m=0
Consider two signals, x1(n) and x 2 (n). Let y1(n) and y 2 (n) be the respective outputs.
N M
l q ∑ b x (n + m) + ∑ c y (n + m)
y1(n) = H x1(n) = m 1 m 1
m= −1 m=0
N M
l q ∑ b x (n + m) + ∑ c y (n + m)
y 2 (n) = H x 2 (n) = m 2 m 2
m= −1 m=0
L N O L M O
a y (n) + a y (n) = a M ∑ b x (n + m) + ∑ c y (n + m)P + a M ∑ b x (n + m) + ∑ c y (n + m)P
N M
.....(1)
1 1 2
MN
2 1
m= −1 PQ MN
m 1
m=0 PQ m 1 2
m= −1
m 2
m=0
m 2
N M
= ∑b
m = −1
m a1x1(n + m) + a 2 x 2 (n + m) + ∑c
m= 0
m y 3 (n + m)
N M M
.....(2)
= a1 ∑b
m = −1
m x1(n + m) + a 2 ∑b
m = −1
m x 2 (n − m) + ∑c
m= 0
m y 3 (n + m)
If y3(n) = H {a1 x1(n) + a2 x2(n)} ; then, y3(n + m) = H {a1 x1(n + m) + a2 x2(n + m)}
N N M M
= a1 ∑b
m = −1
m x1(n + m) + a 2 ∑b
m = −1
m x 2 (n + m) + a1 ∑c
m=0
m y1(n + m) + a 2 ∑c
m=0
m y 2 (n + m)
F b N M I
= a1 GH ∑
m = −1
m x1(n + m) + ∑c
m= 0
m y1(n + m) JK
F b N M I
+ a2 GH ∑
m = −1
m x 2 (n − m) + ∑c
m= 0
m JK
y 2 (n + m) .....(4)
Solution
When, n = –1, y(–1) = a x(–2) + x(1) ; Response depends on future input
n = 0, y(0) = a x(0) + x(0)
n = 1, y(0) = a x(2) + x(1) ; Response depends on future input.
Except n = 0 for all other values of n, the response depends on future input.
Hence the system is noncausal.
n n
c) y(n) = ∑ x(m) + ∑ x(2m)
m = −1 m = −∞
Solution
0 0
n = 0, y(0) = ∑ x(m) + ∑ x(2m) ⇒ y(0) = x( −1) + x(0) + ..... + x(−4) + x(−2) + x(0).....
m = −1 m = −∞
Solution
1
( 0 .3 ) 3
1 1
(0 .3)
n
( 0 .3 ) 2 ( 0 .3 ) 2
1 y (n )
1
0 .3 u (n + 2 ) 0 .3
1 1
X ⇒
0.3
2
( 0 .3 )
−3 −2 −1 0 1 2 −3 −2 −1 0 1 2 −3 −2 −1 0
Solution
4
y(n) = ∑ x(n − k) = x(n + 4)
k = −4
+ x(n + 3) + x(n + 2) + x(n + 1) + x(n) + x(n − 1) + x(n − 2) + x(n − 3) + x(n − 4)
+∞ 4 0 4
∴ ∑ h(n)
n = −∞
= ∑ (8)
n = −∞
n
= ∑ (8) + ∑ (8)
n = −∞
n
n =1
n
∞
= ∑ (8)
n= 0
−n
+ 81 + 8 2 + 8 3 + 84
=
∞
F 1I
∑ GH 8 JK
n
+ 4680 =
∞
∑ (0.125) n
+ 4680 =
1
+ 4680
n= 0 n= 0 1 − 0.125
= 4681.14 = Constant
Hence it is stable system.
E2. 16 DSP, Chapter 2 -Discrete Time Signals and Systems
e) y(n) = x(n – 3)
If x(n) = d(n), then y(n) = h(n)
d(n – 3) = 1, only
\ h(n) = d(n – 3) when n = 3, and
∞ +∞ zero for all other
∴ ∑
n = −∞
h(n) = ∑
n = −∞
δ(n − 3) = 1
values of n
h(n) =
|RS ( −4a) n
; n ≥ 0
T|(2b) −n
; n < 0
Solution
The condition to be satisfied for the stability of the system is,
+∞ −1 ∞
∞ ∞
= ∑ |2b| n
+ ∑ |4a| n
n =1 n= 0
∞ ∞
= ∑ |2b| n
− |2b|0 + ∑ |4a| n
n= 0 n= 0
∞
1
If 0 <|2b| < 1, then ∑|2b| n
=
1 − |2b|
n= 0
∞
1
If 0 <|4a| < 1, then ∑|4a| n
=
1 − |4a|
n= 0
+∞
1 1
∴ ∑ h(n) = 1 − |2b| − 1+ 1 − |4a| = Constant
n = −∞
E2.12. a) Determine the impulse response for the cascade of two LTI systems having impulse responses,
h1 (n) =
FG 1 IJ n
∴ h(n) = ∑
∞
h2 (m) h1(n − m) =
∞
∑ δ(m − 3)
FG 1IJ n −m
=
∞
∑ δ(m − 3)
FG 1IJ FG 1IJ
n −m
m= 0 m=0
H 7K m=0
H 7K H 7K
FG 1IJ ∑ δ(m − 3) FG 1IJ
=
n ∞ −m
H 7K H 7K m=0
7
F 1I F 1I for n ≥ 3
∴ h(n) = G J G J
n −3
H 7K H 7K
F 1I
h(n) = G J u(n − 3) for all n.
n− 3
H 7K
Solution for Exercise Problems E2. 17
b) Determine the overall impulse response of the interconnected discrete time system shown in fig E2.12.
Take, h1 (n) =
FG 1 IJ n
u(n) ; h2 (n) =
FG 1 IJ n
u(n) ; h3 (n) =
FG 1 IJ n
u(n)
H 3K H6K H 9K
h 2 ( n)
x (n )
+ y (n )
h 1 ( n) + h 3 ( n)
Solution F ig E 2 .1 2
The given system can be redrawn as,
h 2 (n)
x (n ) y (n ) x (n ) y (n )
h 2 (n) + h 2 (n) + [(h 2 (n) + h1(n)) ∗ h3 (n)]
+ h 3 (n)
h1(n) x (n ) h(n) y (n )
b g
h(n) = h2 (n) + h1(n) + h2 (n) ∗ h3 (n) = h2 (n) + h1(n) ∗ h3 (n) + h2 (n) ∗ h3 (n) b g b g
Evaluation of h1(n) * h3(n)
∞
h1(n) ∗ h3 (n) = ∑ h (m) h (n − m)
m= −∞
1 3
=
n
∑ h (m) h (n − m) =
n
∑ GH 3 JK
F 1I FG 1IJ
m n −m
=
FG 1IJ ∑ FG 1IJ
n n m
9m =
FG 1IJ ∑ FG 9 IJ
n n m
m= 0
1 3
m= 0
H 9K H 9K H 3K m= 0
H 9K H 3K m= 0
FG 9 IJ − 1 n +1
F 1I H 3 K
n
= G J
H 9K 9 − 1
3
FG 9 IJ 9 − 1 n
FG 9 IJ 9 − 1 n
F 1I H 3 K 3
= G J
n
= G J
F 1I H 3 K 3 F 1I L 1 F 9 I 9 − 1 OP
= G J M G J
n n n
H 9K 9
−1
H 9K 2 H 9 K MN 2 H 3 K 3 2 PQ
3
3 F 1I
G J u(n) − 21 FGH 91IJK u(n) for all 'n'
n n
=
2 H 3K
Evaluation of h2(n) * h3(n)
h2 (n) ∗ h3 (n) =
+∞
∑ h (m) h (n − m) = ∑ h (m) h (n − m)
F 1I FG 1IJ = FG 1IJ ∑ FG 1IJ FG 1IJ
n
=
n
∑ GH 6 JK
m n −m n n m −m
m= −∞
2 3
m= 0
H 9K H 9K H 6K H 9K
2 3
m= 0 m= 0
F 1 I F 1I n
F 1I F 3 I = FG 1IJ H 2 K
n
= G J ∑ G J 9 = G J ∑ G J
m n
F 1I M H 2 K P
n m n n
H 9 K H 2 K H 9 K 3 − 1 = GH 9 JK MM 1 PP
m
H 9K H 6K m=0 m=0
2 MN 2 PQ
F 1I L F 3 I 3 − 2OP = FG 1IJ LMFG 3 IJ 3 − 2OP = FG 1IJ FG 3 IJ 3 − 2 FG 1IJ
= G J M2G J
n n n n n n n
H 9 K MN H 2 K 2 PQ H 9 K MNH 2 K PQ H 9 K H 2 K H 9K
F 3I F 1In
F 1 I F 1I F 1 I n
= G J 3 − 2 G J = 3 G J − 2 G J = 3 G J u(n) − G J u(n) for all n.
F 1I n n n n
H 18 K H 9K H 6K H 9K H 6K H 9K
Overall Impulse Response
b
h(n) = h2 (n) + h1(n) ∗ h3 (n) + h2 (n) ∗ h3 (n) g b g
E2. 18 DSP, Chapter 2 -Discrete Time Signals and Systems
h(n) =
FG 1IJ u(n) + LMFG 3 IJ FG 1IJ u(n) − FG 1IJ FG 1IJ u(n)OP + LM3 FG 1IJ u(n) − FG 1IJ u(n)OP
n n n n n
H 6K MNH 2 K H 3 K H 2 K H 9 K PQ MN H 6 K H 9 K PQ
FG 1IJ u(n) − 3 FG 1IJ u(n) + 3 FG 1IJ u(n) =
n n n
LM4 F 1I n
FG IJ
3 1
n
3 FG 1IJ OP u(n)
n
⇒ h(n) = 4
H 6K 2 H 9K 2 H 3K MN GH 6 JK −
H K
2 9
+
2 H 3 K PQ
E2.13. Determine the response of an LTI system whose and impulse response h(n) and input x(n) are given by,
a) l
h(n) = 1, 4, 1, − 2, 1 q
A
l
x(n) = 1, 3, 5, − 1, − 2 q
A
Solution
The response y(n) of the system is given by convolution of x(n) and h(n).
+∞
y(n) = x(n) ∗ h(n) = ∑ x(m) h(n − m)
m= −∞
The 9 samples of output sequence are computed by table method as shown below.
m –5 –4 –3 –2 –1 0 1 2 3 4 5 6 7
x(m) 1 3 5 –1 –2
h(m) 1 4 1 –2 1
h(–m) 1 –2 1 4 1
h(–3–m) 1 –2 1 4 1
h(–2–m) 1 –2 1 4 1
h(–1–m) 1 –2 1 4 1
h(0 – m) 1 –2 1 4 1
h(1 – m) 1 –2 1 4 1
h(2 – m) 1 –2 1 4 1
h(3 – m) 1 –2 1 4 1
h(4 – m) 1 –2 1 4 1
h(5 – m) 1 –2 1 4 1
3
When n = −3 ; y(−3) = ∑ x(m) h(−3 − m) = 0 + 0 + 0 + 0 + 1+ 0 + 0 + 0 + 0 = 1
m = −5
3
When n = −2 ; y(−2) = ∑ x(m) h(−2 − m) = 0 + 0 + 0 + 4 + 3 + 0 + 0 + 0
m = −4
=7
3
When n = −1 ; y(−1) = ∑ x(m) h(−1 − m) = 0 + 0 + 1+ 12 + 5 + 0 + 0 = 18
m = −3
3
When n = 0 ; y(0) = ∑ x(m) h(0 − m)
m = −2
= 0 − 2 + 3 + 20 − 1+ 0 = 20
3
When n = 1 ; y(1) = ∑ x(m) h(1 − m)
m = −1
= 1 − 6 + 5 − 4 − 2 = −6
Solution for Exercise Problems E2. 19
4
When n = 2 ; y(2) = ∑ x(m) h(2 − m) = 0 + 3 − 10 − 1− 8 + 0 = −16
m = −1
5
When n = 3 ; y(3) = ∑ x(m) h(3 − m) = 0 + 0 + 5 + 2 − 2 + 0 + 0 = 5
m = −1
6
When n = 4 ; y(4) = ∑ x(m) h(4 − m) = 0 + 0 + 0 − 1+ 4 + 0 + 0 + 0 = 3
m = −1
7
When n = 5 ; y(5) = ∑ x(m) h(5 − m) = 0 + 0 + 0 + 0 − 2 + 0 + 0 + 0 + 0 = −2
m = −1
l
∴ y(n) = 1, 7, 18, 20, − 6, − 16, 5, 3, − 2 q
A
E2.13. b) h(n) =
|RS1 ; 0 ≤n≤ 2
T|0 ; n ≥ 3
n
x(n) = a u(n) ; |a| < 1
Solution
x (m ) h (m ) h ( −m )
0
a =1 1 1 1
a
2
a
3
a
0 1 2 3 m 0 1 2 3 6 m −3 −2 −1 0
4 5 −6 −5 −4 m
By convolution formula,
∞
y(n) = ∑ x(m) h(n − m)
m = −∞
∞ ∞
When n = 0 ; y(0) = ∑ x(m) h(0 − m) = ∑ v0 (m)
m=0 m=0
x (m ) h( −m ) v 0 (m )
0 0
a =1 1 1=a
a
a
2
x ⇒
3
0
a ∴ y (0) = a
0 1 2 3 m −3 −2 −1 0 1 m 0 1 2 m
∞ ∞
When n = 1 ; y(1) = ∑ x(m) h(1 − m) = ∑ v1(m)
m=0 m=0
x (m ) h (1 − m ) v 1 (m )
0
0
a =1 1=a
1 1
a 1
a
a
2
⇒
3
x y (1) = a
0
+ a
1
a
0 1 2 3 m −2 −1 0 1 m −1 0 1 2 m
Similarly,
When, n = 2 ; y(2) = a0 + a1 + a2
When, n = 3 ; y(3) = a1 + a2 + a3
When, n = 4 ; y(4) = a2 + a3 + a4
When, n = 5 ; y(5) = a3 + a4 + a5
n
∴ y(n) = ∑a
k =0
k
; for n = 0, 1, 2
n
= ∑a
k =n − 2
k
; for n > 2
E2. 20 DSP, Chapter 2 -Discrete Time Signals and Systems
E2.14. Perform circular convolution of the two sequences,
l
a) x1 (n) = 1, 2, − 1 −1 q and x2 (n) = 2, 4, 6, 8 l q
A A
Solution
N −1
Let x 3 (n) = x1(n) ∗ x 2 (n) = ∑ x (m) x
m=0
1 2,n (m) ; x 2,n (m) = x 2 ((n − m))N ; N = 4
x 1 ( 2 ) = −1 x 1( m ) x 1( 0 ) = 1 x2 (2) = 6 x 2 (m ) x 2 (0 ) = 2 x 2 (2 ) = 6 x 2 ( −m ) x 2 (0) = 2
x 1 ( 3 ) = −1 x 2 (3 ) = 8 x 2 (1) = 4
3 3
When n = 0 ; x 3 (0) = ∑ x (m) x
m=0
1 2,0 (m) = ∑ v (m) = 2 + 16 − 6 − 4 = 8
m=0
0
2 8 16
−1 x 1 (m ) 1 x 6 x 2 ,0 ( m ) 2 ⇒ −6 v 0 (m ) 2
−1 4 −4
3 3
When n = 1 ; x 3 (1) = ∑ x (m) x
m=0
1 2,1(m) = ∑ v (m) = 4 + 4 − 8 − 6 = −6
m=0
1
2 2 4
−1 6 −6
3 3
When n = 2; x 3 (2) = ∑ x (m) x
m=0
1 2,2 (m) = ∑ v (m) = 6 + 8 − 2 − 8 = 4
m=0
2
2 4 8
−1 x1(m) 1 x 2 x 2 , 2 (m) 6 ⇒ −2 v 2 (m ) 6
−1 8 −8
3 3
When n = 3 ; x 3 (3) = ∑ x (m) x
m=0
1 2,3 (m) = ∑ v (m) = 8 + 12 − 4 − 2 = 14
m=0
3
2 6 12
−1 x 1(m) 1 x 4 x 2, 3 (m ) 8 ⇒ −4 v 3 (m) 8
−1 2 −2
l
x 3 (n) = 8, − 6, 4, 14 q
A
b) Perform the circular convolution of the two sequences,
l
x1 (n) = 0, 0.6, − 1, 1.5, 2 ; x2 (n) = −2, 3, 0.2, 0.7, 0.8 q l q
A A
Solution
The response x3(n) of the system is given by convolution of x1(n) and x2(n).
Solution for Exercise Problems E2. 21
N −1 4
x 3 (n) = x1(n) ∗ x 2 (n) = ∑ x (m) x ((n − m))
m=0
1 2 N = ∑ x (m) x ((n − m))
m=0
1 2 5
4
= ∑ x (m) x
m=0
1 2,n (m)
m –4 –3 –2 –1 0 1 2 3 4
When n = 0 ;
4
x 3 (0) = ∑ x (m) x
m=0
1 2,0 (m) = x1(0) x 2,0 (0) + x1(1) x 2,0 (1) + x1(2) x 2,0 (2) + x1(3) x 2,0 (3) + x1(4) x 2,0 (4)
b g b
= (0 × −2) + 0.6 × 0.8 + −1 × 0.7 + 1.5 × 0.2 + 2 × 3 = 6.08 g b g b g
Similarly
g b g b b g b g
When n = 1 ; x 3 (1) = (0 × 3) + 0.6 × −2 + −1 × 0.8 + 1.5 × 0.7 + 2 × 0.2 = −0.55
A
E2.15. The input x(n) and impulse response h(n) of an LTI system are given by,
x(n) = l − 1, 1, − 1, 1, − 1, 1 q and l
h(n) = −0.5, 0.5, − 1, 0.5, − 1, − 2 q
A A
Find the response of the system using,
a) Linear Convolution
b) Circular Convolution
Solution
m –6 –5 –4 –3 –2 –1 0 1 2 3 4 5 6 7 8 9
x(m) –1 1 –1 1 –1 1
4
When n = −1, y( −1) = ∑ x(m) h
m = −6
−1(m)
= x( −6) h−1(−6) + x( −5) h−1( −5) + x( −4)h−1(−4) + x( −3) h−1(−3) + x( −2) h−1(−2) + x( −1)h−1(−1)
+ x(0) h−1(0) + x(1) h−1(1) + x(2)h−1(2) + x(3) h−1(3) + x(4) h−1(4)
= 0 + 0 + 0 + 0 + 0 + (−1 × − 0.5 ) + 0 + 0 + 0 + 0 + 0 = 0.5
4
When n = 0 ; y(0) = ∑ x(m) h (m) 0 b g b
= 0 + 0 + 0 + 0 + −1 × 0.5 + 1 × −0.5 + 0 + 0 + 0 + 0 = −1 g
m= −5
4
When n = 1 ; y(1) = ∑ x(m) h (m) 1 b g b g b
= 0 + 0 + 0 + −1 × −1 + 1 × 0.5 + −1 × −0.5 + 0 + 0 + 0 = 2 g
m= −4
4
When n = 2 ; y(2) = ∑ x(m) h (m) 2 b g b g b
= 0 + 0 + −1 × 0.5 + 1 × −1 + −1 × 0.5 + 1 × −0.5 + 0 + 0 = −2.5 g b g
m= −3
4
When n = 3 ; y(3) = ∑ x(m) h (m) 3 b g b g b g b
= 0 + −1 × −1 + 1 × 0.5 + −1 × −1 + 1 × 0.5 + −1 × −0.5 + 0 = 3.5 g b g
m= −2
4
When n = 4 ; y(4) = ∑ x(m) h (m) 4 b g b g b g b
= −1 × −2 + 1 × −1 + −1 × 0.5 + 1 × −1 + −1 × 0.5 + 1 × −0.5 = −1.5 g b g b g
m= −1
5
When n = 5 ; y(5) = ∑ x(m) h (m) 5 b g b g b g b
= 0 + 1 × −2 + −1 × −1 + 1 × 0.5 + −1 × −1 + 1 × 0.5 + 0 = 1 g b g
m= −1
6
When n = 6 ; y(6) = ∑ x(m) h (m) 6 b g b g b
= 0 + 0 + −1 × −2 + 1 × −1 + −1 × 0.5 + 1 × −1 + 0 + 0 = −0.5 g b g
m= −1
7
When n = 7 ; y(7) = ∑ x(m) h (m) 7 b g b g b
= 0 + 0 + 0 + 1 × −2 + −1 × −1 + 1 × 0.5 + 0 + 0 + 0 = −0.5 g
m= −1
8
When n = 8 ; y(8) = ∑ x(m) h (m) 8 b g b
= 0 + 0 + 0 + 0 + −1 × −2 + 1 × −1 + 0 + 0 + 0 + 0 = 1 g
m= −1
9
When n = 9 ; y(9) = ∑ x(m) h (m) 9 b g
= 0 + 0 + 0 + 0 + 0 + 1 × −2 + 0 + 0 + 0 + 0 + 0 = − 2
m= −1
l
y(n) = 0.5, − 1, 2, − 2.5, 3.5, − 1. 5, 1, − 0.5, − 0.5, 1, − 2 q
A
Solution for Exercise Problems E2. 23
b) Response of LTI system using circular convolution
The response y(n) is 11-point sequence. The y(n) start at n = –1 and end of n = 9. Hence both x(n) and h(n)
should be converted to 11-point sequence such that they start at n = –1 and end at n = 9 by appending zeros for
missing samples.
l
∴ x(n) = −1, 1, − 1, 1, − 1, 1, 0, 0, 0, 0, 0 q
A
l
h(n) = 0, − 0.5, 0.5, − 1, 0.5, − 1, − 2, 0, 0, 0, 0 q
A
9 9
Now, y(n) = x(n) ∗ h(n) = ∑ x(m) h((n − m))
m= −1
11 = ∑ x(m) h (m) ;
m= −1
n where hn (m) = h((n − m))11
m –10 –9 –8 –7 –6 –5 –4 –3 –2 –1 0 1 2 3 4 5 6 7 8 9
x(m) –1 1 –1 1 –1 1 0 0 0 0 0
9
When n = −1 ; y( −1) = ∑ x(m) h −1(m) b g
= −1 × −0.5 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 0.5
m= −1
9
When n = 0 ; y(0) = ∑ x(m) h (m) 0 b g b g
= −1 × 0.5 + 1 × −0.5 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = −1
m= −1
9
When n = 1 ; y(1) = ∑ x(m) h (m) 1 b g b g b g
= −1 × −1 + 1 × 0.5 + −1 × −0.5 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 2
m= −1
9
When n = 2 ; y(2) = ∑ x(m) h (m) 2 b g b g b g b g
= −1 × 0.5 + 1 × −1 + −1 × 0.5 + 1 × −0.5 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = −2.5
m= −1
9
When n = 3 ; y(3) = ∑ x(m) h (m) 3 b g b g b g b g b
= −1 × −1 + 1 × 0.5 + −1 × −1 + 1 × 0.5 + −1 × −0.5 + 0 + 0 + 0 + 0 + 0 + 0 = 3.5 g
m= −1
9
When n = 4 ; y(4) = ∑ x(m) h (m) 4 b g b g b g b g b
= −1 × −2 + 1 × −1 + −1 × 0.5 + 1 × −1 + −1 × 0.5 + 1 × −0.5 + 0 + 0 + 0 + 0 + 0 = −1.5 g b g
m= −1
9
When n = 5 ; y(5) = ∑ x(m) h (m) 5 b g b g b g b
= 0 + 1 × −2 + −1 × −1 + 1 × 0.5 + −1 × −1 + 1 × 0.5 + 0 + 0 + 0 + 0 + 0 = 1 g b g
m= −1
9
When n = 6 ; y(6) = ∑ x(m) h (m) 6 b g b g b g b
= 0 + 0 + −1 × −2 + 1 × −1 + −1 × 0.5 + 1 × −1 + 0 + 0 + 0 + 0 + 0 = −0.5 g
m= −1
9
When n = 7 ; y(7) = ∑ x(m) h (m) = 0 + 0 + 0 + b1× −2g + b−1 × −1g + b1× 0.5g + 0 + 0 + 0 + 0 + 0 = −0.5
m= −1
7
E2. 24 DSP, Chapter 2 -Discrete Time Signals and Systems
9
When n = 8 ; y(8) = ∑ x(m) h (m) 8 b g b g
= 0 + 0 + 0 + 0 + −1 × −2 + 1 × −1 + 0 + 0 + 0 + 0 + 0 = 1
m= −1
9
When n = 9 ; y(9) = ∑ x(m) h (m) 9 b g
= 0 + 0 + 0 + 0 + 0 + 1 × −2 + 0 + 0 + 0 + 0 + 0 = −2
m= −1
m –2 –1 0 1 2 3 4
x(m) 1 –1 2
h(m) 2 3 –1
h(–m)=h0(m) –1 3 2
h1(m) –1 3 2
h2(m) –1 3 2
h3(m) –1 3 2
h4(m) –1 3 2
+∞
y1(n) = x1(n) ∗ h(n) = ∑ x (m) h(n − m)
m= −∞
1
+∞
= ∑ x (m) h (m) ;
m= −∞
1 n n = 0, 1, 2, 3, 4
The convolution of section –2 and 3 are identical to that of section -1 except the starting value of n.
∴ y 2 (n) = l 2, 1, 0, 7, − 2 q
An= 3
∴ y 3 (n) = l 2, 1, 0, 7, − 2 q
An= 6
Overall Output
n 0 1 2 3 4 5 6 7 8 9 10
y1(n) 2 1 0 7 –2
y2(n) 2 1 0 7 –2
y3(n) 2 1 0 7 –2
y(n) 2 1 0 9 –1 0 9 –1 0 7 –2
l
y(n) = 2, 1, 0, 9, − 1, 0, 9, − 1, 0, 7, − 2 q
Overlap save Method
l
x(n) = 1, − 1, 2, 1, − 1, 2, 1, − 1, 2 q
h(n) = l2, 3, − 1 q
N1 = 9, N2 = 3, Let N3 = 3
x1(n) = 1, n = 0 x 2 (n) = 1 , n = 3 x 3 (n) = 1, n = 6
= −1, n = 1 = −1, n = 4 = −1, n = 7
= 2, n = 2 = 2, n = 5 = 2, n = 8
Let, y1(n), y2(n) and y3(n) be output of linear convolution of x1(n), x2(n) and x3(n) with h(n) respectively.
Now each output will consists of 3 + 3 – 1 = 5 samples. Hence convert x1(n), x2(n), x3(n) and h(n) to 5 sample sequence as shown
below.
x1(n) = 1, n = 0 x 2 (n) = 1, n = 3 x 3 (n) = 1, n = 6
= −1, n = 1 = −1, n = 4 = −1, n = 7
= 2, n = 2 = 2, n = 5 = 2, n = 8
= 1, n = 3 = 1, n = 6 = 0, n = 9
= −1, n = 4 = −1, n = 7 = 0, n = 10
Convolution of Section 1
m –4 –3 –2 –1 0 1 2 3 4
x1(m) 1 –1 2 1 –1
h(m) 2 3 –1 0 0
h(–m)= h0(m) 0 0 –1 3 2 0 0 –1 3
h1(m) 0 0 –1 3 2 0 0 –1
h2(m) 0 0 –1 3 2 0 0
h3(m) 0 0 –1 3 2 0
h4(m) 0 0 –1 3 2
E2. 26 DSP, Chapter 2 -Discrete Time Signals and Systems
N −1 4
y1(n) = x1(n) ∗ h(n) = ∑ x (m) h((n − m)) = ∑ x (m) h (m) ;
m=0
1 n
m=0
1 n where hn (m) = h((n − m))5
4
When n = 0 ; y1(0) = ∑ x (m) h (m) =
m=0
1 0 2 + 0 + 0 − 1 − 3 = −2
4
When n = 1 ; y1(1) = ∑ x (m) h (m) =
m=0
1 1 3 − 2 + 0 + 0 + 1= 2
4
When n = 2 ; y1(2) = ∑ x (m) h (m) =
1 2 − 1− 3 + 4 + 0 + 0 = 0
m=0
4
When n = 3 ; y1(3) = ∑ x (m) h (m) =
m=0
1 3 0 + 1+ 6 + 2 + 0 = 9
4
When n = 4 ; y1(4) = ∑ x (m) h (m) =
m=0
1 4 0 + 0 − 2 + 3 − 2 = −1
∴ y1(n) = l − 2, 2, 0, 9, − 1 q
A
n=0
Convolution of Section 2
The output of convolution of section -2 will be identical to that of section-1 except the starting value of n.
∴ y 2 (n) = l − 2, 2, 0, 9, − 1 q
A
n= 3
Convolution of Section 3
m –4 –3 –2 –1 0 1 2 3 4 5 6 7 8 9 10
x3(m) 1 –1 2 0 0
h(m) 2 3 –1 0 0
h0(m) 0 0 –1 3 2
h6(m) 0 0 –1 3 2 0 0 –1 3
h7(m) 0 0 –1 3 2 0 0 –1
h8(m) 0 0 –1 3 2 0 0
h9(m) 0 0 –1 3 2 0
h10(m) 0 0 –1 3 2
10 10
y 3 (n) = x 3 (n) ∗ h(n) = ∑ x (m) h((n − m)) = ∑ x (m) h (m) ;
m=6
3 5
m=6
3 n where hn (m) = h((n − m))5
10
When n = 6 ; y 3 (6) = ∑ x (m) h (m) =
m=6
3 6 2+0+0+0+0 = 2
10
When n = 7 ; y 3 (7) = ∑ x (m) h (m) =
3 7 3−2+0+0+0=1
m=6
10
When n = 8 ; y 3 (8) = ∑ x (m) h (m) =
m=6
3 8 − 1− 3 + 4 + 0 + 0 = 0
10
When n = 9 ; y 3 (9) = ∑ x (m) h (m) =
3 9 0 + 1+ 6 + 0 + 0 = 7
m=6
10
When n = 10 ; y 3 (10) = ∑ x (m) h
m=6
3 10 (m) = 0 + 0 − 2 + 0 + 0 = −2
∴ y 3 (n) = l 2, 1, 0, 7, − 2 q
A n= 6
Solution for Exercise Problems E2. 27
Overall Output
n 0 1 2 3 4 5 6 7 8 9 10
y1(n) –2 2 0 9 –1
y2(n) –2 2 0 9 –1
y3(n) 2 1 0 7 –2
y(n) * * 0 9 –1 0 9 –1 0 7 –2
The 6 samples of crosscorrelation sequence are computed using table method as shown below.
n –2 –1 0 1 2 3 4 5
x(n) –1 2 3 –4
y(n) 2 –1 –3
y(n–(–1))= y–1(n) 2 –1 –3
y(n–0)= y0(n) 2 –1 –3
y(n–1)= y1(n) 2 –1 –3
y(n–2)= y2(n) 2 –1 –3
y(n–3)= y3(n) 2 –1 –3
y(n–4)= y4(n) 2 –1 –3
3
When m = −1 ; rxy ( −1) = ∑ x(n) y
n= −2
−1(n) = 0+0+3+0+0+0 = 3
3
When m = 0 ; rxy (0) = ∑ x(n) y (n) =
n= −1
0 0 + 1 − 6 + 0 + 0 = −5
3
When m = 1 ; rxy (1) = ∑ x(n) y (n) =
n=0
1 − 2 − 2 − 9 + 0 = −13
3
When m = 2 ; rxy (2) = ∑ x(n) y (n) =
n=0
2 0 + 4 − 3 + 12 = 13
E2. 28 DSP, Chapter 2 -Discrete Time Signals and Systems
4
When m = 3 ; rxy (3) = ∑ x(n) y (n) =
n=0
3 0 + 0 + 6 + 4 + 0 = 10
5
When m = 4 ; rxy (4) = ∑ x(n) y
n=0
4 (n) = 0 + 0 + 0 − 8 + 0 + 0 = −8
∴ rxy (m) =
RS 3, −5, − 13, 13, 10, − 8
UV
T A W
E2.18. Determine the autocorrelation sequence for x(n) = {1, 4, 3, –5, 2}
-
Solution
The autocorrelation sequence rxx(m) is given by,
+∞
rxx (m) = ∑ x(n) x(n − m)
n= −∞
n –5 –4 –3 –2 –1 0 1 2 3 4 5 6 7
x(n) 1 4 3 –5 2
x–4(n) 1 4 3 –5 2
x–3(n) 1 4 3 –5 2
x–2(n) 1 4 3 –5 2
x–1(n) 1 4 3 –5 2
x0(n) 1 4 3 –5 2
x1(n) 1 4 3 –5 2
x2(n) 1 4 3 –5 2
x3(n) 1 4 3 –5 2
x4(n) 1 4 3 –5 2
3
When m = −4 ; rxx ( −4) = ∑ x(n) x
n= −5
−4 (n) = 0+0+0+0+2+0+0+0+0 = 2
3
When m = −3 ; rxx ( −3) = ∑ x(n) x
n= −4
−3 (n) = 0+0+0− 5+8+0+0+0 = 3
3
When m = −2 ; rxx ( −2) = ∑ x(n) x
n= −3
−2 (n) = 0 + 0 + 3 − 20 + 6 + 0 + 0 = −11
3
When m = −1 ; rxx ( −1) = ∑ x(n) x
n= −2
−1(n) = 0 + 4 + 12 − 15 − 10 + 0 = −9
3
When m = 0 ; rxx (0) = ∑ x(n) x (n) =
n= −1
0 1+ 16 + 9 + 25 + 4 = 55
4
When m = 1 ; rxx (1) = ∑ x(n) x (n) =
n= −1
1 0 + 4 + 12 − 15 − 10 + 0 = −9
5
When m = 2 ; rxx (2) = ∑ x(n) x (n) =
n= −1
2 0 + 0 + 3 − 20 + 6 + 0 + 0 = −11
Solution for Exercise Problems E2. 29
6
When m = 3 ; rxx (3) = ∑ x(n) x (n) = 3 0+0+0− 5 + 8+0+0+0= 3
n= −1
7
When m = 4 ; rxx (3) = ∑ x(n) x (n) = 4 0+0+0+0+2+ 0+0+0+0= 2
n= −1
Solution n
Given that, y(n) = ∑ c x(p − 2)
p=0
p
; for n ≥ 0
0
When n = 0 ; y(0) = ∑ c x(p − 2) = c x(−2) = x(−2)
p=0
p 0
⇒ x(−2) = y(0)
1
When n = 1 ; y(1) = ∑ c x(p − 2) = c x(−2) + c x(−1)
p=0
p 0 1
= x( −2) + c x( −1)
1
= y(0) + c x(−1) ⇒ x( −1) = y(1) − y(0)
c
2
When n = 2 ; y(2) = ∑ c x(p − 2) = c x(−2) + c x(−1) + c x(0)
p=0
p 0 1 2
E2.20. A discrete time system is excited by an input x(n), and the response is, y(n) = 4, 3, 6, 7.5, 3, 30, − 8 . If the l q
A
l q
impulse response of the system is h(n) = 2, 4, − 2 , then what will be the input to the system?
A
Solution
Let, N1 = Number of samples in x(n)
Now, N3 = N1 + N2 – 1 Þ N1 = N3 – N2 + 1 = 7 – 3 + 1 = 5 samples
1 LM n −1 O
x(n) = y(n) −
MN ∑ x(m) h(n − m)PP
h(0) m=0 Q
y(0) 4
When n = 0 ; x(0) = = =2
h(0) 2
LM
1 OP 1 1
When n = 1 ; x(1) =
MN ∑
h(0)
y(1) −
m= 0
x(m) h(1 − m) =
PQ h(0)
y(1) − x(0) h(1) =
2
3 − (2 × 4) = −2.5
1 L O 1 1
1
When n = 2 ; x(2) = M
h(0) MN
y(2) − ∑ x(m) h(2 − m)P =
PQ h(0) y(2) − x(0) h(2) − x(1) h(1) =
2
b g
6 − (2 × −2) − −2.5 × 4 = 10
m=0
E2. 30 DSP, Chapter 2 -Discrete Time Signals and Systems
1 LM 2 O= 1
When n = 3 ; x(3) = y(3) −
MN ∑ x(m) h(3 − m)PP y(3) − x(0) h(3) − x(1) h(2) − x(2) h(1)
h(0) m=0 Q h(0)
1
=
2
b g
7.5 − (2 × 0) − −2.5 × −2 − (10 × 4) = −18 . 75
1 LM 2 O= 1
When n = 4 ; x(4) = y(4) −
MN ∑ x(m) h(4 − m)PP y(4) − x(0) h(4) − x(1) h(3) − x(2) h(2) − x(3) h(1)
h(0) m=0 Q h(0)
1
=
2
b g
3 − (2 × 0) − −2.5 × 0 − (10 × −2) − (−18.75 × 4) = 49
l q l
∴ x(n) = x(0), x(1), x(2), x(3), x(4) = 2, − 2.5, 10, − 18.75, 49 q
A
E2.21. Perform circular correlation of the sequences, x(n) = −1, 1, 2, 6 l q and l q
y(n) = 4, − 2, − 1, 2
Solution
Let rxy (m) be the sequence obtained by circular correlation of x(n) and y(n).
q 0 1 2 3 4 5 6 7
x(n) –1 1 2 6
y(n) 4 –2 –1 2
y0(n) 4 –2 –1 2 4 –2 –1 2
y1(n) 2 4 –2 –1 2 4 –2 –1
y2(n) –1 2 4 –2 –1 2 4 –2
y3(n) –2 –1 2 4 –2 –1 2 4
3
When m = 0 ; rxy (0) = ∑ x(n) y (n) = −4 − 2 − 2 + 12 = 4
0
n= 0
3
When m = 1 ; rxy (1) = ∑ x(n) y (n) = −2 + 4 − 4 − 6 = −8
1
n=0
3
When m = 2 ; rxy (2) = ∑ x(n) y (n) = 1+ 2 + 8 − 12 = −1
2
n= 0
3
When m = 3 ; rxy (3) = ∑ x(n) y (n) = 2 − 1+ 4 + 24 = 29
3
n= 0
l
∴ rxy (m) = 4, − 8, − 1, 29 q
Chapter 3
Z-Transform
3.1 Introduction
Transform techniques are an important tool in the analysis of signals and systems. The Laplace
transforms are popularly used for analysis of continuous time signals and systems. Similarly Z-transform
plays an important role in analysis and representation of discrete time signals and systems. The Z-transform
provides a method for the analysis of discrete time signals and systems in the frequency domain which is
generally more efficient than its time domain analysis.
The Z-transform of x(n) will convert the time domain signal x(n) to z-domain signal X(z), where the
signal becomes a function of complex variable z.
jv z -plan e
The complex variable z is defined as, z1
r1
z = u + jv = r ejw ω1
−u u
where, u = Real part of z ; v = Imaginary part of z
r = u 2 + v 2 = Magnitude of z −jv
F ig 3 .1 : z-p la ne .
ω = tan −1 v = Phase or Argument of z
u
The u and v takes value from –¥ to +¥ . A two dimensional complex plane with values of u on
horizontal axis and values of v on vertical axis as shown in fig 3.1 is called z-plane. A circle with radius r1 in
z-plane represents all values of z1 having same magnitude r1 with variable phase w 1, where w 1 = 0 to 2p.
History of Z-Transform
A transform of a sampled signal or sequence was defined in 1947 by W. Hurewicz as,
∞
z [ f ( kT)] = ∑ f ( kT) z− k
k =0
Chapter 3 - Z - Transform 3. 2
which was later denoted in 1952 as Z-transform by a sampled-data control group at Columbia University led
by professor John R. Raggazini and including L.A. Zadeh, E.I. Jury, R.E. Kalman, J.E. Bertram, B. Friedland
and G.F. Franklin, (Source : www.ling.upenn.edu).
Definition of Z-Transform
Let, x(n) = Discrete time signal
X(z) = Z-transform of x(n)
The Z-transform of a discrete time signal, x(n) is defined as,
∞
X( z) = ∑ x( n ) z − n ; where, z is a complex variable. .....(3.1)
n = −∞
n = −∞
Since the time index n is defined for both positive and negative values, the discrete time signal x(n) in
equation (3.1) is considered to be two-sided and the transform is called two-sided Z-transform. If the signal
x(n) is one-sided signal, [i.e., x(n) is defined only for positive value of n] then the Z-transform is called
one-sided Z-transform.
The one-sided Z-transform of x(n) is defined as,
+∞
.....(3.2)
X( z) = Z{x( n)} = ∑ x( n) z − n
n= 0
The computation of X(z) involves summation of infinite terms which are functions of z. Hence it is
possible that the infinite series may not converge to finite value for certain values of z. Therefore for every
X(z) there will be a set of values of z for which X(z) can be computed. Such a set of values will lie in a particular
region of z-plane and this region is called Region Of Convergence (ROC) of X(z).
Inverse Z-Transform
Let, X(z) be Z-transform of x(n). Now the signal x(n) can be uniquely determined from X(z) and its
region of convergence (ROC).
The inverse Z-transform of X(z) is defined as,
x( n) =
1
2 πj z
c
X(z) z n −1 dz .....(3.3)
We also refer x(n) and X(z) as a Z-transform pair and this relation is expressed as,
Z
x(n) ¬ ® X(z)
Z-1
3. 3 Digital Signal Processing
Proof :
∴
zc
X(z) zn −1 dz =
zc k = −∞
+∞
∑ x(k) z n −1− k
dz
Interchanging the order of
=
+∞
∑
k = −∞
x(k)
z c
zn −1− kdz summation and integration.
Multiply and divide by 2pj.
∑
k = −∞
x(k)
1
2πj z
c
z n −1− k
dz .....(3.4)
1
2πj c z
zn −1− k dz = 1 ; k = n
= 0 ; k ≠ n
On applying Cauchy integral theorem the equation (3.4) reduces to,
z c
X(z) zn −1 dz = 2πj x(n)
+∞
∑ x(k)
k = −∞ n=k
= x(n)
∴ x(n) =
1
2πj zc
X(z) zn −1 dz
Geometric Series
The Z-transform of a discrete time signal involves convergence of geometric series. Hence the following
two geometric series sum formula will be useful in evaluating Z-transform.
1. Infinite geometric series sum formula.
If C is a complex constant and 0 < |C|< 1, then,
∞
1
∑= Cn = 1− C
.....(3.5)
n 0
N −1 N
1 − CN CN − 1 C N +1 − 1
When C ≠ 1, ∑ Cn =
1− C
=
C −1
or ∑ Cn =
C −1
.....(3.6)
n= 0 n= 0
N−1 N
When C = 1, ∑= Cn = N or ∑= Cn = N +1 .....(3.7)
n 0 n 0
Note : The infinite geometric series sum formula requires that the magnitude of C be strictly less than unity,
but the finite geometric series sum formula is valid for any value of C.
Chapter 3 - Z - Transform 3. 4
= x( − (N − 1)) z(N −1) + ....... + x( −2)z2 + x( −1) z + x(0) F ig 3.3 : R O C o f fin ite
d u ra tio n a ntica u sa l sig n a l.
In the above summation, when z = ¥ , all the terms except the last term become infinite. Hence the X(z)
exists for all values of z, except, z = ¥ . Therefore, the ROC of X(z) is entire z-plane, except z = ¥ .
Case iii : Finite duration, two-sided (noncausal) signal
Let, x(n) be a finite duration signal with N-samples, defined in the range –M £ n £ + M,
N −1
where, M =
2
l q
∴ x(n) = x( − M),......., x( −2), x( −1), x(0), x(1), x(2), ........x( M)
3. 5 Digital Signal Processing
Now, the Z-transform of x(n) is,
+M
X( z) = ∑− x(n) z− n
n= M
= x( − M ) z M + ....... + x( −2) z2 + x( −1) z + x(0) + x(1)z−1 + x(2)z −2 +......+ x( M) z − M
x(1) x(2) x( M)
= x( − M ) z M + ........ + x( −2) z2 + x( −1) z + x(0) + + + ...... +
z z2 zM
jv
z -p la n e
In the above summation, when z = 0, the terms with negative
R O C is e ntire u
power of z attain infinity and when z = ¥ , the terms with positive
z -p la n e ex c ep t
power of z attain infinity. Hence X(z) converges for all values of z, z = 0 an d z = ∞
except z = 0 and z = ¥ . Therefore, the ROC is entire z-plane, except F ig 3.4 : R O C o f fin ite
z = 0 and z = ¥ . d u ra tio n tw o -sid ed sig n a l.
Here the condition to be satisfied for the convergence of X(z) is, jv z -p lan e
0 < |r 2
–1
z| < 1 r2
| z|
\ |r2–1 z| < 1 Þ < 1 ⇒ |z| < |r2 |
| r2 | R O C of u
n
The term |r2| represents a circle of radius r2 in z-plane as shown in fig 3.6. x (n) = r 2 ; n ≤ 0
From the above analysis we can say that X(z) converges for all points internal to
the circle of radius r2 in z-plane. Therefore, the ROC of X(z) is interior of the F ig 3.6 : R O C o f infinite
circle of radius r2 as shown in fig 3.6. d u ratio n left-sid ed sign a l.
Sequence ROC
Finite, right-sided (causal) Entire z-plane except z = 0
Finite, left-sided (anticausal) Entire z-plane except z = ¥
Finite, two-sided (noncausal) Entire z-plane except z = 0 and z = ¥
Infinite, right-sided (causal) Exterior of circle of radius r1, where |z| > r1
Infinite, left-sided (anticausal) Interior of circle of radius r2, where |z| < r2
Infinite, two-sided (noncausal) The area between two circles of radius r2 and r1
where, r2 > r1, and r1< |z| < r2, (i.e., |z| >r1, and, |z| < r2)
3. 7 Digital Signal Processing
Table 3.2 : Characteristic Families of Signals and Corresponding ROC
0
n
x (n ) E n tire z -p la n e
L e ft-sid ed jv
(o r a n tic a usa l) e xc e pt z = ∞
z -p la n e
0
n
x (n ) E n tire z -p la n e
Tw o -side d
(o r n o nc a u sa l) jv e xc e pt z = 0
z -p la n e a nd z = ∞
0
n
Infinite Duration Signals
x (n ) jv
r1 z -p la n e
R ig h t-side d
(o r c au sal)
u
|z|> r 1
0
n
jv z-p la n e
x (n )
L e ft-sid ed
(o r a n tic a usa l)
u
r2
0
n
|z| < r 2
jv z -p la n e
x (n )
Tw o -side d r 1 < |z | < r 2
(o r n o nc a u sa l) r1
[|z | > r 1
a nd |z |< r 2 ]
r2
u
0
n
Chapter 3 - Z - Transform 3. 8
Example 3.1
Determine the Z-transform and their ROC of the following discrete time signals.
a) x(n) = {3, 4, 2, 7} b) x(n) = {6, 8, 9, 3} c) x(n) = {2, 4, 6, 8, 10}
- - -
Solution
a) Given that, x(n) = {3, 4, 2, 7}
-
i.e., x(0) = 3 ; x(1) = 4 ; x(2) = 2 ; x(3) = 7 ; and x(n) = 0 for n < 0 and for n > 3.
By the definition of Z-transform,
∞
Z {x(n)} = X(z) = ∑ x(n) z −n
n = −∞
The given sequence is a finite duration sequence defined in the range n = 0 to 3, hence the limits of
summation is changed to n = 0 to n = 3.
3 jv
∴ X ( z) = ∑
n = 0
x(n) z −n z -p la n e
The given sequence is a finite duration sequence defined in the range n = 3 to 0, hence the limits of
summation is changed to n = 3 to 0.
jv
0
z -p la n e
∴ X(z) = ∑
x(n) z
n = −3
−n
R O C is e ntire u
= x(−3) z3 + x( −2) z 2 + x(−1) z + x(0)
z -p la n e ex c e pt
= 6z3 + 8z2 + 9z + 3 z=∞
In X(z), when z = ¥ , except the last term all other terms become infinite. Hence X(z) will be finite for all
values of z, except z = ¥ . Therefore, the ROC is entire z-plane except z = ¥.
Example 3.2
Determine the Z-transform and their ROC of the following discrete time signals.
a) x(n) = u(n) b) x(n) = 0.3n u(n) c) x(n) = 0.8n u(n 1) d) x(n) = 0.3n u(n) + 0.8n u(n1)
Solution
a) Given that, x(n) = u(n)
The u(n) is a discrete unit step signal, which is defined as,
u(n) = 1 ; for n ³ 0 Infinite geometric series sum formula
= 0 ; for n < 0 ∞
1
By the definition of Z-transform,
∑
n = 0
Cn =
1− C
; if , 0 <|C|< 1
∞ ∞
Z{x(n)} = X(z) = ∑ x(n) z −n
= ∑ u(n) z −n
n = −∞ n = 0
∞ ∞
1 Using infinite geometric series sum formula.
= ∑ z −n = ∑ (z −1 n
) =
1 − z −1
n = 0 n = 0
1 z jv
= = 1 z -p la n e
1− 1 / z z − 1 |Z |=
.8
=0
u(n 1) = 0 ; for n ³ 0
|z |
=1 ; for n £ 1 u
ROC
\ x(n) = 0 ; for n ³ 0
n
= 0.8 ; for n £ 1
By the definition of Z-transform,
∞ −1
Z{x(n)} = X(z) = ∑ x(n) z −n = ∑ 0.8n z −n
n = −∞ n = −∞
∞ ∞ ∞
= ∑ 0.8 −n zn = ∑ (0.8 −1 z)n = ∑ (0.8 −1 z)n − 1 (0.81 z)0 = 1
n = 1 n = 1 n = 0
n n |z |
= Z{0.3 u(n)} + Z{0.8 u(−n − 1)} Using linearity property. =0 u
.8
z z
= − Using the results of (b) and (c). ROC
z − 0.3 z − 0.8
2 2
z(z − 0.8) − z(z − 0.3) z − 0.8z − z + 0.3z −0.5z
= = 2 = 2
(z − 0.3) (z − 0.8) z − 0.8z − 0.3z + 0.24 z − 1.1z + 0.24
+∞
X 2(z) = Z{x 2(n)} = ∑ x (n) z
n = −∞
2
−n
.....(3.9)
+∞ +∞
∴ Z{a1x1(n)+a2 x 2(n)} = ∑
n = −∞
a1x1(n)+a2 x 2 (n) z− n = ∑
n = −∞
a1x1(n) z− n +a2 x2 (n) z− n
+∞ +∞ +∞ +∞
= ∑
n = −∞
a1x1(n) z− n + ∑
n = −∞
a2 x2(n)z− n = a1 ∑
n = −∞
x1(n) z− n +a2 ∑ x (n)z
n = −∞
2
−n
2. Shifting property
Case i: Two-sided Z-transform
The shifting property of Z-transform states that, Z-transform of a shifted signal shifted by m-units of
time is obtained by multiplying zm to Z-transform of unshifted signal.
Let, Z{x(n)} = X(z)
Now, by shifting property,
Z{x(n–m)} = z–m X(z)
Z{x(n+m)} = zm X(z)
Proof :
By definition of Z-transform,
+∞
X(z) = Z{x(n)} = ∑ x(n) z −n
.....(3.10)
n = −∞
+∞
∴ Z{x(n − m)} = ∑ x(n − m) z −n
n = −∞
+∞
Let, n m = p, \ n = p + m
= ∑ x(p) z −(m + p)
when n ® -¥, p ® -¥
p = −∞
+∞ when n ® +¥, p ® +¥
= ∑ x(p) z −m
z− p
p = −∞
+∞ +∞
= z− m ∑ x(p) z
p = −∞
−p
= z− m ∑ x(n) z
n = −∞
−n
Let, p → n
+∞
= ∑ x(p) z
p = −∞
−p
zm
+∞ +∞
= zm ∑
p = −∞
x(p) z− p = zm ∑ x(n) z
n = −∞
−n
Let, p → n
Proof :
By definition of one-sided Z-transform,
+∞
X( z) = Z {x(n)} = ∑ x(n) z −n
.....(3.11)
n= 0
+∞
∴ Z {x(n − m)} = ∑
n=0
x(n − m) z− n
+∞ Multiply by zm and z m
= ∑
n=0
x(n − m) z− n zm z− m
+∞
= z− m ∑
n=0
x(n − m) z−( n − m)
Let, n m = p,
+∞ when n ® 0, p ® m
= z −m
∑ x(p) z −p
when n ® +¥, p ® +¥
p = −m
+∞ −1
= z− m ∑ x(p) z− p + z− m ∑ x(p) z− p
p= 0 p = −m
+∞ m
= z− m ∑ x(p) z− p + z− m ∑ x(− p) zp Let p = n, in first summation.
p= 0 p=1 Let p = i, in second summation.
+∞ m
= z− m ∑ x(n) z− n + z− m ∑ x(− i) zi Using equation (3.11).
n=0 i=1
m
= z− m X(z) + ∑ x( − i) z−(m − i) .....(3.12)
i=1
Note : In equation (3.12) if x(i) for i = 1 to m are zero then the shifting property of one-sided Z-transform
for delayed signal will be same as that for two-sided Z-transform.
3. 13 Digital Signal Processing
By definition of one-sided Z-transform,
+∞
Z {x(n+m)} = ∑
n=0
x(n + m) z− n
Multiply by zm and z m
+∞
= ∑
n=0
x(n + m) z− n zm z− m
+∞ Let, n + m = p,
= zm ∑ x(n + m) z −( n + m)
when n ® 0 , p ® m
n=0
+∞
when n ® + ¥ , p ® + ¥
= z m
∑ x(p) z− p
p=m
+∞ m −1
= zm ∑ x(p) z− p − zm ∑ x(p) z− p
p=0 p=0 Let p = n, in first summation.
+∞ m −1 Let p = i, in second summation.
= zm ∑ x(n) z− n − zm ∑ x(i) z− i
n=0 i=0 Using equation (3.11).
m −1
m
= z X(z) − ∑ x(i) z m−i
.....(3.13)
i=0
Note : In equation (3.13) if x(i) for i = 0 to m 1 are zero then the shifting property of one-sided Z-transform
for advanced signal will be same as that for two-sided Z-transform.
3. Multiplication by n (or Differentiation in z-domain)
If Z{x(n)} = X(z)
d
m
then Z nx(n) = − zr dz
X(z)
In general,
t FGH IJ X(z) m
d
o
Z n m x(n) = − z
Kdz
d F d F F d F IJ I ..... IJ I
= −z −z ..... G − z
dz GH dz GH H
G −z dzd
dz H
X(z)
K JK K JK
1444444424444444
3
m − times
Proof :
By definition of Z-transform,
+∞
X( z) = Z{x(n)} = ∑ x(n) z −n
.....(3.14)
n = −∞
+∞
∴ Z {n x(n)} = ∑
n = −∞
n x(n) z− n
+∞
= ∑
n = −∞
n x(n) z− n z z−1 Multiply by z and z 1
+∞
= −z ∑
n = −∞
x(n) − n z− n − 1
= −z ∑
+∞
x(n)
LM d z OP
−n d −n
z = − n z− n −1
n = −∞ N dz Q dz
+∞
d Interchanging summation
= −z
dz ∑ x(n) z
n = −∞
−n
and differentiation.
d
= −z X(z) Using equation (3.14).
dz
Chapter 3 - Z - Transform 3. 14
4. Multiplication by an exponential sequence, an (or Scaling in z-domain)
If Z{x(n)} = X(z)
o t
then Z a n x(n) = X(a −1z)
Proof :
By definition of Z-transform,
+∞
Z{x(n)} = ∑ x(n) z −n
.....(3.15)
n = −∞
+∞
∴ Z {a n x(n)} = ∑
n = −∞
a n x(n) z− n
+∞
= ∑ x(n) (a −1z)− n .....(3.16)
n = −∞
The equation (3.16) is similar
= X(a −1z) to the form of equation (3.15).
5. Time reversal
If Z{x(n)} = X(z)
then Z{x(–n)} = X(z–1)
Proof :
By definition of Z-transform,
+∞
Z{x(n)} = ∑ x(n) z −n
.....(3.17)
n = −∞
+∞
∴ Z {x( − n)} = ∑
n = −∞
x( − n) z− n
Let, p = n
+∞ when n ® -¥, p ® +¥
= ∑
p = −∞
x(p) zp when n ® +¥, p ® -¥
+∞
= ∑ x(p) (z−1 )− p .....(3.18)
p = −∞ The equation (3.18) is similar
= X(z−1) to the form of equation (3.17).
6. Conjugation
If Z{x(n)} = X(z)
then Z{x*(n)} = X*(z*)
Proof :
By definition of Z-transform,
+∞
X(z) = Z{x(n)} = ∑ x(n) z −n
.....(3.19)
n = −∞
+∞
∴ Z {x ∗(n)} = ∑
n = −∞
x∗(n) z− n
LM+∞ OP ∗
=
MN ∑
n = −∞
x(n) (z∗ )− n
PQ The equation (3.20) is similar
.....(3.20)
∗
= X(z∗ ) to the form of equation (3.19).
= X ∗( z∗ )
3. 15 Digital Signal Processing
7. Convolution theorem
If Z{x1(n)} = X1(z)
and Z{x2(n)} = X2(z)
then Z{x1(n) * x2(n)} = X1(z) X2(z)
+∞
where, x1 (n) ∗ x2 (n) = ∑
m = −∞
x1 (m) x2 (n − m) .....(3.21)
Proof :
By definition of Z-transform,
+∞
X1(z) = Z{x1(n)} = ∑ x (n) z
1
−n
.....(3.22)
n = −∞
+∞
X 2(z) = Z{x 2 (n)} = ∑ x (n) z 2
−n
.....(3.23)
n = −∞
+∞
∴ Z {x1(n) ∗ x 2 (n)} = ∑
n = −∞
x1(n) ∗ x 2 (n) z− n
8. Correlation property
If Z{x(n)} = X(z) and Z{y(n)} = Y(z)
then Z{rxy(m)} = X(z) Y(z –1)
+∞
where, rxy (m) = ∑ x(n) y(n − m)
n= −∞
.....(3.24)
Proof :
By definition of Z-transform,
+∞
X(z) = Z {x(n)} = ∑ x(n) z −n
.....(3.25)
n = −∞
+∞
Y(z) = Z{y(n)} = ∑ y(n) z −n
.....(3.26)
n = −∞
Chapter 3 - Z - Transform 3. 16
+∞
∴ Z { rxy (m)} = ∑
m = −∞
rxy (m) z− m
+∞ LM +∞ OP
= ∑
m = −∞ MN ∑
n = −∞
x(n) y(n − m) z− m
PQ Using equation (3.24).
+∞ +∞
= ∑ ∑
m = −∞ n = −∞
x(n) y(n − m) z− m z− n zn Multiply by zn and z n
+∞ +∞
= ∑ x( n) z− n ∑ y( n − m) z( n − m)
n = −∞ m = −∞ Let, n m = p \ m = n p
+∞ +∞
when m ® -¥, p ® +¥,
= ∑
n = −∞
x( n) z −n
∑
p = −∞
y(p) z p
when m ® +¥, p ® -¥.
LM +∞ OP LM +∞ OP
=
MN ∑
n = −∞
x( n) z− n
PQ MN ∑
p = −∞
y(p) (z−1)− p
PQ Using equations (3.25)
−1
= X(z) Y(z ) and (3.26).
x(0) = Lt X(z)
z→∞
Proof :
+∞
X( z) = ∑ x(n) z −n
n=0
Lt X( z) = Lt
LMx(0) +
x(1)
+
x(2)
+
x(3)
+ ......
OP
z→∞ z→∞ N z z2 z3 Q
= x(0) + 0 + 0 + 0 + ......
∴ x(0) = Lt X( z)
z→∞
3. 17 Digital Signal Processing
10. Final value theorem
Let x(n) be a one-sided signal defined in the range 0 £ n £ ¥.
Now, if Z {x(n)} = X(z),
then the final value of x(n) [i.e., x(¥ )] is given by,
x(∞) = Lt (1 − z −1 ) X(z) or x( ∞) = Lt
FG z − 1IJ X(z)
z→1 z→1 H zK
Proof :
By definition of one-sided Z-transfrom,
+∞
m r ∑ x(n) z
Z x(n) =
n=0
−n
.....(3.27)
+∞
m
∴ Z x(n − 1) − x(n) = r ∑ n=0
x(n − 1) − x(n) z− n
(LHS) (RHS)
m
LHS = Z x(n − 1) − x(n) r
m r m r
= Z x(n − 1) − Z x(n) Using linearity property.
−1
= z X( z) + x( −1) − X(z) Using shifting property and equation (3.27).
−1
= x( −1) − (1 − z ) X(z)
= Lt x(−1) − (1− z−1) X(z) Taking limit z → 1
z→1
+∞
RHS = ∑
n=0
x(n − 1) − x(n) z− n
+∞
= Lt
z→1 ∑
n=0
x(n − 1) − x(n) z− n Taking limit z ® 1
+∞
On applying limit z ® 1, the term zn
= ∑
n=0
x(n − 1) − x(n) becomes unity.
p Changing the summation index from
= Lt
p→∞ ∑
n=0
x(n − 1) − x(n) 0 to p and then taking limit p ® ¥.
m
Z x1 (n) x2 (n) = r 1
2 πj z
C
X (v) X
1 2
FH vz IK v −1
dv
x1(n) =
1
2πj z
C
X1( z) zn − 1 dz =
1
2πj z
C
X1( v) v n − 1 dv let, z = v .....(3.30)
+∞
X 2( z) = ∑ x ( n) z
2
−n
.....(3.31)
n = −∞
Using the definition of Z-transform, the Z {x1(n) x2(n)} can be written as,
+∞
m
Z x1( n) x 2( n) = r ∑ x (n) x (n) z
1 2
−n
n = −∞
L1 OP
=
+∞
∑ MM 2πj
n = −∞ N z
C
X1( v ) v n − 1 dv x 2( n) z− n
PQ Using equation (3.30).
=
1
2πj z
C
X1( v )
+∞
∑
n = −∞
x 2( n) z− n v n v −1 dv Interchanging the order of
summation and integration.
L OP
` =
1
2πj z
C
1
MN
+∞
n = −∞
F zI
X ( v ) M ∑ x ( n) G J
H vK 2
−n
PQ v
−1
dv
=
1
2πj z
C
X (v ) X FH z IK v dv
1
v 2
−1
Using equation (3.31).
∑
+∞
n = −∞
x1 (n) x∗2 (n) =
1
2πj z
C
FH IK
X1(z) X∗2 1∗ z−1 dz
z
3. 19 Digital Signal Processing
Proof :
x1(n) =
1
2πj z
C
X1( z) zn − 1 dz =
1
2πj z
C
X1( v) v n − 1 dv let, z = v .....(3.32)
Using the definition of Z - transform, the Z x1(n) x∗2( n) can be written as, { }
+∞
{
Z x1( n) x∗2( n) = } ∑ x1(n) x∗2(n) z− n
n = −∞
.....(3.34)
On substituting for x1(n) from equation (3.32) in equation (3.34) we can write,
LM 1 OP
+∞
∑ x (n) x (n) z
n = −∞
1
∗
2
−n
=
+∞
∑
n = −∞ MN 2πj z
C
X1( v ) v n − 1 dv x∗2( n) z− n
PQ
LM x (n) z v OP v dv
=
1
2πj z
C
X1( v)
MN ∑ n = −∞
+∞
PQ
∗
2
−n n −1
Interchanging the
order of summation
and integration.
L F zI O
=
1
2πj z
C
1
MN
+∞
X ( v ) M ∑ x ( n) G J P v dv
H v K PQ
n = −∞
∗
2
−n
−1
L Fz I O −n
∗
=
1
2πj z
C
1
MN
+∞
X ( v ) M ∑ x ( n) G J P v dv
H v K PQ
n = −∞
2
∗