Chapter 2

Discrete-Time
Di t Ti Signals
Si l &
Systems
清大電機系林嘉文
[email protected]
03 5731152
03-5731152
Original PowerPoint slides prepared by S. K. Mitra 2-1-1
© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (1/10)
• Signals represented as sequences of numbers, called
samples
• Sample value of a typical signal or sequence denoted as
x[n] with n being an integer in the range − ∞ ≤ n ≤ ∞
• x[n] defined only for integer values of n and undefined for
non-integer values of n
• Discrete-time signal represented by {x[n]}
• Discrete-time signal
g mayy also be written as a sequence
q of
numbers inside braces:

Original PowerPoint slides prepared by S. K. Mitra 2-1-2

© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (2/10)
• Graphical representation of a discrete-time signal with
real-valued samples is as shown below:

Original PowerPoint slides prepared by S. K. Mitra 2-1-3

© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (3/10)
• In some applications, a discrete-time sequence {x[n]}
may be generated by periodically sampling a continuous-
time signal xa(t) at uniform intervals of time

• Here,
H th
the n-th
th sample
l iis given
i b
by

Original PowerPoint slides prepared by S. K. Mitra 2-1-4

© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (4/10)
• The spacing T between two consecutive samples is
called the sampling interval or sampling period
• Reciprocal of sampling interval T, denoted as FT, is
called the sampling frequency (in Hz)

• A complex
p sequence
q {{x[n]}
[ ]} can be written as {{x[n]}
[ ]} =
{xre[n]}+ j{xim[n]} where xre[n] and xim[n] are the real and
imaginary parts of x[n]
• Often the braces are ignored to denote a sequence if
there is no ambiguity

Original PowerPoint slides prepared by S. K. Mitra 2-1-5

© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (5/10)
• Example - {x[n]} = {cos0.25n} is a real sequence
• {y[n]} = {ej0.3n} is a complex sequence
• We can rewrite

where

Original PowerPoint slides prepared by S. K. Mitra 2-1-6

© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (6/10)
• Two types of discrete-time signals:
– Sampled-data signals in which samples are
continuous-valued
– Digital signals in which samples are discrete-
valued
l d (by
(b quantizing
ti i the
th sample l values
l either
ith byb
rounding or truncation)

Original PowerPoint slides prepared by S. K. Mitra 2-1-7

© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (7/10)
• A discrete-time signal may be a finite-length or an
infinite-length sequence
• Example - x[n] = n2, − 3 ≤ n ≤ 4 is a finite-length
sequence of length 8
• y[n] = cos0.4n is an infinite-length sequence
• A length-N
g sequence
q is often referred to as an N-point
p
sequence
• The length
g of a finite-length
g sequence
q can be
increased by zero-padding, i.e., by appending it with
zeros

Original PowerPoint slides prepared by S. K. Mitra 2-1-8

© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (8/10)
• A right-sided sequence x[n] has zero-valued samples
for n < N1

• If N1 ≥ 0,
0 a right-sided
i h id d sequence iis called
ll d a causall
sequence
• A left-sided
l ft id d sequence x[n]
[ ] has
h zero-valued
l d samplesl ffor
n > N2 (called a anti-causal sequence if N2 ≤ 0)

Original PowerPoint slides prepared by S. K. Mitra 2-1-9

© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (9/10)
• Size of a Signal - given by the norm of the signal

Lp-norm：

where p is a positive integer

• The value of p is typically
yp y 1 or 2 or ∞
L2-norm x 2
is the root-mean-squared (rms) value of {x[n]}
norm x
L1-norm 1 is the mean absolute value of {x[n]}
L∞-norm x ∞ is the peak absolute value of {x[n]} (why?)
x ∞ = x m ax
Original PowerPoint slides prepared by S. K. Mitra 2-1-10
© The McGraw-Hill Companies, Inc., 2007
 Discrete-Time Signals: Time-Domain
Representation (10/10)
Example -
• Let {y[n]}, 0 ≤ n ≤ N −1, be an approximation of {x[n]}, 0 ≤
n ≤ N −1
• An estimate of the relative error is given by the ratio of the
L2-norm of the difference signal and the L2-norm of {x[n]}:
1/ 2
⎛ N −1
2 ⎞
⎜ ∑ y [ n ] − x[ n ] ⎟
E rel =⎜ n=0
N −1
⎟
⎜ ⎟
∑
2
⎜ x [ n ] ⎟
⎝ n=0 ⎠

Original PowerPoint slides prepared by S. K. Mitra 2-1-11

© The McGraw-Hill Companies, Inc., 2007
 Elementary Operations on Sequences

• Product (modulation) operation:

– An application is in forming a finite-length sequence from an

infinite-length sequence by multiplying the latter with a finite-
g sequence
length q called an window sequence
q ((windowing) g)

Original PowerPoint slides prepared by S. K. Mitra 2-1-12

© The McGraw-Hill Companies, Inc., 2007
 Elementary Operations on Sequences

• Addition operation:

• Multiplication operation:

• Time-shifting operation: y[n] = x[n − N]

(Unit Delay)

(Unit Advance)

Original PowerPoint slides prepared by S. K. Mitra 2-1-13

© The McGraw-Hill Companies, Inc., 2007
 Elementary Operations on Sequences

• Time-reversal (folding) operation:

y[n] = x[−n]
• Branching operation: used to provide multiple copies of
q
a sequence

• Example:

Original PowerPoint slides prepared by S. K. Mitra 2-1-14

© The McGraw-Hill Companies, Inc., 2007
 Elementary Operations on Sequences
Ensemble Averaging
• An application of the addition operation in improving the
quality of measured data corrupted by an additive
random noise
• Let di denote the noise vector corrupting
p g the i-th
measurement of the uncorrupted data vector s

• The average data vector, called the ensemble average,

obtained after K measurements is given by

Original PowerPoint slides prepared by S. K. Mitra 2-1-15

© The McGraw-Hill Companies, Inc., 2007
 Elementary Operations on Sequences

Original PowerPoint slides prepared by S. K. Mitra 2-1-16

© The McGraw-Hill Companies, Inc., 2007
 Combinations of Basic Operations

• Example -

Original PowerPoint slides prepared by S. K. Mitra 2-1-17

© The McGraw-Hill Companies, Inc., 2007
 Sampling Rate Alteration

• A process to generate a new sequence y[n] with a

sampling FT′ rate higher or lower than that of the sampling
rate FT of a given sequence x[n]
• Sampling rate alteration ratio:

– if R > 1, the process called interpolation

– if R < 1,
1 the process called decimation

Original PowerPoint slides prepared by S. K. Mitra 2-1-18

© The McGraw-Hill Companies, Inc., 2007
 Up Sampling
Up-Sampling
• In up-sampling by an integer factor L > 1
1, L −1
1 equidistant
zero-valued samples are inserted between each two
p
consecutive samples of the input
p sequence
q x[n]:
[ ]

Original PowerPoint slides prepared by S. K. Mitra 2-1-19

© The McGraw-Hill Companies, Inc., 2007
 Down Sampling
Down-Sampling
• In down-sampling by an integer factor M > 1,
1 every M-th
samples of the input sequence are kept and M −1 in-
between samples
p are removed:

Original PowerPoint slides prepared by S. K. Mitra 2-1-20

© The McGraw-Hill Companies, Inc., 2007
 Classification of Sequences
q
Based on Symmetry (1/4)
• Conjugate-symmetric sequence:

– If x[n] is real, then it is an even sequence

– for a conjugate-symmetric sequence {x[n]}, x[0]
must be a real number

Original PowerPoint slides prepared by S. K. Mitra 2-1-21

© The McGraw-Hill Companies, Inc., 2007
 Classification of Sequences
q
Based on Symmetry (2/4)
• Conjugate-antisymmetric sequence:

– If x[n] is real, then it is an odd sequence

– for a conjugate anti-symmetric sequence {y[n]}, y[0]
must be an imaginary number

Original PowerPoint slides prepared by S. K. Mitra 2-1-22

© The McGraw-Hill Companies, Inc., 2007
 Classification of Sequences
q
Based on Symmetry (3/4)
• Any complex sequence can be expressed as a sum of its
conjugate-symmetric part and its conjugate-antisymmetric
part:

where

• Consider the length-7 sequence defined for − 3 ≤ n ≤ 3

Original PowerPoint slides prepared by S. K. Mitra 2-1-23

© The McGraw-Hill Companies, Inc., 2007
 Classification of Sequences
q
Based on Symmetry (4/4)
• Any real sequence can be expressed as a sum of its
even part and its odd part:

where

Original PowerPoint slides prepared by S. K. Mitra 2-1-24

© The McGraw-Hill Companies, Inc., 2007
 Classification of Sequences
q
Based on Periodicity
• A sequence satisfying is is called a
periodic sequence with a period N where N is a positive
integer and k is any integer
• Smallest value of N satisfying is called
the fundamental period

• A sequence not satisfying the periodicity condition is

called an aperiodic sequence
Original PowerPoint slides prepared by S. K. Mitra 2-1-25
© The McGraw-Hill Companies, Inc., 2007
 Classification of Sequences
q
Energy & Power Signals (1/3)
• Total energy of a sequence x[n] is defined by

• An infinite length sequence with finite sample values

may or may not have finite energy
• The average power of an aperiodic sequence is
defined by

• Define the energy of a sequence x[n] over a finite

interval − K ≤ n ≤ K as

Original PowerPoint slides prepared by S. K. Mitra 2-1-26

© The McGraw-Hill Companies, Inc., 2007
 Classification of Sequences
q
Energy & Power Signals (2/3)
• The average power of a periodic sequence with a
period N is given by

• The averageg p power of an infinite-length

g sequence
q may
y
be finite or infinite
• Example - Consider the causal sequence defined by

• Note: x[n] has infinite energy, its average power is

Original PowerPoint slides prepared by S. K. Mitra 2-1-27

© The McGraw-Hill Companies, Inc., 2007
 Classification of Sequences
q
Energy & Power Signals (3/3)
• An infinite energy signal with finite average power is
called a power signal
– Example - A periodic sequence which has a finite
average power but infinite energy
• A finite energy signal with zero average power is called
an energy signal
– Example - A finite-length sequence which has finite
energy but zero average power

Original PowerPoint slides prepared by S. K. Mitra 2-1-28

© The McGraw-Hill Companies, Inc., 2007
 Other Types of Classification (1/2)
• A sequence x[n] is said to be bounded if。

–E
Example
l - The
Th sequence x[n]
[ ] = cos0.3πn
03 i ab
is bounded
d d
sequence as

• A sequence x[n] is said to be absolutely summable if

– Example - The following sequence is absolutely

summable

Original PowerPoint slides prepared by S. K. Mitra 2-1-29

© The McGraw-Hill Companies, Inc., 2007
 Other Types of Classification (2/2)

• A sequence x[n] is said to be square summable if。

– Example - The sequence

is square-summable but not absolutely summable

Original PowerPoint slides prepared by S. K. Mitra 2-1-30

© The McGraw-Hill Companies, Inc., 2007
 Basic Sequences (1/7)

• Unit Sample Sequence -

• Unit Step
p Sequence
q -

Original PowerPoint slides prepared by S. K. Mitra 2-1-31

© The McGraw-Hill Companies, Inc., 2007
 Basic Sequences (2/7)

• Real Sinusoidal Sequence –

Example: A = 2, ωo = 0.1

Original PowerPoint slides prepared by S. K. Mitra 2-1-32

© The McGraw-Hill Companies, Inc., 2007
 Basic Sequences (3/7)

• Exponential Sequence –
where A and α are real or complex numbers
• If we write

Original PowerPoint slides prepared by S. K. Mitra 2-1-33

© The McGraw-Hill Companies, Inc., 2007
 Basic Sequences (4/7)
• Sinusoidal sequence Acos(ωon + ϕ) and complex
exponential
ti l sequence Bexp(
B ( jjωon ) are periodic
i di
sequences of period N if ωoN = 2πr where N and r are
positive integers
• Smallest value of N satisfying ωoN = 2πr is the
fundamental period of the sequence
• To verify the above fact, consider

• x1[n] = x2[n] if and only if ωoN = 2πr or

• If 2π/ωo is a noninteger rational number, then the period
will
ill b
be a multiple
lti l off 2π/ω
2 / o; otherwise,
th i it’
it’s aperiodic
i di
Original PowerPoint slides prepared by S. K. Mitra 2-1-34
© The McGraw-Hill Companies, Inc., 2007
 Basic Sequences (5/7)

• Here ωo = 0 • Here ωo = 0.1π

• period • period

Original PowerPoint slides prepared by S. K. Mitra 2-1-35

© The McGraw-Hill Companies, Inc., 2007
 Basic Sequences (6/7)
• Property 1 - Consider x[n] = exp(jω1n) and y[n] =
exp(jω2n) with 0 ≤ ω1 < π and 2πk ≤ ω2 < 2π(k +1)
where k is anyy positive
p integer
g
– If ω2 = ω1 + 2πk, then x[n] = y[n]
– then x[n]
[ ] and y[
y[n]] are indistinguishable
g
• Property 2 - The frequency of oscillation of Acos(ωon)
increases as increases from 0 to π, and then decreases
as increases from π to 2π
– frequencies in the neighborhood of ω = 0 (or 2kπ) are
called low frequencies, whereas, frequencies in the
neighborhood of ω = π (or (2k+1)π) are called high
frequencies
Original PowerPoint slides prepared by S. K. Mitra 2-1-36
© The McGraw-Hill Companies, Inc., 2007
 Basic Sequences (7/7)

• An arbitrary sequence can be represented in the time-

domain as a weighted sum of some basic sequence and
its delayed (advanced) versions

Original PowerPoint slides prepared by S. K. Mitra 2-1-37

© The McGraw-Hill Companies, Inc., 2007
 The Sampling Process (1/3)
• Sampling
S li P Process
• Convert x(t) to numbers x[n]
• “n” is an integer; x[n] is a sequence of values
• Think of “n” as the storage address in memory
• Uniform Sampling at t = nT
• IDEAL: x[n] = x(nT)

x(t) x[n]
C-to-D

Original PowerPoint slides prepared by S. K. Mitra 2-1-38

© The McGraw-Hill Companies, Inc., 2007
 The Sampling Process (2/3)

• Often, a discrete-time sequence x[n] is developed by

uniformly sampling a continuous-time signal as follows

• Time variable t of xa(t) is related to the time variable n of

x[n] only at discrete-time instants given by

Original PowerPoint slides prepared by S. K. Mitra 2-1-39

© The McGraw-Hill Companies, Inc., 2007
 The Sampling Process (3/3)
• Consider the continuous-time
continuous time signal

• The corresponding discrete-time signal is

i th
is the normalized
li d di
digital
it l angular
l ffrequency off x[n]
[ ]
• The unit of normalized digital angular frequency ωo is
radians/sample
di / l (Ω o : radians/second)
di / d)
Original PowerPoint slides prepared by S. K. Mitra 2-1-40
© The McGraw-Hill Companies, Inc., 2007
 Sampling for Audio CD
• x[n] is a sampled sinusoid
– A list of numbers stored in memory
• Example: audio CD
• CD rate is 44,100 samples per second
– 16
16-bit
bit samples
l
– Stereo uses 2 channels
• Number
N b off b
bytes
t ffor 1 minute
i t iis
– 2 X (16/8) X 60 X 44100 = 10.584 Mbytes
– So,
So a CD
CD-ROM
ROM of 680
680-Mbyte
Mb te can store up
p to abo
aboutt
one-hour music
– What about MP3?
Original PowerPoint slides prepared by S. K. Mitra 2-1-41
© The McGraw-Hill Companies, Inc., 2007
 Ambiguity in Sampling
• Sa
Sample
p e tthe
e following
o o g tthree
ee ssignals
g a s at 10
0 Hz

• we obtain

g1[n] = g2[n] = g3[n]

Original PowerPoint slides prepared by S. K. Mitra 2-1-42

© The McGraw-Hill Companies, Inc., 2007
 Aliasing (1/2)
• The phenomenon of a continuous-time signal of higher
frequency acquiring the identity of a sinusoidal sequence
of lower frequency after sampling is called aliasing
• There are an infinite number of continuous-time signals
that can lead to the same sequence when sampled
periodically
• The family of continuous-time sinusoids leads to identical
sampled signals
xa ,k (t ) = A cos((Ω ot + φ ) + k ΩT t ), k = 0, ±1, ±2,...
⎛ 2π ( Ωo + k ΩT ) n ⎞
xa ,k (nT ) = A cos((Ω o + k ΩT )nT + φ ) = A cos ⎜ +φ ⎟
⎝ Ω T ⎠
⎛ 2πΩo n ⎞
= A cos ⎜ + φ ⎟ = a cos(ωo n + φ ) = x[n]
⎝ Ω T ⎠
Original PowerPoint slides prepared by S. K. Mitra 2-1-43
© The McGraw-Hill Companies, Inc., 2007
 Aliasing (2/2)
Given
G e tthe
e sa
samples,
p es, d
draw
a a ssinusoid
uso d tthrough
oug tthe
e values
a ues

When n is an integer
x[n ] = cos(0.4π n ) cos((0.4π n ) = cos((2.4π n )
Original PowerPoint slides prepared by S. K. Mitra 2-1-44
© The McGraw-Hill Companies, Inc., 2007
 Sampling Theorem (1/2)
• Recall
R ll

• Th
Thus if ΩT > 2Ωo, then
th the
th corresponding
di normalized
li d
digital angular frequency ωo of the discrete-time signal
obtained by sampling the parent continuous-time
continuous time
sinusoidal signal will be in the range − π < ω < π
No Aliasing

• On the other hand,, if ΩT < 2Ωo, the normalized digital

g
angular frequency will foldover into a lower digital
frequency ωo = ‫ۃ‬2πΩo / ΩT‫ۄ‬2π in the range − π < ω < π
because of aliasing
Original PowerPoint slides prepared by S. K. Mitra 2-1-45
© The McGraw-Hill Companies, Inc., 2007
 Sampling Theorem (2/2)

• To prevent aliasing, the sampling frequency ΩT should be

greater than 2 times the frequency Ωo of the sinusoidal
signal being sampled
• Generalization: Consider an arbitrary continuous-time
signal x(t) composed of a weighted sum of a number of
sinusoidal signals

Original PowerPoint slides prepared by S. K. Mitra 2-1-46

© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System
Discrete-Time
• A discrete-time
discrete time system processes a given input sequence
x[n] to generates an output sequence y[n] with more
desirable properties
• In most applications, the discrete-time system is a single-
input single-output
input, single output system:

• 2-input, 1-output discrete-time systems - Modulator, adder

• 1-input, 1-output discrete-time systems - Multiplier, unit
delay, unit advance

Original PowerPoint slides prepared by S. K. Mitra 2-2-47

© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (1/10)
Discrete-Time
• Accumulator
ccu u ato -

• The output y[n] is the sum of the input sample x[n] and
the p
previous output
p y[y[n −1]]
• The system cumulatively adds, i.e., it accumulates all
input sample values
• Input-output relation can also be written in the form

• The second form is used for a causal input sequence, in

which case y[−1] is called the initial condition
Original PowerPoint slides prepared by S. K. Mitra 2-2-48
© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (2/10)
Discrete-Time
• M-point moving-average system -

• Used in smoothing random variations in data

• A direct implementation of the M-point
M point moving average
system requires M −1 additions, 1 division
• A more efficient implementation,
implementation which requires 2
additions and 1division

Original PowerPoint slides prepared by S. K. Mitra 2-2-49

© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (3/10)
Discrete-Time
• An application: Consider x[n] = s[n] + d[n] where s[n] is
the signal corrupted by a noise d[n]

Original PowerPoint slides prepared by S. K. Mitra 2-2-50

© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (4/10)
Discrete-Time
• Exponentially
po e t a y Weighted
e g ted Running
u g Average
e age Filter
te

• requires
i only
l 2 additions,
dditi 1 multiplication
lti li ti andd storage
t off
the previous running average
• does not require storage of past input data samples
• the filter places more emphasis on current data samples
and less emphasis on past ones as illustrated below

Original PowerPoint slides prepared by S. K. Mitra 2-2-51

© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (5/10)
Discrete-Time

• Linear interpolation - employed to estimate sample

values between pairs of adjacent sample values of a
discrete time sequence
discrete-time
• Factor-of-4 interpolation

Original PowerPoint slides prepared by S. K. Mitra 2-2-52

© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (6/10)
Discrete-Time

• Factor-of-2 interpolator

• Factor-of-3
Factor of 3 interpolator

Original PowerPoint slides prepared by S. K. Mitra 2-2-53

© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (7/10)
Discrete-Time

• Factor-of-2 interpolator

Original PowerPoint slides prepared by S. K. Mitra 2-2-54

© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (8/10)
Discrete-Time
Median Filter –
• The median of a set of (2K+1) numbers is the number
such that K numbers from the set have values greater than
this number and the other K numbers have values smaller
• Median can be determined by rank-ordering the numbers
in the set by their values and choosing the number at the
middle
• Example:
E l CConsider
id th the sett off numbers
b

• Rank-order
R k d sett iis given
i b
by

• med{2, − 3, 10, 5, −1} = 2

Original PowerPoint slides prepared by S. K. Mitra 2-2-55
© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (9/10)
Discrete-Time

Median Filter –
• Implemented
p by
y sliding
g a window of odd length
g over the
input sequence {x[n]} one sample at a time
• Output
p y[y[n]] at instant n is the median value of the
samples inside the window centered at n
• Useful in removing additive random noise, which shows
up as sudden large errors in the corrupted signal
• Usually used for the smoothing of signals corrupted by
impulse noise

Original PowerPoint slides prepared by S. K. Mitra 2-2-56

© The McGraw-Hill Companies, Inc., 2007
 Discrete Time System Examples (10/10)
Discrete-Time
• Median
ed a Filtering
te g Example
a pe–

Original PowerPoint slides prepared by S. K. Mitra 2-2-57

© The McGraw-Hill Companies, Inc., 2007
 Classifications of Discrete-Time
Systems
• Linear system
• Shift-invariant
Shift invariant system)
• Causal system
• Stable system
• Passive and lossless system

Original PowerPoint slides prepared by S. K. Mitra 2-2-58

© The McGraw-Hill Companies, Inc., 2007
 Linear Discrete
Discrete-Time
Time Systems (1/3)
• Definition
e t o - If iss thee ou
output
pu y1[[n]] due to
oaan input
pu x1[[n]] and
a d
y2[n] is the output due to an input x2[n] then for an input
x[n]
[ ] =αx1[[n]] + β
βx2[[n]]
the output is given by
y[n]] =αyy1[[n]] + βy2[[n]]
y[
for any arbitrary constants α and β
• Example: Accumulator –
For an input

the output is

Original PowerPoint slides prepared by S. K. Mitra 2-2-59

© The McGraw-Hill Companies, Inc., 2007
 Linear Discrete
Discrete-Time
Time Systems (2/3)
• If the outputs y1[n] and y2[n] for inputs x1[n] and x2[n]
are given by y [ n ] = y [ − 1] + n x [ l ]
1 1 ∑ 1 l =0
n
y 2 [ n ] = y 2 [ − 1] + ∑ x 2 [ l ]
l =0

• The output y[n] for an input αx1[n] + βx2[n] is

• Now αy1[n] + βy2 [n]

n n
= α( y1[−1] + ∑ x1[l ]) + β( y2 [−1] + ∑ x2 [l ]
l =0 l =0
n n
= (αy1[−1] + βy2 [−1]) + (α ∑ x1[l ] + β∑ x2 [l ])
Original PowerPoint slides prepared by S. K. Mitra l =0 l =0 2-2-60
© The McGraw-Hill Companies, Inc., 2007
 Linear Discrete
Discrete-Time
Time Systems (3/3)

• For the causal accumulator to be linear the condition

y[-1] = αy1 [-1] + βy2 [-1] must hold for all initial
conditions y[−1].
y[−1] y1 [-1],
[ 1] y2 [-1]
[ 1] , and constants α and β
• This condition cannot be satisfied unless the
accumulator is initially at rest with zero initial condition
• For nonzero initial condition, the system is nonlinear

Original PowerPoint slides prepared by S. K. Mitra 2-2-61

© The McGraw-Hill Companies, Inc., 2007
 Non Linear Discrete
Non-Linear Discrete-Time
Time Systems
• The median filter described earlier is a nonlinear discrete-
time system
• To show this,
this consider a median filter with a window of
length 3
• The output of the filter for an input {x1[n]}= {3,
{3 4,
4 5}， 0 ≤ n ≤
2, is {y1[n]}= {3, 4, 4}， 0 ≤ n ≤ 2
• The output for an input {x2[n]} [n]}= {2, −1,1, −1},
1}, 0 ≤ n ≤ 2 is
{y2[n]}= {0, −1, −1}, 0 ≤ n ≤ 2
• However,, the output p for an input p {{x[n]}=
[ ]} {{x1[[n]] + x2[[n]}
]} is
{y[n]}= {3, 4, 3} ≠ {y1[n] + y2[n]}= {3, 3, 3}
• Hence, the median filter is a nonlinear discrete-time system

Original PowerPoint slides prepared by S. K. Mitra 2-2-62

© The McGraw-Hill Companies, Inc., 2007
 Shift Invariant Systems (1/2)

• For a shift-invariant system, if y1[n] is the response to an

input x1[n], then the response to an input x[n] = x1[n − n0]
is simply
y[n] = y1[n − n0]
where n0 is any positive or negative integer
• In the case of sequences and systems with indices n
related to discrete instants of time
time, the above property is
called time-invariance property
• Time
Time-invariance
invariance property ensures that for a specified
input, the output is independent of the time the input is
being applied

Original PowerPoint slides prepared by S. K. Mitra 2-2-63

© The McGraw-Hill Companies, Inc., 2007
 Shift Invariant Systems (2/2)
• Example – Consider the following up-sampler

• for
f input
i t x1[n]
[ ] = x[n
[ − no] ，the
th output
t t x1,u[n]
[ ] is
i

• However, the upsampler is a time-varying system because

⎧ x[(n − n0 ) / L],
] n = n0 , n0 ± L, n0 ± 2 L,...
xu [n − n0 ] = ⎨
⎩ 0, otherwise
≠ x1,u [n]
Original PowerPoint slides prepared by S. K. Mitra 2-2-64
© The McGraw-Hill Companies, Inc., 2007
 Linear Time
Time-Invariant
Invariant Systems

• Linear Time-Invariant (LTI) System - A system

satisfying both the linearity and the time-invariance
property
• LTI systems are mathematically easy to analyze and
characterize and consequently,
characterize, consequently easy to design
• Highly useful signal processing algorithms have been
developed utilizing this class of systems over the last
several decades

Original PowerPoint slides prepared by S. K. Mitra 2-2-65

© The McGraw-Hill Companies, Inc., 2007
 Causal Systems (1/2)

• In a causal system, the no-th output sample y[no]

depends only on input samples x[n] for n ≤ no and does
not depend on input samples for n > no
• Let y1[n] and y2[n] be the responses of a causal system to
the inputs x1[n] and x2[n] , respectively.
respectively Then
x1[n] = x2[n] for n < N
Implied also that
y1[[n]] = y2[[n]] for n < N
• For a causal system, changes in output samples do not
precede changes
p g in the input
p samples
p
Original PowerPoint slides prepared by S. K. Mitra 2-2-66
© The McGraw-Hill Companies, Inc., 2007
 Causal Systems (2/2)
• Examples of causal systems:

• Examples of noncausal systems:

y[n] = xu[n] + 1/2 (xu[n −1] + xu[n +1])
y[n] = xu[n] + 1/3 (xu[n −1] + xu[n +2]) + 2/3 (xu[n −2] + xu[n +1])
• A noncausal system can be made causal by delaying the
output by an appropriate number of samples
• A causal implementation of the factor-of-2 interpolator

Original PowerPoint slides prepared by S. K. Mitra 2-2-67

© The McGraw-Hill Companies, Inc., 2007
 Stable Systems
• Bounded-Input,
ou ded put, Bounded
ou ded Output (BIBO)
( O) stab
stability
ty
• If y[n] is the response to an input x[n] and if

then

• Example – the M-point moving average filter is BIBO

stable

• With a bounded input

Original PowerPoint slides prepared by S. K. Mitra 2-2-68

© The McGraw-Hill Companies, Inc., 2007
 Passive and Lossless Systems
• A d
discrete-time
sc ete t e syste
system iss de
defined
ed to be pass
passivee if,, for
o
every finite-energy input x[n], the output y[n] has, at
most, the same energy
∞ ∞

∑ ∑
2 2
y[ n ] ≤ x[ n ]
n = −∞ n = −∞
• For a lossless system,
system the above inequality is satisfied
with an equal sign for every input
p - Consider the discrete-time system
• Example y defined byy
y[n] =α x[n − N] with N a positive integer
• Its output energy is given by

passive system if ǀαǀ <1, and lossless if ǀαǀ =1

Original PowerPoint slides prepared by S. K. Mitra 2-2-69
© The McGraw-Hill Companies, Inc., 2007
 Impulse & Step Responses
• The
e response
espo se o
of a ddiscrete-time
sc ete t e syste
system to a u
unitt sa
sample
pe
sequence {δ[n]} is called, the (unit) impulse response,
and is denoted byy {{h[n]}
[ ]}
• The response of a discrete-time system to a unit step
sequence
q (μ[n]),
(μ[ ]) is called the ((unit)) step
p response,
p and
is denoted by {s[n]}
• Example - The impulse response {h[n]} of the factor-of-2
interpolator

Is obtained by

Original PowerPoint slides prepared by S. K. Mitra 2-2-70

© The McGraw-Hill Companies, Inc., 2007
 Impulse Response
• Example
a p e - The
e impulse
pu se response
espo se o
of tthe
eddiscrete-time
sc ete t e
accumulator

is obtained by setting x[n] = δ[n] resulting in

• Example - The impulse response {h[n]} of the factor-of-2

factor of 2
interpolator 1
y[n] = xu [n] + ( xu [n − 1] + xu [n + 1])
2
is 1
h[n] = δ[n] + (δ[n − 1] + δ[n + 1])
2
Original PowerPoint slides prepared by S. K. Mitra 2-2-71
© The McGraw-Hill Companies, Inc., 2007
 Time-Domain Characterization of LTI
Discrete-Time System (1/3)
• Input-Output Relationship -
A consequence of the linear, time-invariance property is
th t an LTI di
that discrete-time
t ti system
t is
i completely
l t l
characterized by its impulse response
Knowing the impulse response,
response one can compute
the output of the system for any arbitrary input
• Let h[n] denote the impulse response of an LTI discrete-
time system, we can compute y[n] for the input:

• We can compute its outputs for each member of the input

separately and add the individual outputs to determine y[n]
(Linearity)
Original PowerPoint slides prepared by S. K. Mitra 2-2-72
© The McGraw-Hill Companies, Inc., 2007
 Time-Domain Characterization of LTI
Discrete-Time System (2/3)
• Since the system is LTI

• Because of the linearity property we get

Original PowerPoint slides prepared by S. K. Mitra 2-2-73

© The McGraw-Hill Companies, Inc., 2007
 Time-Domain Characterization of LTI
Discrete-Time System (3/3)
• Now, any arbitrary input sequence x[n] can be expressed
as a linear combination of delayed and advanced unit
sample sequences in the form:

• The response of the LTI system to an input x[k]δ[n − k]

will be x[k]h[n − k]
• Hence,
H the
h response y[n]
[ ] to an input
i

will be
or

Original PowerPoint slides prepared by S. K. Mitra 2-2-74

© The McGraw-Hill Companies, Inc., 2007
 Convolution Sum (1/3)
• The
e su
summation
at o

is called the convolution sum of the sequences x[n]

[ ] and represented
and h[n] p as

• Properties
p of convolution
– Commutative property:

– Associative property :

– Distributive property :
Original PowerPoint slides prepared by S. K. Mitra 2-2-75
© The McGraw-Hill Companies, Inc., 2007
 Convolution Sum (2/3)
• Interpretation –
– Time-reverse h[k] to form h[-k]
– Shift h[-k]
h[ k] to the right by n sampling periods if n > 0 (or
shift to the left by n sampling periods if n < 0) to form
h[n-k]
[ ]
– Form the product v[k] = x[k]h[n-k]
– Sum all samples p of v[k]
[ ] to develop
p the n-th sample
p of
y[n] of the convolution sum

Original PowerPoint slides prepared by S. K. Mitra 2-2-76

© The McGraw-Hill Companies, Inc., 2007
 Convolution Sum (3/3)
• The computation of an output sample using the
convolution sum is simply a sum of products
• Involves fairly simple operations such as additions
additions,
multiplications, and delays
• We illustrate the convolution operation for the following
two sequences:

• The next several slides illustrate the convolution process

Original PowerPoint slides prepared by S. K. Mitra 2-2-77
© The McGraw-Hill Companies, Inc., 2007
 Convolution (1/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-78

© The McGraw-Hill Companies, Inc., 2007
 Convolution (2/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-79

© The McGraw-Hill Companies, Inc., 2007
 Convolution (3/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-80

© The McGraw-Hill Companies, Inc., 2007
 Convolution (4/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-81

© The McGraw-Hill Companies, Inc., 2007
 Convolution (5/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-82

© The McGraw-Hill Companies, Inc., 2007
 Convolution (6/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-83

© The McGraw-Hill Companies, Inc., 2007
 Convolution (7/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-84

© The McGraw-Hill Companies, Inc., 2007
 Convolution (8/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-85

© The McGraw-Hill Companies, Inc., 2007
 Convolution (9/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-86

© The McGraw-Hill Companies, Inc., 2007
 Convolution (10/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-87

© The McGraw-Hill Companies, Inc., 2007
 Convolution (11/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-88

© The McGraw-Hill Companies, Inc., 2007
 Convolution (12/12)

Original PowerPoint slides prepared by S. K. Mitra 2-2-89

© The McGraw-Hill Companies, Inc., 2007
 Computing Convolution Sum

• In practice, if either the input or the impulse response is

of finite length, the convolution sum can be used to
compute the output sample as it involves a finite sum of
products
• If both the input sequence and the impulse response
sequence are of finite length, the output sequence is
also of finite length
• If both the input sequence and the impulse response
sequence are of infinite length, convolution sum cannot
be used to compute the output

Original PowerPoint slides prepared by S. K. Mitra 2-2-90

© The McGraw-Hill Companies, Inc., 2007
 Convolution: Step by Step (1/4)
• Example
a p e - Develop
e e op the
t e sequence
seque ce y[
y[n]] ge
generated
e ated by tthe
e
convolution of the sequences x[n] and h[n] shown below

• As can be seen from the shifted time-reversed version

{h[n − k]} for n < 0, shown below for , for any value of the
sample index k, the k-th sample of either {x[k]} or {h[n −
k]} is zero

Original PowerPoint slides prepared by S. K. Mitra 2-2-91

© The McGraw-Hill Companies, Inc., 2007
 Convolution: Step by Step (2/4)

• As a result, for n < 0, the product of the k-th samples of

{x[k]} and {h[n − k]} is always zero, and hence
y[n]
[ ] = 0 for
f n<0
• Consider now the computation of y[0]
• The
Th sequence {h[−k]}
{h[ k]} is
i shown
h on th
the right
i ht
• The product sequence {x[k]h[−k]} is plotted below which
has a single nonzero sample x[0]h[0] for k = 0
• Thus y[0] = x[0]h[0] = −2

Original PowerPoint slides prepared by S. K. Mitra 2-2-92

© The McGraw-Hill Companies, Inc., 2007
 Convolution: Step by Step (3/4)

• For the computation of y[1], we shift {h[-k]} to the right by

one sample period to form {h[1-k]} as shown below
• Hence,
H y[1]
[1] = x[0]h[1]
[0]h[1] + x[1]h[0]
[1]h[0] = −4
4 + 0 = −4
4

• Similarly, y[2] = x[0]h[2] + x[1]h[1] + x[2]h[0] =1

Original PowerPoint slides prepared by S. K. Mitra 2-2-93

© The McGraw-Hill Companies, Inc., 2007
 Convolution: Step by Step (4/4)

• Repeat the process, we obtain the following output

• In general, if the lengths of the two sequences being

convolved are M and N, then the sequence generated by
th convolution
the l ti iis off llength
th M + N −11
Original PowerPoint slides prepared by S. K. Mitra 2-2-94
© The McGraw-Hill Companies, Inc., 2007
 Tabular Method of Convolution Sum
Computation (1/2)
• Can be used to convolve two finite-length sequences

Original PowerPoint slides prepared by S. K. Mitra 2-2-95

© The McGraw-Hill Companies, Inc., 2007
 Tabular Method of Convolution Sum
Computation (2/2)
• The method can also be applied to convolve two finite-
length two-sided sequences。
• In
I this
thi case, a decimal
d i l point i t iis fifirstt placed
l d tto th
the right
i ht off
the sample with the time index n = 0 for each sequence
• Next,
Next convolution is computed ignoring the location of the
decimal point
• Finally,
Finally the decimal point is inserted according to the rules
of conventional multiplication
• The sample immediately to the left of the decimal point is
then located at the time index n = 0

Original PowerPoint slides prepared by S. K. Mitra 2-2-96

© The McGraw-Hill Companies, Inc., 2007
 Simple Interconnection Schemes
• Two simple interconnection schemes are:
– Cascade Connection

– Parallel Connection

Original PowerPoint slides prepared by S. K. Mitra 2-2-97

© The McGraw-Hill Companies, Inc., 2007
 Cascade Connection (1/2)
• The ordering of the systems in the cascade has no effect on
the overall impulse response
• A cascade connection of two stable systems is stable
• A cascade connection of two passive (lossless) systems is
passive (lossless)
• An application is in the development of an inverse system
• If the cascade connection satisfies the relation

then the LTI system h1[n] is said to be the inverse of h2[n]

and vice-versa

Original PowerPoint slides prepared by S. K. Mitra 2-2-98

© The McGraw-Hill Companies, Inc., 2007
 Cascade Connection (2/2)
• Example - Consider the discrete-time accumulator with
an impulse response μ[n]
• Its inverse system satisfy the condition

• It follows
f ll from
f the
th above
b that
th t h2[n]
[ ] = 0 for
f n < 0 and
d

• Thus the impulse response of the inverse system of the

discrete-time accumulator is given by
(b k
(backward
d diff
difference system)
t )
Original PowerPoint slides prepared by S. K. Mitra 2-2-99
© The McGraw-Hill Companies, Inc., 2007
 Interconnection Schemes
• Co
Consider
s de tthe
eddiscrete-time
sc ete t e syste
system where
ee

Original PowerPoint slides prepared by S. K. Mitra 2-2-100

© The McGraw-Hill Companies, Inc., 2007
 Stability Condition of an LTI
Discrete-Time System (1/3)
• BIBO O Stability
Stab ty Condition
Co d t o - A d discrete-time
sc ete t e syste
system is
s
BIBO stable if and only if the output sequence {y[n]}
remains bounded for all bounded input sequence {x[n]}
• An LTI discrete-time system is BIBO stable if and only if
its impulse response sequence {h[n]} is absolutely
summable,
bl ii.e.

• P
Proof:
f Assume
A h[ ] is
h[n] i a reall sequence
• Since the input sequence x[n] is bounded we have
therefore

Original PowerPoint slides prepared by S. K. Mitra 2-3-101

© The McGraw-Hill Companies, Inc., 2007
 Stability Condition of an LTI
Discrete-Time System (2/3)
• Thus, S < ∞ implies ǀy[n]ǀ ≤ By < ∞, indicating that y[n] is
also bounded
• To
T prove theth converse, assume y[n] [ ] is
i bounded,
b d d ii.e., ǀy[n]ǀ
ǀ [ ]ǀ
≤ By
• Consider the bounded input given by
x[n] = sgn(h[−n]) where sgn(c) = 1, for c ≥ 0, and
sgn(c) = − 1 for c < 0
• For this input, y[n] at n = 0 is

• Therefore,
Therefore if S = ∞,
∞ then {y[n]} is not a bounded sequence
Original PowerPoint slides prepared by S. K. Mitra 2-3-102
© The McGraw-Hill Companies, Inc., 2007
 Stability Condition of an LTI
Discrete-Time System (3/3)
• Example - Consider a causal LTI discrete-time system
with an impulse response

• For this system

• Therefore S < ∞ if |α| < 1 , for which the system is BIBO

stable
t bl
• If |α| = 1, the system is not BIBO stable

Original PowerPoint slides prepared by S. K. Mitra 2-3-103

© The McGraw-Hill Companies, Inc., 2007
 Causality Condition of an LTI
Discrete-Time System (1/3)
• Let x1 [n] and x2 [n] be two input sequences with
x1[n] = x2[n] for n ≤ no
• The corresponding output samples at of an LTI system
with an impulse response {h[n]} are then given by

Original PowerPoint slides prepared by S. K. Mitra 2-3-104

© The McGraw-Hill Companies, Inc., 2007
 Causality Condition of an LTI
Discrete-Time System (2/3)
• If the LTI system is also causal
causal, then
y1[no] = y2[no]
• As
A x1[n]
[ ] = x2[n]
[ ] for
f n ≤ no

• This implies

• As for x1[n] ≠ x2[n] the only way the condition

holds if h[k]
[ ] = 0 for k < 0
Original PowerPoint slides prepared by S. K. Mitra 2-3-105
© The McGraw-Hill Companies, Inc., 2007
 Causality Condition of an LTI
Discrete-Time System (3/3)
• An LTI discrete-time system is causal if and only if its
impulse response {h[n]} is a causal sequence。
• Example - The discrete-time accumulator defined by

is causal as it has a causal impulse response

• Example - The factor-of-2 interpolator defined by

is noncausal as it has a noncausal impulse response

Original PowerPoint slides prepared by S. K. Mitra 2-3-106

© The McGraw-Hill Companies, Inc., 2007
 Finite-Dimensional LTI
Discrete-Time Systems
• An important subclass of LTI discrete-time
discrete time systems is
characterized by a linear constant coefficient difference
equation of the form

where {dk} and {pk} are constants characterizing the system

• The order of the system is given by max(N
max(N,M),
M) which is the
order of the difference equation
• Suppose the system is causal, then the output y[n] can be
recursively computed using
provided d0 ≠ 0
Original PowerPoint slides prepared by S. K. Mitra 2-3-107
© The McGraw-Hill Companies, Inc., 2007
 Classification of LTI Discrete-Time
Systems (1/3)
Based on Impulse Response Length -
• If the impulse response h[n] is of finite length, i.e.,
h[ ] = 0 for
h[n] f n < N1 andd n > N2, N1 < N2
then it is known as a finite impulse response (FIR)
discrete time system
discrete-time
• The convolution sum description here is

• The outputo tp t y[n] [n] of an FIR LTI discrete-time

discrete time ssystem
stem can
be computed directly from the convolution sum as it is a
finite sum of products (e (e.g.,
g moving-average
moving average filter &
interpolator)
Original PowerPoint slides prepared by S. K. Mitra 2-3-108
© The McGraw-Hill Companies, Inc., 2007
 Classification of LTI Discrete-Time
Systems (2/3)
• If the impulse response h[n] is of infinite length
length, then it is
known as a infinite impulse response (IIR) discrete-time
system
• Example - The discrete-time accumulator defined by
y[n] = y[n −1]
1] + x[n]
is an IIR system
• Example - The numerical integration formulas that are
used to numerically solve integrals of the form

can be characterized by the following 1st-order IIR system

Original PowerPoint slides prepared by S. K. Mitra 2-3-109

© The McGraw-Hill Companies, Inc., 2007
 Classification of LTI Discrete-Time
Systems (3/3)
Based on the Output Calculation Process -
• Nonrecursive System - Here the output can be
calculated sequentially
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
Based on the Coefficients -
• Real Discrete-Time System
y - The impulse
p response
p
samples are real valued
• Complex Discrete-Time System - The impulse response
samples are complex valued
Original PowerPoint slides prepared by S. K. Mitra 2-3-110
© The McGraw-Hill Companies, Inc., 2007
 Correlation of Signals (1/4)
• There
eea are
e app
applications
cat o s where
e e itt is
s necessary
ecessa y to co
compare
pa e
one reference signal with one or more signals
– to determine the similarity between the pair
– to determine additional information based on the similarity
• For example, in digital communications, the receiver has
t determine
to d t i which
hi h particular
ti l sequence h has bbeen
received by comparing the received signal with possible
sequences that may be transmitted
• Similarly, in radar and sonar applications, the received
signal reflected from the target is a delayed (and even a
distorted) version of the transmitted signal
g
• The received signal is often corrupted
p by
y additive
random noise, making signal detection more complicated 2-3-111
Original PowerPoint slides prepared by S. K. Mitra
© The McGraw-Hill Companies, Inc., 2007
 Correlation of Signals (2/4)
• A measure of similarity between a pair of energy signals
signals,
x[n] and y[n], is given by the cross-correlation sequence

• The parameter l called lag, lag indicates the time time-shift

shift
between the pair of signals
• y[
y[n]] iss said
sa d to
o be sshifted
ed by l sa
samples
p es to
o the
e right
g with
respect to the reference sequence x[n] for positive
values of l
• The ordering of the subscripts xy in rxy[l] specifies that
x[n] is the reference sequence which remains fixed in
ti
time while
hil y[n]
[ ] is
i being
b i shifted
hift d with
ith respectt tto x[n]
[ ]
Original PowerPoint slides prepared by S. K. Mitra 2-3-112
© The McGraw-Hill Companies, Inc., 2007
 Correlation of Signals (3/4)
• If y[
y[n]] iss made
ade tthe
e reference
e e e ce ssignal
g a aand
d sshiftt x[n]
[ ] with
t
respect to y[n], then the corresponding cross-correlation
sequence is given by

• The autocorrelation sequence of x[n] is given by

• Note, , the energy of x[n]

• From the relation ryx[l] = rxy[−l] it follows that rxx[l] = rxx[−l],
i l i th
implying thatt rxx[l] is
i an even ffunction
ti for
f reall x[n]
[ ]
Original PowerPoint slides prepared by S. K. Mitra 2-3-113
© The McGraw-Hill Companies, Inc., 2007
 Correlation of Signals (4/4)
• Rewrite the expression for the cross-correlation as

• The cross-correlation of y[n] with the reference signal

x[n] can be computed by processing x[n] with an LTI
discrete time system of impulse response y[−n]
discrete-time y[ n]

• Likewise, the autocorrelation of x[n] can be computed by

processing x[n] with an LTI discrete-time
discrete time system of
impulse response

Original PowerPoint slides prepared by S. K. Mitra 2-3-114

© The McGraw-Hill Companies, Inc., 2007
 Properties of Autocorrelation and
Cross-correlation Sequences (1/3)
• Consider two finite
finite-energy
energy sequences x[n] and y[n]
• The energy of the combined sequence ax[n]+y[n-l] is
also finite and nonnegative,
nonnegative ii.e.,
e

• Thus

where and rxx[0] = Ex > 0 and ryy[0] = Ey > 0

• The above equation can be rewritten as

for any finite value of a

Original PowerPoint slides prepared by S. K. Mitra 2-3-115

© The McGraw-Hill Companies, Inc., 2007
 Properties of Autocorrelation and
Cross-correlation Sequences (2/3)
• The matrix

is thus positive semidefinite

or, equivalently,

• The inequality provides an upper bound for the cross-

correlation samples
p
• If we set y[n] = x[n], then the inequality reduces to
rxx [l ] ≤ rxx [ 0] = Ex
Original PowerPoint slides prepared by S. K. Mitra 2-3-116
© The McGraw-Hill Companies, Inc., 2007
 Properties of Autocorrelation and
Cross-correlation Sequences (3/3)
• Thus
Thus, at zero lag (l = 0)
0), the sample value of the
autocorrelation sequence has its maximum value
• Now
N consider
id th
the case
y[n] = ±b x[n − N]
where
h N is
i an iinteger
t and
d b > 0 iis an arbitrary
bit number
b
• In this case
• Therefore

• Using
U i ththe above
b result:
lt

• We
W gett − br
b xx[0] ≤ rxy[l] ≤ br
b xx[0]
Original PowerPoint slides prepared by S. K. Mitra 2-3-117
© The McGraw-Hill Companies, Inc., 2007
 Computation of Correlations (1/2)
• Example - Consider the two finite
finite-length
length sequences
x[n] = [1 3 −2 1 2 −1 4 4 2], y[n] = [2 −1 4 1 −2 3]

rxy[n] rxx[n]

Original PowerPoint slides prepared by S. K. Mitra 2-3-118

© The McGraw-Hill Companies, Inc., 2007
 Computation of Correlations (2/2)
• Example - The cross-correlation
cross correlation of x[n] and y[n] = x[n −
N] for N = 4
• Note: The peak of the cross
cross-correlation
correlation is precisely the
value of the delay N

rxy[n]
[ ]
Original PowerPoint slides prepared by S. K. Mitra 2-3-119
© The McGraw-Hill Companies, Inc., 2007
 Normalized Forms of Correlation
• Normalized forms of autocorrelation and cross-
correlation are given by

• Note: |ρxx[l]| ≤ 1 and |ρyy[l]| ≤ 1 independent of the range

off values
l off x[n]
[ ] and
d y[n]
[ ]
• The cross-correlation sequence for a pair of power
signals x[n] and y[n],
signals, y[n] is defined as

• The autocorrelation sequence of a power signal x[n] is

given by
Original PowerPoint slides prepared by S. K. Mitra 2-3-120
© The McGraw-Hill Companies, Inc., 2007
 Normalized Forms of Correlation
• The cross-correlation sequence for a pair of periodic
signals of period N, and , is given by

• The autocorrelation sequence of :

• Both and are also periodic with a period N

• Let
L b
be a periodic
i di signal
i l corrupted
dbby the
h random
d
noise d[n] resulting in the signal

which is observed for 0 ≤ n ≤ M −1 where M >> N

Original PowerPoint slides prepared by S. K. Mitra 2-3-121

© The McGraw-Hill Companies, Inc., 2007
 Normalized Forms of Correlation
• The autocorrelation of w[n] is given by

• is a periodic sequence with a period N and hence

will have peaks at l = 0, N, 2N,... with the same
amplitudes as l approaches M
• As and d[n] are not correlated, samples of cross-
correlation sequences and are likely to be
very small relative to the amplitudes of
Original PowerPoint slides prepared by S. K. Mitra 2-3-122
© The McGraw-Hill Companies, Inc., 2007
 Normalized Forms of Correlation
• The autocorrelation rdd [l] of d[n] will show a peak at l = 0
with other samples having rapidly decreasing amplitudes
with increasingg values of ||l||
• Hence, peaks of rww [l] for l > 0 are essentially due to the
peaks of and can be used to determine whether
is a periodic sequence and also its period N if the peaks
occur at periodic intervals

Original PowerPoint slides prepared by S. K. Mitra 2-3-123

© The McGraw-Hill Companies, Inc., 2007
 Normalized Forms of Correlation
• Example - Determine the period of the sinusoidal
sequence x[n] = cos(0.25n), 0 ≤ n ≤ 95 corrupted by an
additive uniformlyy distributed random noise of amplitude
p
in the range [−0.5,0.5]

rww[l] rdd[l]
Original PowerPoint slides prepared by S. K. Mitra 2-3-124
© The McGraw-Hill Companies, Inc., 2007