Copyright ? 2001,S,K,Mitra 1
Stability Condition of a
Discrete-Time LTI System
? BIBO Stability Condition - A discrete-time
LTI system is BIBO stable if the output
sequence {y[n]} remains bounded for any
bounded input sequence{x[n]}
? A discrete-time LTI system is BIBO stable
if and only if its impulse response sequence
{h[n]} is absolutely summable,i.e,
??? ?
?
???n
nh ][S
Copyright ? 2001,S,K,Mitra 2
Stability Condition of a
Discrete-Time LTI System
? Proof,Assume h[n] is a real sequence
? Since the input sequence x[n] is bounded we
have
? Therefore
??? xBnx ][
][][][][][ knxkhknxkhny
kk
???? ??
?
???
?
???
x
k
x BkhB ?? ?
?
???
][S
Copyright ? 2001,S,K,Mitra 3
Stability Condition of a
Discrete-Time LTI System
? Thus,S < implies
indicating that y[n] is also bounded
? To prove the converse,assume that y[n] is
bounded,i.e.,
? Consider the input given by
? ??? yBny ][
yBny ?][
??
?
??
????
0
0
][if,
][if] ),[s g n (][
nhK
nhnhnx
Copyright ? 2001,S,K,Mitra 4
Stability Condition of a
Discrete-Time LTI System
where sgn(c) = +1 if c > 0 and sgn(c) =
if c < 0 and
? Note,Since,{x[n]} is obviously
bounded
? For this input,y[n] at n = 0 is
? Therefore,implies S <
1?
1?K
yBny ?][ ?
1?][nx
?
?
???
??
k
khkhy ][])[sg n(][ 0 S ??? yB
Copyright ? 2001,S,K,Mitra 5
Stability Condition of a
Discrete-Time LTI System
? Example - Consider a causal discrete-time
LTI system with an impulse response
? For this system
? Therefore if for which the
system is BIBO stable
? If,the system is not BIBO stable
S ?? | | 1? ?
| | 1? ?
][)(][ nnh n ???
?
???
?
??? ??
?
?
?
??? 1
1
0n
n
n
n n ][
S 1??if
Copyright ? 2001,S,K,Mitra 6
Causality Condition of a
Discrete-Time LTI System
? Let and be two input sequences
with
? The corresponding output samples at
of an LTI system with an impulse response
{h[n]} are then given by
][nx1 ][nx2
][][ nxnx 21 ? onn ?for
onn ?
Copyright ? 2001,S,K,Mitra 7
Causality Condition of a
Discrete-Time LTI System
??
?
?
?
???
????
0
222
k
o
k
oo knxkhknxkhny ][][][][][
?
?
???
??
1
2
k
o knxkh ][][
??
?
?
?
???
????
0
111
k
o
k
oo knxkhknxkhny ][][][][][
?
?
???
??
1
1
k
o knxkh ][][
Copyright ? 2001,S,K,Mitra 8
Causality Condition of a
Discrete-Time LTI System
? If the LTI system is also causal,then
? As
? This implies
][][ nxnx 21 ? onn ?for
][][ oo nyny 21 ?
??
?
?
?
?
???
0
2
0
1
k
o
k
o knxkhknxkh ][][][][
??
?
???
?
???
???
1
2
1
1
k
o
k
o knxkhknxkh ][][][][
Copyright ? 2001,S,K,Mitra 9
Causality Condition of a
Discrete-Time LTI System
? As for the only way
the condition
will hold if both sums are equal to zero,
which is satisfied if
][][ nxnx 21 ? onn ?
??
?
???
?
???
???
1
2
1
1
k
o
k
o knxkhknxkh ][][][][
0?][kh for k < 0
Copyright ? 2001,S,K,Mitra 10
Causality Condition of a
Discrete-Time LTI System
? A discrete-time LTI system is causal if and
only if its impulse response {h[n]} is a causal
sequence
? Example - The discrete-time system defined
by
is a causal system as it has a causal impulse
response
]3[]2[]1[][][ 4321 ??????????? nxnxnxnxny
}{]}[{ 4321 ?????nh
?
Copyright ? 2001,S,K,Mitra 11
Causality Condition of a
Discrete-Time LTI System
? Example - The discrete-time accumulator
defined by
is a causal system as it has a causal impulse
response given by
[ ] [ ]
n
y n x
? ??
? ?
l
l
][][][ nnh
n
???? ?
????
?
Copyright ? 2001,S,K,Mitra 12
Causality Condition of a
Discrete-Time LTI System
? Example - The factor-of-2 interpolator
defined by
is noncausal as it has a noncausal impulse
response given by
? ?]1[]1[][][ 21 ????? nxnxnxny uuu
}5.015.0{]}[{ ?nh
?
Copyright ? 2001,S,K,Mitra 13
Causality Condition of a
Discrete-Time LTI System
? Note,A noncausal LTI discrete-time system
with a finite-length impulse response can
often be realized as a causal system by
inserting an appropriate amount of delay
? Example - A causal version of the factor-of-
2 interpolator is obtained by delaying the
input by one sample period,
? ?][]2[]1[][ 21 nxnxnxny uuu ?????
Copyright ? 2001,S,K,Mitra 14
Finite-Dimensional Discrete-
Time LTI Systems
? An important subclass of discrete-time LTI
systems is characterized by a linear constant-
coefficient difference equation of the form
? x[n] and y[n] are,respectively,the input and
the output of the system
? and are constants characterizing
the system
}{ kd }{ kp
??
??
???
M
k
k
N
k
k knxpknyd
00
][][
Copyright ? 2001,S,K,Mitra 15
Finite-Dimensional Discrete-
Time LTI Systems
? The order of the system is given by
max(N,M),which is the order of the difference
equation
? It is possible to implement an LTI system
characterized by a constant-coefficient
difference equation since the computation
involves two finite sums of products
Copyright ? 2001,S,K,Mitra 16
Finite-Dimensional Discrete-
Time LTI Systems
? If we assume the system to be causal,then
the output y[n] can be recursively computed
using
provided
? y[n] can be computed for all,
knowing x[n] and the initial conditions
00 ?d
onn ?
][,...],2[],1[ Nnynyny ooo ???
][][][
1 01 0
knx
d
pkny
d
dny M
k
k
N
k
k ????? ??
??
Copyright ? 2001,S,K,Mitra 17
? The output response y[n] of the LTI system
described by
can be computed as
where
Total Solution Calculation
??
??
???
M
k
k
N
k
k knxpknyd
00
][][
[ ] [ ] [ ]cpy n y n y n??
[]cyn
[]pyn
is the complementary solution to the
homogeneous difference equation
obtained by setting
is the particular solution resulting from
the specified input signal x[n]
[ ] 0xn ??
?
Copyright ? 2001,S,K,Mitra 18
? We assume that it is of the form
? By substitution in the homogeneous
equation,it is
Computing the
Complementary Solution
[] ncyn ??
00
1
0 1 1
[]
( ) 0
NN
nk
kk
kk
n N N N
NN
d y n k d
d d d d
?
? ? ? ?
?
??
??
?
? ? ?
? ? ? ? ? ?
??
L
Copyright ? 2001,S,K,Mitra 19
? The polynomial is called the
characteristic polynomial of the given LTI
system
? Let denote its N roots
Characteristic Polynomial
0
N
nk
k
k
d ? ?
?
?
12,,,N? ? ?K
Copyright ? 2001,S,K,Mitra 20
? If the N roots are distinct,the complementary
solution is expressed by
where are constants determined
by the specified initial conditions of the DT
system
Complementary Solution
1 1 2 2[] n n nc N Nyn ? ? ? ? ? ?? ? ? ?L
12,,,N? ? ?K
Copyright ? 2001,S,K,Mitra 21
? If there are multiple roots,the complementary
solution takes on a different form,
? For instance,if has multiplicity L,and the
remaining roots are
distinct,the complementary solution is
Complementary Solution
1?
NL? 2,,NL?? ?K
1
21
1 1 123
12
1[]
n n n L n
cL
nn
L N N L
yn n n n? ? ? ???
?
??
? ? ?
?
??
? ? ? ? ? ?
? ? ?
L
L
Copyright ? 2001,S,K,Mitra 22
? For the computation of,the procedure
consists in assuming that it is of the same
form as the specific input signal x[n],
? E.g.,if x[n] is a sinusoidal signal,so is
? If x[n] is a constant signal,so is,etc,
Particular Solution
[]pyn
[]pyn
[]pyn
Copyright ? 2001,S,K,Mitra 23
? An alternate approach to the solution of
consists in computing
where
Zero-Input Response and
Zero-State Response
??
??
???
M
k
k
N
k
k knxpknyd
00
][][
[ ] [ ] [ ]z i z sy n y n y n??
[]ziyn
[]zsyn
is the zero-input solution obtained by
solving the difference equation by
setting [ ] 0xn ?
is the zero-state solution obtained by solving
the difference equation by applying x[n] and
setting all initial conditions to zero
?
?
Copyright ? 2001,S,K,Mitra 24
? The impulse response h[n] of a causal
discrete-time LTI system is simply the zero-
state response with
? Assuming that all the roots of the
characteristic polynomial are distinct,the
impulse response can be expressed as
Impulse Response of a Causal
Discrete-Time LTI System
[ ] [ ]x n n??
1
[ ] [ ]
N
n
ii
i
h n n? ? ?
?
? ?
i?
Copyright ? 2001,S,K,Mitra 25
Locations of the Roots of the
Characteristic Equation
for BIBO Stability
? It follows that
? Therefore,if for all values of i,it is
implying the BIBO stability of the system
0 0 1 1 0
| [ ] | [ ] | | | |
NN
nn
i i i i
n n i i n
h n n? ? ? ? ?
? ? ?
? ? ? ? ?
??? ? ? ? ?
| | 1i? ?
0
| [ ] |
n
hn
?
?
???
Copyright ? 2001,S,K,Mitra 26
Classification of Discrete-Time
LTI Systems
Based on the Impulse Response Length,
? If the impulse response h[n] is of finite
length,i.e.,
then it is known as a finite impulse
response (FIR) discrete-time system
? The convolution sum description here is
2121,a n df o r0][ NNNnNnnh ????
?
?
??
2
1
][][][
N
Nk
knxkhny
Copyright ? 2001,S,K,Mitra 27
Classification of Discrete-Time
LTI Systems
? The output y[n] of an FIR LTI discrete-time
system can be computed directly from the
convolution sum as it is a finite sum of
products
? Examples of FIR LTI discrete-time systems
are the moving-average system and the
linear interpolators
Copyright ? 2001,S,K,Mitra 28
Classification of Discrete-Time
LTI Systems
? If the impulse response is of infinite length,
then it is known as an infinite impulse
response (IIR) discrete-time system
? The class of IIR systems we are concerned
with in this course are characterized by
linear constant coefficient difference
equations
Copyright ? 2001,S,K,Mitra 29
Classification of Discrete-Time
LTI Systems
? Example - The discrete-time accumulator
defined by
is an IIR system
][]1[][ nxnyny ???
Copyright ? 2001,S,K,Mitra 30
Classification of Discrete-Time
LTI Systems
? Example - The familiar numerical
integration formulas that are used to
numerically solve integrals of the form
can be shown to be characterized by linear
constant coefficient difference equations,
and hence,are examples of IIR systems
? ???
t
dxty
0
)()(
Copyright ? 2001,S,K,Mitra 31
Classification of Discrete-Time
LTI Systems
? If we divide the interval of integration into n
equal parts of length T,then the previous
integral can be rewritten as
where we have set t = nT and used the
notation
?
?
?????
nT
Tn
dxTnynTy
)1(
)())1(()(
? ???
nT
dxnTy
0
)()(
Copyright ? 2001,S,K,Mitra 32
Classification of LTI Discrete-
Time Systems
? Using the trapezoidal method we can write
? Hence,a numerical representation of the
definite integral is given by
)}())1(({)(
2
)1(
nTxTnxdx T
nT
Tn
??????
?
)}())1(({))1(()( 2 nTxTnxTnynTy T ?????
Copyright ? 2001,S,K,Mitra 33
Numerical Integration with the
Trapezoidal Method
t
()xt
nT( 1)nT?
()x nT
( ( 1 ) )x n T?
Copyright ? 2001,S,K,Mitra 34
Classification of Discrete-Time
LTI Systems
? Let y[n] = y(nT) and x[n] = x(nT)
? Then
reduces to
which is the difference equation representation
of a first-order IIR discrete-time system
)}())1(({))1(()( 2 nTxTnxTnynTy T ?????
]}1[][{]1[][ 2 ????? nxnxnyny T
Copyright ? 2001,S,K,Mitra 35
Classification of LTI Discrete-
Time Systems
Based on the Output Calculation Process,
? Nonrecursive System - Here the output can
be calculated sequentially,knowing only
the present and past input samples
? Recursive System - Here the output
computation involves past output samples in
addition to the present and past input
samples
Copyright ? 2001,S,K,Mitra 36
Classification of LTI Discrete-
Time Systems
Based on the Coefficients,
? Real Discrete-Time System - The impulse
response samples are real valued
? Complex Discrete-Time System - The
impulse response samples are complex
valued
Copyright ? 2001,S,K,Mitra 37
Correlation of Signals
? There are applications where it is necessary
to compare one reference signal with one or
more signals to determine the similarity
between the pair and to determine additional
information based on the similarity
Copyright ? 2001,S,K,Mitra 38
Correlation of Signals
? For example,in digital communications,a
set of data symbols are represented by a set
of unique discrete-time sequences
? If one of these sequences has been
transmitted,the receiver has to determine
which particular sequence has been received
by comparing the received signal with every
member of possible sequences from the set
Copyright ? 2001,S,K,Mitra 39
Correlation of Signals
? Similarly,in radar and sonar applications,
the received signal reflected from the target
is a delayed version of the transmitted
signal and by measuring the delay,one can
determine the location of the target
? The detection problem gets more
complicated in practice,as often the
received signal is corrupted by additive
random noise
Copyright ? 2001,S,K,Mitra 40
Correlation of Signals
Definitions
? A measure of similarity between a pair of
energy signals,x[n] and y[n],is given by the
cross-correlation sequence defined
by
? The parameter called lag,indicates the
time-shift between the pair of signals
?
][?xyr
...,,,],[][][ 210 ????? ?
?
???
???
n
xy nynxr
Copyright ? 2001,S,K,Mitra 41
Correlation of Signals
? y[n] is said to be shifted by samples to the
right with respect to the reference sequence
x[n] for positive values of,and shifted by
samples to the left for negative values of
? The ordering of the subscripts xy in the
definition of specifies that x[n] is the
reference sequence which remains fixed in
time while y[n] is being shifted with respect
to x[n]
][?xyr
?
?? ?
Copyright ? 2001,S,K,Mitra 42
Correlation of Signals
? If y[n] is made the reference signal and x[n]
is shifted with respect to y[n],then the
corresponding cross-correlation sequence is
given by
? Thus,is obtained by time-reversing
? ? ??? ?? nyx nxnyr ][][][ ??
][][][ ?? ???? ? ? ??? xym rmxmy
][?yxr
][?xyr
Copyright ? 2001,S,K,Mitra 43
Correlation of Signals
? The autocorrelation sequence of x[n] is
given by
obtained by setting y[n] = x[n] in the
definition of the cross-correlation sequence
? Note:,the energy
of the signal x[n]
? ? ??? ?? nxx nxnxr ][][][ ??
][?xyr
2[ 0] [ ] Ex x x
nr x n
?
? ? ????
Copyright ? 2001,S,K,Mitra 44
Correlation of Signals
? From the relation it follows
that implying that is
an even function for real x[n]
? An examination of
reveals that the expression for the cross-
correlation looks quite similar to that of the
linear convolution
][][ ?? ?? xyyx rr
][][ ?? ?? xxxx rr ][?xxr
? ? ??? ?? nxy nynxr ][][][ ??
Copyright ? 2001,S,K,Mitra 45
Correlation of Signals
? This similarity is much clearer if we rewrite
the expression for the cross-correlation as
? Thus,the cross-correlation of y[n] with the
reference signal x[n] can be computed by
processing x[n] with a discrete-time LTI
system of impulse response ][ ny ?
][][)]([][][ ???? ????? ? ? ??? yxnynxr nxy *
][ ny ?][nx ][nrxy
Copyright ? 2001,S,K,Mitra 46
Correlation of Signals
? Likewise,the autocorrelation of x[n] can be
computed by processing x[n] with a
discrete-time LTI system of impulse
response
][ nx ?][nx ][nrxx
][ nx ?
Copyright ? 2001,S,K,Mitra 47
Properties of Autocorrelation and
Cross-correlation Sequences
? Consider two finite-energy sequences x[n]
and y[n]
? The energy of the combined sequence
is also finite and
nonnegative,i.e.,
][][ ??? nynxa
?? ? ???? ??? ??? nn nxanynxa ][])[][( 222?
02 2 ????? ?? ? ???? ??? nn nynynxa ][][][ ??
Copyright ? 2001,S,K,Mitra 48
Properties of Autocorrelation and
Cross-correlation Sequences
? Thus
where and
? We can rewrite the equation on the previous
slide as
for any finite value of a
00202 ??? ][][][ yyxyxx rrara ?
00 ?? xxxr E][ 00 ?? yyyr E][
? ? 01001 ????????
?
?
??
? a
rr
rr
a
yyxy
xyxx
][][
][][
?
?
Copyright ? 2001,S,K,Mitra 49
Properties of Autocorrelation and
Cross-correlation Sequences
? Or,in other words,the matrix
is positive semidefinite
? This implies that
or,equivalently,
??
?
??
?
][][
][][
0
0
yyxy
xyxx
rr
rr
?
?
000 2 ?? ][][][ ?xyyyxx rrr
yxyyxxxy rrr EE?? ][][|][| 00?
Copyright ? 2001,S,K,Mitra 50
Properties of Autocorrelation and
Cross-correlation Sequences
? The last inequality on the previous slide
provides an upper bound for the cross-
correlation samples
? If we set y[n] = x[n],then the inequality
reduces to
? Thus,at zero lag ( ),the sample value of
the autocorrelation sequence has its
maximum value
| [ ] | [0 ] Ex x x x xrr ??l
0??
Copyright ? 2001,S,K,Mitra 51
Properties of Autocorrelation and
Cross-correlation Sequences
? Now consider the case
where N is an integer and b > 0 is an
arbitrary number
? In this case xy b EE 2?
][][ Nnxbny ???
Copyright ? 2001,S,K,Mitra 52
Properties of Autocorrelation and
Cross-correlation Sequences
? Therefore
? Using the above result in
we get
xxyx bb EEEE ?? 22
yxyyxxxy rrr EE?? ][][|][| 00?
][][][ 00 xxxyxx rbrrb ??? ?
Copyright ? 2001,S,K,Mitra 53
Correlation Computation
Using MATLAB
? The cross-correlation and autocorrelation
sequences can easily be computed using
MATLAB
? Example - Consider the two finite-length
sequences
? ?244121231 ???][ nx
? ?321412 ???][ ny
Copyright ? 2001,S,K,Mitra 54
Correlation Computation
Using MATLAB
? The cross-correlation sequence
computed using Program 2_7 of textbook
(with a correction!) is plotted below
][nrxy
Copyright ? 2001,S,K,Mitra 55
Correlation Computation
Using MATLAB
? The autocorrelation sequence
computed using Program 2_7 is shown below
? Note,At zero lag,is the maximum
][?xxr
][0xxr
-5 0 5
- 20
0
20
40
60
L a g i nde x
A
m
pl
i
t
ude
Copyright ? 2001,S,K,Mitra 56
Correlation Computation Using
MATLAB
? The plot below shows the cross-correlation
of x[n] and for N = 4
? Note,The peak of the cross-correlation is
precisely the value of the delay N
][][ Nnxny ??
Copyright ? 2001,S,K,Mitra 57
Correlation Computation
Using MATLAB
? The plot below shows the autocorrelation of
x[n] corrupted with an additive random
noise generated using the function randn
? Note,The autocorrelation still exhibits a
peak at zero lag
-5 0 5
0
20
40
60
80
L a g i nde x
A
m
pl
i
t
ude
Copyright ? 2001,S,K,Mitra 58
Correlation Computation Using
MATLAB
? The autocorrelation and the cross-correlation can
also be computed using the function xcorr
? In Matlab,the cross-correlation is in fact defined
as
[ ] [ ] [ ],0,1,2,...
[ ] [ ],
xy
n
n
r x n y n
x n y n
?
? ? ?
?
? ? ?
? ? ? ? ?
??
?
?
l l l
l
Copyright ? 2001,S,K,Mitra 59
Normalized Forms of
Correlation
? Normalized forms of autocorrelation and
cross-correlation are given by
? They are often used for convenience in
comparing and displaying
? Note,and
independent of the range of values of x[n]
and y[n]
][][
][
][,
][
][][
000 yyxx
xy
xy
xx
xx
xx rr
r
r
r ???? ?? ??
1?|][| ?xx? 1?|][| ?xy?
Copyright ? 2001,S,K,Mitra 60
Correlation Computation for
Power Signals
? The cross-correlation sequence for a pair
of power signals,x[n] and y[n],is defined
as
? The autocorrelation sequence of a power
signal x[n] is given by
?
????
?
?
?
K
KnK
xy nynxKr ][][l i m][ ?? 12
1
?
????
?
?
?
K
KnK
xx nxnxKr ][][lim][ ?? 12
1
Copyright ? 2001,S,K,Mitra 61
Correlation Computation for
Periodic Signals
? The cross-correlation sequence for a pair of
periodic signals of period N,and,
is defined as
? The autocorrelation sequence of a periodic
signal of period N is given by
][nx~ ][ny~
][nx~
? ?? ?? 101 NnNxy nynxr ][][][ ??~ ~ ~ ~
? ?? ?? 101 NnNxx nxnxr ][][][ ??~ ~ ~ ~
Stability Condition of a
Discrete-Time LTI System
? BIBO Stability Condition - A discrete-time
LTI system is BIBO stable if the output
sequence {y[n]} remains bounded for any
bounded input sequence{x[n]}
? A discrete-time LTI system is BIBO stable
if and only if its impulse response sequence
{h[n]} is absolutely summable,i.e,
??? ?
?
???n
nh ][S
Copyright ? 2001,S,K,Mitra 2
Stability Condition of a
Discrete-Time LTI System
? Proof,Assume h[n] is a real sequence
? Since the input sequence x[n] is bounded we
have
? Therefore
??? xBnx ][
][][][][][ knxkhknxkhny
kk
???? ??
?
???
?
???
x
k
x BkhB ?? ?
?
???
][S
Copyright ? 2001,S,K,Mitra 3
Stability Condition of a
Discrete-Time LTI System
? Thus,S < implies
indicating that y[n] is also bounded
? To prove the converse,assume that y[n] is
bounded,i.e.,
? Consider the input given by
? ??? yBny ][
yBny ?][
??
?
??
????
0
0
][if,
][if] ),[s g n (][
nhK
nhnhnx
Copyright ? 2001,S,K,Mitra 4
Stability Condition of a
Discrete-Time LTI System
where sgn(c) = +1 if c > 0 and sgn(c) =
if c < 0 and
? Note,Since,{x[n]} is obviously
bounded
? For this input,y[n] at n = 0 is
? Therefore,implies S <
1?
1?K
yBny ?][ ?
1?][nx
?
?
???
??
k
khkhy ][])[sg n(][ 0 S ??? yB
Copyright ? 2001,S,K,Mitra 5
Stability Condition of a
Discrete-Time LTI System
? Example - Consider a causal discrete-time
LTI system with an impulse response
? For this system
? Therefore if for which the
system is BIBO stable
? If,the system is not BIBO stable
S ?? | | 1? ?
| | 1? ?
][)(][ nnh n ???
?
???
?
??? ??
?
?
?
??? 1
1
0n
n
n
n n ][
S 1??if
Copyright ? 2001,S,K,Mitra 6
Causality Condition of a
Discrete-Time LTI System
? Let and be two input sequences
with
? The corresponding output samples at
of an LTI system with an impulse response
{h[n]} are then given by
][nx1 ][nx2
][][ nxnx 21 ? onn ?for
onn ?
Copyright ? 2001,S,K,Mitra 7
Causality Condition of a
Discrete-Time LTI System
??
?
?
?
???
????
0
222
k
o
k
oo knxkhknxkhny ][][][][][
?
?
???
??
1
2
k
o knxkh ][][
??
?
?
?
???
????
0
111
k
o
k
oo knxkhknxkhny ][][][][][
?
?
???
??
1
1
k
o knxkh ][][
Copyright ? 2001,S,K,Mitra 8
Causality Condition of a
Discrete-Time LTI System
? If the LTI system is also causal,then
? As
? This implies
][][ nxnx 21 ? onn ?for
][][ oo nyny 21 ?
??
?
?
?
?
???
0
2
0
1
k
o
k
o knxkhknxkh ][][][][
??
?
???
?
???
???
1
2
1
1
k
o
k
o knxkhknxkh ][][][][
Copyright ? 2001,S,K,Mitra 9
Causality Condition of a
Discrete-Time LTI System
? As for the only way
the condition
will hold if both sums are equal to zero,
which is satisfied if
][][ nxnx 21 ? onn ?
??
?
???
?
???
???
1
2
1
1
k
o
k
o knxkhknxkh ][][][][
0?][kh for k < 0
Copyright ? 2001,S,K,Mitra 10
Causality Condition of a
Discrete-Time LTI System
? A discrete-time LTI system is causal if and
only if its impulse response {h[n]} is a causal
sequence
? Example - The discrete-time system defined
by
is a causal system as it has a causal impulse
response
]3[]2[]1[][][ 4321 ??????????? nxnxnxnxny
}{]}[{ 4321 ?????nh
?
Copyright ? 2001,S,K,Mitra 11
Causality Condition of a
Discrete-Time LTI System
? Example - The discrete-time accumulator
defined by
is a causal system as it has a causal impulse
response given by
[ ] [ ]
n
y n x
? ??
? ?
l
l
][][][ nnh
n
???? ?
????
?
Copyright ? 2001,S,K,Mitra 12
Causality Condition of a
Discrete-Time LTI System
? Example - The factor-of-2 interpolator
defined by
is noncausal as it has a noncausal impulse
response given by
? ?]1[]1[][][ 21 ????? nxnxnxny uuu
}5.015.0{]}[{ ?nh
?
Copyright ? 2001,S,K,Mitra 13
Causality Condition of a
Discrete-Time LTI System
? Note,A noncausal LTI discrete-time system
with a finite-length impulse response can
often be realized as a causal system by
inserting an appropriate amount of delay
? Example - A causal version of the factor-of-
2 interpolator is obtained by delaying the
input by one sample period,
? ?][]2[]1[][ 21 nxnxnxny uuu ?????
Copyright ? 2001,S,K,Mitra 14
Finite-Dimensional Discrete-
Time LTI Systems
? An important subclass of discrete-time LTI
systems is characterized by a linear constant-
coefficient difference equation of the form
? x[n] and y[n] are,respectively,the input and
the output of the system
? and are constants characterizing
the system
}{ kd }{ kp
??
??
???
M
k
k
N
k
k knxpknyd
00
][][
Copyright ? 2001,S,K,Mitra 15
Finite-Dimensional Discrete-
Time LTI Systems
? The order of the system is given by
max(N,M),which is the order of the difference
equation
? It is possible to implement an LTI system
characterized by a constant-coefficient
difference equation since the computation
involves two finite sums of products
Copyright ? 2001,S,K,Mitra 16
Finite-Dimensional Discrete-
Time LTI Systems
? If we assume the system to be causal,then
the output y[n] can be recursively computed
using
provided
? y[n] can be computed for all,
knowing x[n] and the initial conditions
00 ?d
onn ?
][,...],2[],1[ Nnynyny ooo ???
][][][
1 01 0
knx
d
pkny
d
dny M
k
k
N
k
k ????? ??
??
Copyright ? 2001,S,K,Mitra 17
? The output response y[n] of the LTI system
described by
can be computed as
where
Total Solution Calculation
??
??
???
M
k
k
N
k
k knxpknyd
00
][][
[ ] [ ] [ ]cpy n y n y n??
[]cyn
[]pyn
is the complementary solution to the
homogeneous difference equation
obtained by setting
is the particular solution resulting from
the specified input signal x[n]
[ ] 0xn ??
?
Copyright ? 2001,S,K,Mitra 18
? We assume that it is of the form
? By substitution in the homogeneous
equation,it is
Computing the
Complementary Solution
[] ncyn ??
00
1
0 1 1
[]
( ) 0
NN
nk
kk
kk
n N N N
NN
d y n k d
d d d d
?
? ? ? ?
?
??
??
?
? ? ?
? ? ? ? ? ?
??
L
Copyright ? 2001,S,K,Mitra 19
? The polynomial is called the
characteristic polynomial of the given LTI
system
? Let denote its N roots
Characteristic Polynomial
0
N
nk
k
k
d ? ?
?
?
12,,,N? ? ?K
Copyright ? 2001,S,K,Mitra 20
? If the N roots are distinct,the complementary
solution is expressed by
where are constants determined
by the specified initial conditions of the DT
system
Complementary Solution
1 1 2 2[] n n nc N Nyn ? ? ? ? ? ?? ? ? ?L
12,,,N? ? ?K
Copyright ? 2001,S,K,Mitra 21
? If there are multiple roots,the complementary
solution takes on a different form,
? For instance,if has multiplicity L,and the
remaining roots are
distinct,the complementary solution is
Complementary Solution
1?
NL? 2,,NL?? ?K
1
21
1 1 123
12
1[]
n n n L n
cL
nn
L N N L
yn n n n? ? ? ???
?
??
? ? ?
?
??
? ? ? ? ? ?
? ? ?
L
L
Copyright ? 2001,S,K,Mitra 22
? For the computation of,the procedure
consists in assuming that it is of the same
form as the specific input signal x[n],
? E.g.,if x[n] is a sinusoidal signal,so is
? If x[n] is a constant signal,so is,etc,
Particular Solution
[]pyn
[]pyn
[]pyn
Copyright ? 2001,S,K,Mitra 23
? An alternate approach to the solution of
consists in computing
where
Zero-Input Response and
Zero-State Response
??
??
???
M
k
k
N
k
k knxpknyd
00
][][
[ ] [ ] [ ]z i z sy n y n y n??
[]ziyn
[]zsyn
is the zero-input solution obtained by
solving the difference equation by
setting [ ] 0xn ?
is the zero-state solution obtained by solving
the difference equation by applying x[n] and
setting all initial conditions to zero
?
?
Copyright ? 2001,S,K,Mitra 24
? The impulse response h[n] of a causal
discrete-time LTI system is simply the zero-
state response with
? Assuming that all the roots of the
characteristic polynomial are distinct,the
impulse response can be expressed as
Impulse Response of a Causal
Discrete-Time LTI System
[ ] [ ]x n n??
1
[ ] [ ]
N
n
ii
i
h n n? ? ?
?
? ?
i?
Copyright ? 2001,S,K,Mitra 25
Locations of the Roots of the
Characteristic Equation
for BIBO Stability
? It follows that
? Therefore,if for all values of i,it is
implying the BIBO stability of the system
0 0 1 1 0
| [ ] | [ ] | | | |
NN
nn
i i i i
n n i i n
h n n? ? ? ? ?
? ? ?
? ? ? ? ?
??? ? ? ? ?
| | 1i? ?
0
| [ ] |
n
hn
?
?
???
Copyright ? 2001,S,K,Mitra 26
Classification of Discrete-Time
LTI Systems
Based on the Impulse Response Length,
? If the impulse response h[n] is of finite
length,i.e.,
then it is known as a finite impulse
response (FIR) discrete-time system
? The convolution sum description here is
2121,a n df o r0][ NNNnNnnh ????
?
?
??
2
1
][][][
N
Nk
knxkhny
Copyright ? 2001,S,K,Mitra 27
Classification of Discrete-Time
LTI Systems
? The output y[n] of an FIR LTI discrete-time
system can be computed directly from the
convolution sum as it is a finite sum of
products
? Examples of FIR LTI discrete-time systems
are the moving-average system and the
linear interpolators
Copyright ? 2001,S,K,Mitra 28
Classification of Discrete-Time
LTI Systems
? If the impulse response is of infinite length,
then it is known as an infinite impulse
response (IIR) discrete-time system
? The class of IIR systems we are concerned
with in this course are characterized by
linear constant coefficient difference
equations
Copyright ? 2001,S,K,Mitra 29
Classification of Discrete-Time
LTI Systems
? Example - The discrete-time accumulator
defined by
is an IIR system
][]1[][ nxnyny ???
Copyright ? 2001,S,K,Mitra 30
Classification of Discrete-Time
LTI Systems
? Example - The familiar numerical
integration formulas that are used to
numerically solve integrals of the form
can be shown to be characterized by linear
constant coefficient difference equations,
and hence,are examples of IIR systems
? ???
t
dxty
0
)()(
Copyright ? 2001,S,K,Mitra 31
Classification of Discrete-Time
LTI Systems
? If we divide the interval of integration into n
equal parts of length T,then the previous
integral can be rewritten as
where we have set t = nT and used the
notation
?
?
?????
nT
Tn
dxTnynTy
)1(
)())1(()(
? ???
nT
dxnTy
0
)()(
Copyright ? 2001,S,K,Mitra 32
Classification of LTI Discrete-
Time Systems
? Using the trapezoidal method we can write
? Hence,a numerical representation of the
definite integral is given by
)}())1(({)(
2
)1(
nTxTnxdx T
nT
Tn
??????
?
)}())1(({))1(()( 2 nTxTnxTnynTy T ?????
Copyright ? 2001,S,K,Mitra 33
Numerical Integration with the
Trapezoidal Method
t
()xt
nT( 1)nT?
()x nT
( ( 1 ) )x n T?
Copyright ? 2001,S,K,Mitra 34
Classification of Discrete-Time
LTI Systems
? Let y[n] = y(nT) and x[n] = x(nT)
? Then
reduces to
which is the difference equation representation
of a first-order IIR discrete-time system
)}())1(({))1(()( 2 nTxTnxTnynTy T ?????
]}1[][{]1[][ 2 ????? nxnxnyny T
Copyright ? 2001,S,K,Mitra 35
Classification of LTI Discrete-
Time Systems
Based on the Output Calculation Process,
? Nonrecursive System - Here the output can
be calculated sequentially,knowing only
the present and past input samples
? Recursive System - Here the output
computation involves past output samples in
addition to the present and past input
samples
Copyright ? 2001,S,K,Mitra 36
Classification of LTI Discrete-
Time Systems
Based on the Coefficients,
? Real Discrete-Time System - The impulse
response samples are real valued
? Complex Discrete-Time System - The
impulse response samples are complex
valued
Copyright ? 2001,S,K,Mitra 37
Correlation of Signals
? There are applications where it is necessary
to compare one reference signal with one or
more signals to determine the similarity
between the pair and to determine additional
information based on the similarity
Copyright ? 2001,S,K,Mitra 38
Correlation of Signals
? For example,in digital communications,a
set of data symbols are represented by a set
of unique discrete-time sequences
? If one of these sequences has been
transmitted,the receiver has to determine
which particular sequence has been received
by comparing the received signal with every
member of possible sequences from the set
Copyright ? 2001,S,K,Mitra 39
Correlation of Signals
? Similarly,in radar and sonar applications,
the received signal reflected from the target
is a delayed version of the transmitted
signal and by measuring the delay,one can
determine the location of the target
? The detection problem gets more
complicated in practice,as often the
received signal is corrupted by additive
random noise
Copyright ? 2001,S,K,Mitra 40
Correlation of Signals
Definitions
? A measure of similarity between a pair of
energy signals,x[n] and y[n],is given by the
cross-correlation sequence defined
by
? The parameter called lag,indicates the
time-shift between the pair of signals
?
][?xyr
...,,,],[][][ 210 ????? ?
?
???
???
n
xy nynxr
Copyright ? 2001,S,K,Mitra 41
Correlation of Signals
? y[n] is said to be shifted by samples to the
right with respect to the reference sequence
x[n] for positive values of,and shifted by
samples to the left for negative values of
? The ordering of the subscripts xy in the
definition of specifies that x[n] is the
reference sequence which remains fixed in
time while y[n] is being shifted with respect
to x[n]
][?xyr
?
?? ?
Copyright ? 2001,S,K,Mitra 42
Correlation of Signals
? If y[n] is made the reference signal and x[n]
is shifted with respect to y[n],then the
corresponding cross-correlation sequence is
given by
? Thus,is obtained by time-reversing
? ? ??? ?? nyx nxnyr ][][][ ??
][][][ ?? ???? ? ? ??? xym rmxmy
][?yxr
][?xyr
Copyright ? 2001,S,K,Mitra 43
Correlation of Signals
? The autocorrelation sequence of x[n] is
given by
obtained by setting y[n] = x[n] in the
definition of the cross-correlation sequence
? Note:,the energy
of the signal x[n]
? ? ??? ?? nxx nxnxr ][][][ ??
][?xyr
2[ 0] [ ] Ex x x
nr x n
?
? ? ????
Copyright ? 2001,S,K,Mitra 44
Correlation of Signals
? From the relation it follows
that implying that is
an even function for real x[n]
? An examination of
reveals that the expression for the cross-
correlation looks quite similar to that of the
linear convolution
][][ ?? ?? xyyx rr
][][ ?? ?? xxxx rr ][?xxr
? ? ??? ?? nxy nynxr ][][][ ??
Copyright ? 2001,S,K,Mitra 45
Correlation of Signals
? This similarity is much clearer if we rewrite
the expression for the cross-correlation as
? Thus,the cross-correlation of y[n] with the
reference signal x[n] can be computed by
processing x[n] with a discrete-time LTI
system of impulse response ][ ny ?
][][)]([][][ ???? ????? ? ? ??? yxnynxr nxy *
][ ny ?][nx ][nrxy
Copyright ? 2001,S,K,Mitra 46
Correlation of Signals
? Likewise,the autocorrelation of x[n] can be
computed by processing x[n] with a
discrete-time LTI system of impulse
response
][ nx ?][nx ][nrxx
][ nx ?
Copyright ? 2001,S,K,Mitra 47
Properties of Autocorrelation and
Cross-correlation Sequences
? Consider two finite-energy sequences x[n]
and y[n]
? The energy of the combined sequence
is also finite and
nonnegative,i.e.,
][][ ??? nynxa
?? ? ???? ??? ??? nn nxanynxa ][])[][( 222?
02 2 ????? ?? ? ???? ??? nn nynynxa ][][][ ??
Copyright ? 2001,S,K,Mitra 48
Properties of Autocorrelation and
Cross-correlation Sequences
? Thus
where and
? We can rewrite the equation on the previous
slide as
for any finite value of a
00202 ??? ][][][ yyxyxx rrara ?
00 ?? xxxr E][ 00 ?? yyyr E][
? ? 01001 ????????
?
?
??
? a
rr
rr
a
yyxy
xyxx
][][
][][
?
?
Copyright ? 2001,S,K,Mitra 49
Properties of Autocorrelation and
Cross-correlation Sequences
? Or,in other words,the matrix
is positive semidefinite
? This implies that
or,equivalently,
??
?
??
?
][][
][][
0
0
yyxy
xyxx
rr
rr
?
?
000 2 ?? ][][][ ?xyyyxx rrr
yxyyxxxy rrr EE?? ][][|][| 00?
Copyright ? 2001,S,K,Mitra 50
Properties of Autocorrelation and
Cross-correlation Sequences
? The last inequality on the previous slide
provides an upper bound for the cross-
correlation samples
? If we set y[n] = x[n],then the inequality
reduces to
? Thus,at zero lag ( ),the sample value of
the autocorrelation sequence has its
maximum value
| [ ] | [0 ] Ex x x x xrr ??l
0??
Copyright ? 2001,S,K,Mitra 51
Properties of Autocorrelation and
Cross-correlation Sequences
? Now consider the case
where N is an integer and b > 0 is an
arbitrary number
? In this case xy b EE 2?
][][ Nnxbny ???
Copyright ? 2001,S,K,Mitra 52
Properties of Autocorrelation and
Cross-correlation Sequences
? Therefore
? Using the above result in
we get
xxyx bb EEEE ?? 22
yxyyxxxy rrr EE?? ][][|][| 00?
][][][ 00 xxxyxx rbrrb ??? ?
Copyright ? 2001,S,K,Mitra 53
Correlation Computation
Using MATLAB
? The cross-correlation and autocorrelation
sequences can easily be computed using
MATLAB
? Example - Consider the two finite-length
sequences
? ?244121231 ???][ nx
? ?321412 ???][ ny
Copyright ? 2001,S,K,Mitra 54
Correlation Computation
Using MATLAB
? The cross-correlation sequence
computed using Program 2_7 of textbook
(with a correction!) is plotted below
][nrxy
Copyright ? 2001,S,K,Mitra 55
Correlation Computation
Using MATLAB
? The autocorrelation sequence
computed using Program 2_7 is shown below
? Note,At zero lag,is the maximum
][?xxr
][0xxr
-5 0 5
- 20
0
20
40
60
L a g i nde x
A
m
pl
i
t
ude
Copyright ? 2001,S,K,Mitra 56
Correlation Computation Using
MATLAB
? The plot below shows the cross-correlation
of x[n] and for N = 4
? Note,The peak of the cross-correlation is
precisely the value of the delay N
][][ Nnxny ??
Copyright ? 2001,S,K,Mitra 57
Correlation Computation
Using MATLAB
? The plot below shows the autocorrelation of
x[n] corrupted with an additive random
noise generated using the function randn
? Note,The autocorrelation still exhibits a
peak at zero lag
-5 0 5
0
20
40
60
80
L a g i nde x
A
m
pl
i
t
ude
Copyright ? 2001,S,K,Mitra 58
Correlation Computation Using
MATLAB
? The autocorrelation and the cross-correlation can
also be computed using the function xcorr
? In Matlab,the cross-correlation is in fact defined
as
[ ] [ ] [ ],0,1,2,...
[ ] [ ],
xy
n
n
r x n y n
x n y n
?
? ? ?
?
? ? ?
? ? ? ? ?
??
?
?
l l l
l
Copyright ? 2001,S,K,Mitra 59
Normalized Forms of
Correlation
? Normalized forms of autocorrelation and
cross-correlation are given by
? They are often used for convenience in
comparing and displaying
? Note,and
independent of the range of values of x[n]
and y[n]
][][
][
][,
][
][][
000 yyxx
xy
xy
xx
xx
xx rr
r
r
r ???? ?? ??
1?|][| ?xx? 1?|][| ?xy?
Copyright ? 2001,S,K,Mitra 60
Correlation Computation for
Power Signals
? The cross-correlation sequence for a pair
of power signals,x[n] and y[n],is defined
as
? The autocorrelation sequence of a power
signal x[n] is given by
?
????
?
?
?
K
KnK
xy nynxKr ][][l i m][ ?? 12
1
?
????
?
?
?
K
KnK
xx nxnxKr ][][lim][ ?? 12
1
Copyright ? 2001,S,K,Mitra 61
Correlation Computation for
Periodic Signals
? The cross-correlation sequence for a pair of
periodic signals of period N,and,
is defined as
? The autocorrelation sequence of a periodic
signal of period N is given by
][nx~ ][ny~
][nx~
? ?? ?? 101 NnNxy nynxr ][][][ ??~ ~ ~ ~
? ?? ?? 101 NnNxx nxnxr ][][][ ??~ ~ ~ ~
