Chapter 2 Discrete-Time Signals and Systems

```Biomedical Signal processing
Chapter 2 Discrete-Time Signals and
Systems
Zhongguo Liu
Biomedical Engineering
School of Control Science and Engineering, Shandong University
2015/4/13
1
1
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Chapter 2 Discrete-Time Signals and Systems
2.0 Introduction
2.1 Discrete-Time Signals: Sequences
2.2 Discrete-Time Systems
2.3 Linear Time-Invariant (LTI) Systems
2.4 Properties of LTI Systems
2.5 Linear Constant-Coefficient
Difference Equations
2
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Chapter 2 Discrete-Time Signals and Systems
2.6 Frequency-Domain Representation
of Discrete-Time Signals and systems
2.7 Representation of Sequences by
Fourier Transforms
2.8 Symmetry Properties of the
Fourier Transform
2.9 Fourier Transform Theorems
2.10 Discrete-Time Random Signals
2.11 Summary
3
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
2.0 Introduction
Signal: something conveys information
Signals are represented mathematically as
functions of one or more independent variables.
Continuous-time (analog) signals, discretetime signals, digital signals
Signal-processing systems are classified along the
same lines as signals: Continuous-time (analog)
systems, discrete-time systems, digital systems
Discrete-time signal
Sampling a continuous-time signal
Generated directly by some discrete-time process
4
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
2.1 Discrete-Time Signals: Sequences
Discrete-Time signals are represented as
x  xn,    n  , n : integer
Cumbersome, so just use x  n
In sampling,
xn  xa nT , T : sampling period
1/T (reciprocal of T) : sampling frequency
5
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Figure 2.1 Graphical representation
of a discrete-time signal
Abscissa: continuous line
x  n : is defined only at discrete instants
6
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
x[n]  xa (t ) |t nT  xa (nT )
EXAMPLE
7
Sampling the analog waveform
Figure 2.2
Basic Sequence Operations
Sum of two sequences
x[n]  y[n]
Product of two sequences
x[n]  y[n]
Multiplication of a sequence by a numberα
  x[n]
Delay (shift) of a sequence
y[n]  x[n  n0 ]
n0 : integer
8
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Basic sequences
Unit sample sequence
(discrete-time impulse,
impulse)
9
4/13/2015
0 n  0
 n  
1 n  0
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Basic sequences
A sum of scaled, delayed impulses
pn  a3 n  3  a1 n 1  a2 n  2  a7 n  7
arbitrary
sequence
10
4/13/2015
x[n] 

 x[k ] [n  k ]
k  
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Basic sequences
Unit step sequence
u[n] 
n
  k 
k  
1 n  0
u[n]  
0 n  0

 n
0,
when
n

0
    k   1, when n  0 ,
 k 
 since   k   0 k  0
1 k 0



u[n]   [n]   [n  1]   [n  2]      [n  k ]
 [n]  u[n]  u[n  1]
11
4/13/2015





k 0
First backward difference
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Basic Sequences
Exponential sequences
x[n]  A
n
A and α are real: x[n] is real
A is positive and 0<α<1, x[n] is positive and
decrease with increasing n
-1<α<0, x[n] alternate in sign, but decrease
in magnitude with increasing n
   1: x[n] grows in magnitude as n increases
12
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
EX. 2.1 Combining Basic sequences
If we want an exponential sequences that is
zero for n <0, then
 A n n  0
x[n]  
n0
0
x[n]  A u[n]
n
13
4/13/2015
Cumbersome
simpler
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Basic sequences
Sinusoidal sequence
x[n]  A cosw0n   
14
4/13/2015
for all n
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Exponential Sequences
A  Ae
j
 e
j
x[n]  A  A e  e
n
n
jw0 n
jw0
 A e
n
j  w0 n  
 A  cosw0 n     j A  sin w0 n   
n
n
Exponentially weighted sinusoids
 1
 1
 1
Exponentially growing envelope
Exponentially decreasing envelope
x[n]  Ae
jw0 n
is refered to
Complex Exponential Sequences
15
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Frequency difference between
continuous-time and discrete-time
complex exponentials or sinusoids
x[n]  Ae
j  w0  2 n
 Ae
jw0 n
e
j 2n
 Ae
jw0 n
x[n]  A cos  w0  2 r  n     A cos  w0 n   
 w0 : frequency of the complex sinusoid
or complex exponential
  : phase
16
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Periodic Sequences
A periodic sequence with integer period N
x[n]  x[n  N ]
for all n
A cosw0n     A cosw0n  w0 N   
w0 N  2 k , where k is integer
N  2 k / w0 , where k is integer
17
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
EX. 2.2 Examples of Periodic Sequences
x1[n]  cos n / 4
Suppose it is periodic sequence with period N
x1[n]  x1[n  N ]
cos n / 4  cos n  N  / 4
 n / 4  2 k   n / 4  N / 4, k : integer
N  2 k / ( / 4)  8 k
k  1,  N  8  2 / w0
18
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
EX. 2.2 Examples of Periodic Sequences


2
3

x
[
n
]

cos
3

n
/
8
1
8
8
Suppose it is periodic sequence with period N
x1[n]  x1[n  N ]
cos3 n / 8  cos3 n  N  / 8
3 n / 8  2 k  3 n / 8  3N / 8, k : integer
N  2 k / w0  2 k / (3 / 8) k  3,  N  16
N  2 3/ w0  2 / w0 ( for continuous signal)
19
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
EX. 2.2 Non-Periodic Sequences
x2 [n]  cos n
Suppose it is periodic sequence with period N
x2 [n]  x2 [n  N ]
cos n  cos(n  N )
for n  2 k  n  N , k : integer,
there is no integer N
20
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
High and Low Frequencies in Discrete-time signal
x[n]  A cos(w0n)
(a) w0 = 0 or 2
(b) w0 = /8 or 15/8
(c) w0 = /4 or 7/4
(d) w0 = 
21
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
2.2 Discrete-Time System
Discrete-Time System is a trasformation
or operator that maps input sequence
x[n] into a unique y[n]
y[n]=T{x[n]}, x[n], y[n]: discrete-time
signal
x[n]
T{‧}
y[n]
Discrete-Time System
22
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
EX. 2.3 The Ideal Delay System
y[n]  x[n  nd ],    n  
If nd is a positive integer: the delay of the
system. Shift the input sequence to the
right by nd samples to form the output .
If nd is a negative integer: the system will
shift the input to the left by n samples,
d
23
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
EX. 2.4 Moving Average
M2
1
y  n 
x n  k 

M 1  M 2  1 k  M1
1

x  n  M 1   x  n  M 1  1  ...  x  n   x  n  1  ...  x  n  M 2 

M1  M 2  1
for n=7, M1=0, M2=5
dummy index m
x[m]
n-5
n
24
4/13/2015
m
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Properties of Discrete-time systems
2.2.1 Memoryless (memory) system
Memoryless systems:
the output y[n] at every value of n depends
only on the input x[n] at the same value of n
yn  x[n]
2
25
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Properties of Discrete-time systems
2.2.2 Linear Systems
If
x1 n
T{‧}
y1 n
x2 n
T{‧}
y2 n
and only If:
x1n  x2 n
axn
T{‧}
y1n  y2 n additivity property
T{‧}
ayn
homogeneity or scaling

principle of superposition
x3 n  ax1n  bx2 n
26
4/13/2015
T{‧}
y3 n  ay1n  by2 n
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Example of Linear System
Ex. 2.6 Accumulator system
for arbitrary x1n and x2 n
y1 n 
n
y2 n 
 x k 
k  
1
yn 
n
 xk 
k  
n
 x k 
k  
2
when x3 n  ax1n  bx2 n
y3 n 
n
n
 x k    ax k   bx k 
k  
3
1
k  
n
n
k  
k  
2
 a  x1 k   b  x2 k   ay1 n  by2 n
27
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Example 2.7 Nonlinear Systems
Method: find one counterexample
yn  x[n]
 For
2
 counterexample
1 1  1 1
2
2
2
yn  log10  x[n] 
 For
 counterexample
10 log10 1   log10 101 
28
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Properties of Discrete-time systems
2.2.3 Time-Invariant Systems
Shift-Invariant Systems
x1 n
T{‧}
x2 n  x1n  n0 
y1 n
y2 n  y1n  n0 
T{‧}
29
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Example of Time-Invariant System
Ex. 2.8 Accumulator system
n
yn 
 xk 
k  
x1  xn  n0 
y1n 
30
n
n  n0
n
 x k    xk  n    xk   yn  n 
k  
1
4/13/2015
k  
0
k1  
1
0
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Example of Time-varying System
Ex. 2.9 The compressor system
x  n
T{‧}
  n
yn  xMn,    n  
T{‧}
0
x1 n  x n  n0    n 1
0
 2n
0
T{‧}
 2n 1
0
y1n  x1Mn  xMn  n0   yn  n0   xM n  n0 
31
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Properties of Discrete-time systems
2.2.4 Causality
A system is causal if, for every choice
of n 0 , the output sequence value at
the index n  n0 depends only on the
input sequence value for n  n0
32
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Ex. 2.10 Example for Causal System
Forward difference system is not Causal
yn  xn  1  xn
Backward difference system is Causal
yn  xn  xn  1
33
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Properties of Discrete-time systems
2.2.5 Stability
Bounded-Input Bounded-Output (BIBO)
Stability: every bounded input sequence
produces a bounded output sequence.
if
then
34
xn  Bx  ,
for all n
yn  By  ,
for all n
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Ex. 2.11 Test for Stability or Instability
yn  x[n]
2
if
then
35
is stable
xn  Bx  ,
for all n
yn  By  B  ,
2
x
4/13/2015
for all n
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Ex. 2.11 Test for Stability or Instability
Accumulator system
yn 
n
 xk 
k  
0 n  0
xn  un  
:bounded
1 n  0
n0
0
yn   xk    xk   
: notbounded
k  
k  
n  1 n  0
n
n
Accumulator system is not stable
36
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
2.3 Linear Time-Invariant (LTI)
Systems
Impulse response
 n
 n  n0 
37
4/13/2015
T{‧}
T{‧}
h n
h n  n0 
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
LTI Systems: Convolution
Representation of general sequence as a
linear combination of delayed impulse
xn 

 xk  n  k 
k  
principle of superposition
 
 
yn  T   xk  n  k    xk T  n  k 
k  
 k  


 xk hn  k   xn hn
k  
An Illustration Example（interpretation 1）
38
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
39
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Computation of the Convolution
（interpretation 2）
yn 

 xk hn  k 
k  
hn  k   h k  n
h k 
hk 
reflecting h[k] about the origion to obtain h[-k]
Shifting the origin of the reflected sequence to
k=n
40
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Ex. 2.12
41
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Convolution can be realized by
–Reflecting h[k] about the origin to obtain h[-k].
–Shifting the origin of the reflected sequences to k=n.
–Computing the weighted moving average of x[k] by
using the weights given by h[n-k].
42
Ex. 2.13 Analytical Evaluation
of the Convolution
For system with impulse response
1 0  n  N  1
hn  un  un  N   
otherwise
0
input
xn  a un
h(k)
n
0
Find the output at index n
43
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
1 0  n  N  1
hn  
otherwise
0
xn  a un
n
h(-k)
0
0
h(n-k)
h(k)
x(k)
0
y  n  0 n  0
44
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
h(-k)
h(k)
0
0
n  0, n   N 1  0  0  n  N 1
n 1
1

a
yn   xk h k  n   a k 
1 a
k 0
k 0
n
45
4/13/2015
n
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
h(-k)
h(k)
0
0
n   N 1  0  n  N 1
n
yn 
n
 xk h k  n   a
k  n  N 1

46
a
n  N 1
4/13/2015
a
1 a
k
k  n  N 1
n 1
N

n  N 1 1  a

a
 1 a



Zhongguo Liu_Biomedical Engineering_Shandong Univ.

 0,

n 1
1

a

yn  
,
 1 a
N

1

a
 a n  N 1 
 1 a



47
4/13/2015
n0
0  n  N 1

,

N 1  n
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
2.4 Properties of LTI Systems
Convolution is commutative(可交换的)
xn hn  hn xn
x[n]
h[n]
y[n]
h[n]
x[n]
y[n]
xn h1n  h2 n  xn h1n  xn h2 n
48
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
hn  h1n h2 n
x [n]
h1[n]
h2[n]
y [n]
x [n]
h2[n]
h1[n]
y [n]
x [n]
49
4/13/2015
h1[n] ]h2[n]
y [n]
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Parallel connection of systems
hn  h1n  h2 n
50
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Stability of LTI Systems
LTI system is stable if the impulse response

is absolutely summable .
S
 hk   
k  
yn 


k  
k  
 hk xn  k    hk  xn  k 
xn  Bx
y  n  Bx

 h k   
k 
Causality of LTI systems hn  0, n  0
HW: proof, Problem 2.62
51
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Impulse response of LTI systems
Impulse response of Ideal Delay systems
hn   n  nd , nd a positive fixed integer
Impulse response of Accumulator
1, n  0
hn    k   
 un
k  
0, n  0
n
52
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Impulse response of Moving
Average systems
M2
1
hn 
 n  k 

M 1  M 2  1 k  M1
1

,  M1  n  M 2

  M1  M 2  1

0 ,
otherwise
53
4/13/2015
Zhongguo Liu_Biomedical Engineering_Shandong Univ.
Impulse response of Forward Difference
hn   n  1   n
Impulse response of Backward Difference
hn   n   n  1
54
Finite-duration impulse
response (FIR) systems
The impulse response of the system has
only a finite number of nonzero samples.
M2
1
 n  k 
such as: hn 

M 1  M 2  1 k  M1
1

,  M1  n  M 2

  M1  M 2  1

0 ,
otherwise
The FIR systems always are stable.
S
55

 h  n  
n 
Infinite-duration impulse
response (IIR)
The impulse response of the system is
infinite in duration.
1, n  0
hn    k   
 un
k  
0, n  0
n
Stable IIR System:
a 1
hn  a un
n
S

 h  n  
n 
56
Equivalent systems
h  n     n  1    n     n  1
   n  1    n  1    n     n     n  1
57
Inverse system
hn hi n  hi n hn   n
hn  un  n   n  1
 un  un  1   n
58
2.5 Linear Constant-Coefficient
Difference Equations
An important subclass of linear timeinvariant systems consist of those
system for which the input x[n] and
output y[n] satisfy an Nth-order linear
constant-coefficient difference equation.
N
M
 a yn  k    b xn  m
k 0
59
k
m 0
m
Ex. 2.14 Difference Equation
Representation of the Accumulator
y  n 
n
 x k  ,
k 
yn  xn 
y  n  1 
n 1
 x k 
k 
 xk   xn  yn  1
k  
yn  yn  1  xn
60
n 1
Block diagram of a recursive
difference equation representing an
accumulator
61
y n  y n 1  x n
Ex. 2.15 Difference Equation
Representation of the MovingAverage System with M 1  0
M2
1
yn 
xn  k 

M 2  1 k 0
representation 1
1
un  un  M 2  1
hn 
M 2  1
1
 n   n  M 2  1 un
hn 
M 2  1
another representation 1
62
1
 n   n  M 2  1 un
hn 
M 2  1
yn  yn 1  x1n
1
xn  xn  M 2  1
x1 n 
M 2  1
63
1
xn  xn  M 2  1
yn  yn  1 
M 2  1
Difference Equation
Representation of the System
An unlimited number of distinct
difference equations can be used to
represent a given linear time-invariant
input-output relation.
64
Solving the difference equation
information, a linear constantcoefficient difference equation for
discrete-time systems does not provide
a unique specification of the output for
a given input.
N
M
 a yn  k    b xn  m
k 0
65
k
m 0
m
Solving the difference equation
N
M
 a yn  k    b xn  m
k 0
k
m 0
m
Output:
yn  y p n  yh n
 y p n Particular solution: one output sequence
for the given input x p n
 yh n Homogenous solution: solution for
the homogenous equation( x  n  0 ):
N
 ak yh n  k   0
yh n   A z
k 0
 where zm is the roots of
66
N
m 1
N
n
m m
k
a
z
 k 0
k 0
Solving the difference equation
recursively
If the input xn  and a set of auxiliary value
y 1 , y 2 , y N 
are specified.
y(n) can be written in a recurrence formula:
N
M
ak
bk
y  n   y  n  k    x  n  k , n  0,1, 2,3,
k 1 a0
k 1 a0
N 1
M
ak
bk
y  n  N   
y n  k   
x  n  k ,
k  0 aN
k 1 aN
n  N   N  1,  N  2,  N  3,
67
Example 2.16 Recursive Computation of
Difference Equation
y n  ay n 1  x n,
x n  K n ,
y 1  c
y0  ac  K
y1  ay0  0  aac  K   a c  aK
2


y2  ay1  0  a a c  aK  a c  a K
2

3

2
y3  ay2  0  a a c  a K  a c  a K
y n  a c  a K
n1
68
n
3
2
for n  0
4
3
Example 2.16 Recursive Computation of
Difference Equation
yn  ayn 1  xn
yn 1  a
for n  1
y 2  a
xn  K n
1
y1  c
 yn xn
 y1 x1  a c
1
1 1
2
y 3  a  y 2  x 2  a a c  a c
1
1 2
3
y 4  a  y 3  x 3  a a c  a c
1
y n  a c
n1
for n  1
y n  a c  Ka u n
n1
69
1
n
for all n
Example for Recursive Computation
of Difference Equation
y n  a c  Ka u n
n1
n
for all n
The system is noncausal.
yn 1  a 1  yn xn
The system is not linear.
The system is not time invariant.
y n  ay n 1  x n x n  K n  n0  y 1  c
y  n  a c  Ka
n1
70
nn0
u n  n0  for all n
Difference Equation
Representation of the System
If a system is characterized by a linear
constant-coefficient difference equation and
is further specified to be linear, time
invariant, and causal, the solution is unique.
In this case, the auxiliary conditions are
stated as initial-rest conditions(初始松弛条件).
The auxiliary information is that if the input
xn  is zero for n  n0 ,then the output, yn
is constrained to be zero for n  n0
71
Summary
The system for which the input and
output satisfy a linear constantcoefficient difference equation:
The output for a given input is not
uniquely specified. Auxiliary conditions
are required.
72
Summary
If the auxiliary conditions are in the form
of N sequential values of the output,
y 1, y 2,
, y N 
later value can be obtained by
rearranging the difference equation as a
recursive relation running forward in n,
N
M
ak
bk
y  n   y  n  k    x  n  k , n  0,1, 2,3,
k 1 a0
k 1 a0
73
Summary
and prior values can be obtained by
rearranging the difference equation as a
recursive relation running backward in n.
N 1
M
ak
bk
y  n  N   
y n  k   
x  n  k ,
k  0 aN
k 1 aN
n  N   N  1,  N  2,  N  3,
74
Summary
Linearity, time invariance, and
causality of the system will depend on
the auxiliary conditions.
If an additional condition is that the
system is initially at rest, then the
system will be linear, time invariant,
and causal.
75
Example 2.16 with initial-rest conditions
y n  ay n 1  x n
since x n  0, n  0
x n  K n
y 1  0
y n  Ka u n
n
If the input is K n  n0  , again with initialrest conditions, then the recursive solution
is carried out using the initial condition
yn  0, n  n0
y n  Ka
76
nn0
u n  n0 
Discussion
If the input is K n  n0  , with initial-rest
conditions,
yn  0, n  n0
y n  Ka
nn0
u n  n0 
Note that for n0  0 , initial rest implies
that y 1  0
Initial rest does not always means
y 1 
 y N   0
It does mean that yn0 1    yn0  N   0
if xn  0, n  n0 .
77
2.6 Frequency-Domain
Representation of DiscreteTime Signals and systems
2.6.1 Eigenfunction and Eigenvalue for LTI
If
yn  T xn  H xn xn
 xn  is called as the eigenfunction of the
 , and the associated
system T 
eigenvalue is H xn
78
Eigenfunction and Eigenvalue
Complex exponentials is the eigenfunction
for discrete-time systems. For LTI systems:
x  n  e
jwn
,   n  
y  n  h  n  x  n 


h k e

k 

 h k  x n  k 
k 
jw n  k 
 jw  jwn
 H e e


eigenvalue
79
 
 jwk  jwn
   h k e
e
 k 

eigenfunction
frequency response
Frequency response
 
 jw  jwn
 jwk  jwn
y  n    h  k  e
 H e e
e


 k 

 
 H e
is called as frequency response of
the system.
jw
Real part, imagine part
H e
jw
  H  e   jH  e 
jw
R
I
Magnitude, phase
H e
80
jw
jw
  H e  e
jw
 
jH e jw
Example 2.17 Frequency
response of the ideal Delay
jwn
yn  xn  nd 
x  n  e
jwnnd 
 jwnd jwn
yn  e
e
H e
e
jw
e
 jwnd
From defination(2.109):
H e

jw

81
   h  n e

 jwn
n 
  n  n  e
n 
d
 jwn
h n   n  nd 
 jwnd
e
Example 2.17 Frequency
response of the ideal Delay
H e
jw
e
 jwnd
 cos  wnd   j sin  wnd 
 H R e
 1e
82
 jwnd
  jH  e 
 H e  e
jw
jw
I
jw
 
jH e jw
Linear combination of
complex exponential
xn   k e
jwk n
k
 e
y  n  k H e
k
83
jwk
jwk n
Example 2.18 Sinusoidal
response of LTI systems
A j jw0n A  j  jw0n
x  n   A cos  w0 n     e e
 e e
2
2
y  n  H
e 
jw0
A j jw0n
e e H
2

if h  n  is real , H e


 jw0
e 
 jw0
A  j  jw0n
e e
2
  H e 
*
jw0

y  n  A H e jw0 cos  w0 n      ,   H e jw0
84

Sinusoidal response of the
ideal Delay
jw
jw
y  n  A H  e  cos  w0 n      ,   H  e
0
0
x n  A cos  w0n   
   1,
He
jw
H e
jw
e
   w0 nd
y  n  A cos  w0 n    w0 nd 
 A cos  w0  n  nd    
85

 jwnd
Periodic Frequency Response
The frequency response of discrete-time
LTI systems is always a periodic function of
the frequency variable w with period 2

H e
e
j  w 2 
j  w 2 

H e
86

H e
   h  n e

 j  w 2  n
n 
e
e
  H e 

  H e  ,
j  w 2 
j  w 2 r
 jwn  j 2 n
e
 jwn
jw
jw
for r an integer
Periodic Frequency Response
 
We need only specify H e jw over 0  w  2
or    w  
The “low frequencies” are frequencies
close to zero
The “high frequencies” are frequencies
close to  
More generally, modify the frequency with
2 r , r is integer.
87
Example 2.19 Ideal
Frequency-Selective Filters
Frequency Response of Ideal Low-pass Filter
88
Frequency Response of Ideal
High-pass Filter
89
Frequency Response of Ideal
Band-stop Filter
90
Frequency Response of Ideal
Band-pass Filter
91
Example 2.20 Frequency Response of
the Moving-Average System
1

,  M1  n  M 2

hn   M 1  M 2  1

0,
otherwise
M2
1
H e  

M 1  M 2  1 n M
jw
e
 jwn
1
1
e

M1  M 2  1
92
jwM1
 jw M 2 1
e
 jw
1 e
H e


jw
  M1M 2 1
1
e
1
jw  M1 M 2 1
2
M1 M 2 1
M1 M 2 1
e
jw  M1 M 2 1
2
e
 jw M 2 1
e
 jw
1 e
 jw  M1 M 2 1
1 e
e
1
e
jwM1
jw 2
2
 jw
e
e
e
 jw  M1 M 2 1
2
 jw 2
 jw  M 2  M11
2
e
 jw  M 2  M1 
2
sin  w  M 1  M 2  1 2   jw M 2  M1 

e
M1 M 2 1
sin  w 2 
93
1
2
Frequency Response of the MovingAverage System
sin  w  M 1  M 2  1 2   jw M 2  M1 
H e  
e
M1 M 2 1
sin  w 2 
jw
1

M1 = 0 and M2 = 4
4
5
94
2
 4
5
2.6.2 Suddenly applied Complex
Exponential Inputs
In practice, we may not apply the complex
exponential inputs ejwn to a system, but the
more practical-appearing inputs of the form
x[n] = ejwn  u[n]
i.e., x[n] suddenly applied at an arbitrary time,
which for convenience we choose n=0.
For causal LTI system:
y n  0, n  0
95
for x n  0, n  0
2.6.2 Suddenly applied Complex
Exponential Inputs
jwn
For causal LTI system
xn  e un
n0
 0,
 n
yn  xn hn  
 jwk  jwn
  hk e
e , n  0
 k 0


For n≥0


 jwk  jwn
 jwk  jwn
y  n    h  k  e
 e    h k  e
e
 k 0

 k n1


 H e
96
jw
e


 jwk  jwn
   h k  e
 e  yss  n  yt  n
 k n1


jwn
2.6.2 Suddenly applied Complex
Exponential Inputs
yss  n  H  e
jw
e

jwn
  h k  e
k 0
Transient response

yt n    hk e
k  n 1
97
 jwk
e
jwn
 jwk
e
jwn
2.6.2 Suddenly Applied Complex
Exponential Inputs (continue)
For infinite-duration impulse response (IIR)
yt  n 

 h k  e
k  n 1
 jwk
e
jwn



k  n 1
k 0
 h k    h k 
For stable system, transient response must
become increasingly smaller as n  ,
Illustration of a real part of suddenly applied complex
exponential Input with IIR
98
2.6.2 Suddenly Applied Complex
Exponential Inputs (continue)
If h[n] = 0 except for 0 n  M (FIR), then the
transient response yt[n] = 0 for n+1 > M.
For n  M, only the steady-state response
exists
Illustration of a real part of suddenly applied complex
exponential Input with FIR
99
2.7 Representation of Sequences
by Fourier Transforms
(Discrete-Time) Fourier Transform, DTFT，

analyzing
 jwn
 jw 
   x  n e
 n
X e


If xn  is absolutely summable, i.e. x  n   
n 
then X e jw exists. (Stability)
 
Inverse Fourier Transform, synthesis
1
xn 
2
100
  X e e


jw
jwn
dw
Fourier Transform
   X e  jX e   X e e
X e
jw
jw
R
jw
 
jX e jw
I
rectangular form
  : Fouriertransform,
Xe
jw
polar form
jw
Fourier spectrum, spectrum
X e
jw
 : magnitude, magnitude spectrum,
amplitude spectrum
 : phase, phasespectrum
X e
101
jw
Principal Value（主值）
 
 X e is not unique because any 2 r
jw
may be added to X e
without affecting
the result of the complex exponentiation.
jw
e
 
 
jX e jw
 
jw

X
e
Principle value:
is restricted to the
range of values between   and  . It is
jw

denoted as ARG  X  e  
jw

 arg  X  e : phase function is referred as a
continuous function of
102
w
for 0  w  
Impulse response and
Frequency response
The frequency response of a LTI
system is the Fourier transform of the
impulse response.
H e

jw
   h  n e
1
hn 
2
103
 jwn
n 



 e
He
jw
jwn
dw
Example 2.21: Absolute Summability
xn  a un
Let
n
The Fourier transform
X e

jw
  a e
n  jwn
n 0
 jw n+1

   ae
n 0
1 （ae ）
1
 lim


jw
 jw
n 
1  ae
1  ae

104
 jw
if ae
1
or if a  1
1
a 
 , if a  1

1 a
n 0
n

 jw n
Discussion of convergence
Absolute summability is a sufficient
condition for the existence of a Fourier
transform representation, and it also
guarantees uniform convergence.
Some sequences are not absolutely
summable, but are square summable,
i.e.,

2
 x  n  
n 
105
Discussion of convergence
Sequences which are square
summable, can be represented by a
Fourier transform, if we are willing to
relax the condition of uniform
convergence of the infinite sum
defining X e jw .
 
Is called Mean-square Cconvergence
106
Discussion of convergence
Mean-square convergence
    xne

X e
jw
 jwn
n  
lim


M  
    xne
M
XM e
jw
 jwn
n M
  X e  dw  0
Xe
jw 2
jw
 
M
 
The error X e  X M e
may not approach
zero at each value of w as M   , but
total “energy” in the error does.
jw
107
jw
Example 2.22 : Square-summability
for the ideal Lowpass Filter
 1,
w  wc
H lp e  
0, wc  w  
1 wc jwn
1  jwn  wc
hlp  n 
e
dw 
e

  wc
2  wc
2 jn 
 
jw

e

2 jn
1
jwc n
 jwc n
e

sin wc n

,   n  
n
Since hlp n is nonzero for n  0 , the ideal
lowpass filter is noncausal.
108
Example 2.22 Square-summability
for the ideal Lowpass Filter
sin wc n
hlp  n  
approaches zero as n  ,
n
but only as 1 n .
 hlp n is not absolutely summable.

sin wc n  jwn does not converge
e

uniformly for all w.
n
n  
  
Define H M e
109
M
jw
n M
sin wc n  jwn
e
n
Gibbs Phenomenon
HM e
110
jw

1

2
sin[( 2M+1) ( w   ) / 2]
wc sin[( w   ) / 2] d
wc
M=1
M=3
M=7
M=19
Example 2.22 continued
As M increases, oscillatory behavior at
w  wc is more rapid, but the size of
the ripple does not decrease. (Gibbs
Phenomenon)
As M   , the maximum amplitude of
the oscillation does not approach zero,
but the oscillations converge in location
toward the point w  w .
c
111
Example 2.22 continued

sin wc n  jwn
e

does not converge uniformly
n
n  
jw
to the discontinuous function Hlp e
.
 
However, hlp n is square summable,
and H M e jw  converges in the meansquare sense to Hlp e jw 

  H e  dw  0
lim  Hlp e
M  
112
jw
jw
M
2
Example 2.23 Fourier Transform
of a constant
xn  1 for all n
The sequence is neither absolutely summable
nor square summable.

The Fourier transform of x n
is
    2  w  2 r 

X e
jw
r  
The impulses are functions of a continuous
variable and therefore are of “infinite height,
zero width, and unit area.”
113
Example 2.23 Fourier Transform
of a constant: proof
1 
jw
jwn
x  n 
X  e  e dw

2 
1   
 jwn

2   w  2 r   e dw



2   r 


jwn 
      w  2 r  e  dw

 r 




    w e

114
jwn
dw  e
j 0n



  w dw  1
Example 2.24 Fourier Transform of
Complex Exponential Sequences
xn  e
jw0 n
    2  w  w

X e
jw
0
r  
1
x  n 
2
1

2



X  e jw  e jwn dw
 
 jwn
2   w  w0  2 r   e dw
  r



    w  w0  e

115

 2 r 
jwn
dw  e
jw0 n
Example: Fourier Transform of
Complex Exponential Sequences
xn   ak e
jwk n
,   n  
k
    2 a  w  w

X e
jw
r   k
116
k
k
 2 r 
Example: Fourier Transform
of unit step sequence
xn  un
 
Ue
117
jw

1






w

2

r

 jw
1 e
r  
2.8 Symmetry Properties of the
Fourier Transform
Conjugate-symmetric sequence
xe n  x  n

e
Conjugate-antisymmetric sequence
xo n   x  n

o
xn  xe n  xo n
118
1


xe  n    x  n   x  n   xe  n 
2
1
xo n  xn  x   n   xo  n
2
Symmetry Properties of real sequence
even sequence: a real sequence that is
Conjugate-symmetric x n  x  n
e
e
odd sequence: real, Conjugate-antisymmetric
xo n   xo  n
real sequence: xn  xe n  xo n
119
1
xe n   xn  x n  xe  n
2
1
xo n  xn  x n   xo  n
2
Decomposition of a Fourier
transform
   X e  X e 
Xe
jw
jw
e
Conjugate-symmetric
o
Conjugate-antisymmetric
  
 
  
 
 
1
jw
  jw
  jw
 X e X e
 Xe e
2
 
1
jw
  jw
  jw
 X e X e
 Xo e
2
Xe e
Xo e
120
jw
jw
jw
 
 
 
xn  X e
x[n] is complex
 
x n  X e


jw
 
x  n  X e

 jw

jw
     
j Imxn  X e 
1
1

xe  n   x  n  x  n X  e    X  e   X  e 
2
2
1
jw 1 
jw
  jw 

Re  x  n   x  n  x  n  X e e   X e  X e 
2
2
jw
o

jw
jw
R
   j ImX e 
xo n  jX I e
121
jw
jw
jw
x[n] is real
x  n  x  n  X  e

X R  e   jX I  e
jw
X R e
jw
  X e 
 jw
R
   X e 
X e
jw
xe n  X R
122
jw
 X
  X e 
 e   jX e 

jw
 jw
 jw
R
 jw
I
    X e 
XI e
 jw
jw
I
   X e 
e  x n  jX e 
 jw
X e
 jw
jw
jw
jw
o
I
Ex. 2.25 illustration of Symmetry Properties
1
jw
n
X e 
if a  1
xn  a un
 jw
1  ae
 
1
  jw
X e  
 X e 
 jw
1  ae
1  a cos w
jw
 jw
XR e 

X
e
R
2
1  a  2a cos w
jw
 
 
XI e
jw
 
 a sin w
 jw



X
e
I
2
1  a  2a cos w
 
Xe
jw
 
X e
123
jw
 
1  a
1
2

 2a cos w
12
 
 X e jw
  a sin w 
   X e  jw
 tan 
 1  a cos w 
1
 
Ex. 2.25 illustration of Symmetry Properties
Real part
1  a cos w
1  a 2  2a cos w
Imaginary part
a sin w
1  a 2  2a cos w
a=0.75(solid curve) and a=0.5(dashed curve)
124
Ex. 2.25 illustration of Symmetry Properties
Its magnitude is an even function, and phase is
odd.
X e
125
jw


1  a
1
2
 2a cos w 
12
 a sin w 
X  e   tan 

 1  a cos w 
jw
1
a=0.75(solid curve) and a=0.5(dashed curve)
2.9 Fourier Transform Theorems
X e
jw
  F {x[n]}
x[n]  F { X  e
1
x[n] 
 X e
F
jw
jw
}

2.9.1 Linearity
x1  n 
F
 X 1
e 
ax1  n  bx2  n 
126
jw
x2  n 
F
 aX 1
F
 X 2
e 
jw
 e   bX  e 
jw
jw
2
Fourier Transform Theorems
2.9.2 Time shifting and frequency shifting
 
xn  X e
x  n  nd   e
e
127
jw0 n
jw
 jwnd

xn  X e
jw
X e

j  w w0 

Fourier Transform Theorems
2.9.3 Time reversal
 
x n  X e 
xn  X e
jw
 jw
If xn  is real,
 
x n  X e

jw
e   X e 
x  n  x  n  X  e   X  e 
x  n  x  n   X


128

 jw
jw
jw

 jw
Fourier Transform Theorems
2.9.4 Differentiation in Frequency
 
jw
dX e
nxn  j
dw
x  n  X  e
j
dX  e
129
dw
jw
 j

jw

 jwn
   x  n e
n
 jwn
de
 x n dw
n


 jwn
 nx ne
n
Fourier Transform Theorems
2.9.5 Parseval’s Theorem
E

 xn
2
n  
 X e
1

2
 
xn  X e
  X e 

jw 2


jw 2
jw
dw
is called the energy density spectrum


1 

jw
jwn

E   x  n  x  n    [  X e e dw]x  n 

2

n 
n 

1 
jw

jwn

X e  x  ne dw

jw

X
e
 
2 
n 
 
 
130
Fourier Transform Theorems
2.9.6 Convolution Theorem
  hn  H e 
xn  X e
if y  n 
jw
jw

 x  k  h  n  k   x  n  h  n
k 
   X e H e 
Ye
131
jw
jw
jw
HW: proof
Fourier Transform Theorems
2.9.7 Modulation or Windowing Theorem
 
xn  X e
jw
 
wn  W e
jw
yn  xn wn
 
Ye
jw
1

2
  X e W e


j
j  w  
d
HW: proof
132
Fourier transform pairs
 n  1
 n  n0   e
 jwn0

1
   n     2  w  2 k 
k  
a u  n
n
1
 a  1  1  ae jw

1
u  n 
     w  2 k 
 jw
1 e
k 
 n  1 a u  n  a
n
133
 1 
1
1  ae 
 jw 2
Fourier transform pairs
r sin w p n  1
n
sin w p
un
1
 r  1 
 jw
2  j 2w


1  2r cos w p e  r e

jw
jw
1
e
e
(re )


jwp
 jwp
jwp  jw
 jwp  jw

r (e  e ) 1  re e
1  re e

 1,
w  wc
sin wc n
jw
 X e   
n
0 , wc  w  
jwp n 1

 


sin  w  M  1 2  jwM
1, 0  n  M
x  n  

e
0,
otherwise
sin
w
2




134




2
Fourier transform pairs
e
jw0n


 2   w  w
0
k 
1 jw0n j
cos  w0 n     (e
2

  e   w  w  2 k    e
k 
135
j
0

 j
 2 k 
e
 jw0n  j
)
  w  w0  2 k 
Ex. 2.26 Determine the Fourier Transform
of sequence
xn  a un  5
n
 
x1 n  a un  X 1 e
n
x2 n  x1 n  5  a
 
jw
1

 jw
1  ae
un  5
 n 5 
 
 j 5w
e
 X2 e  e
X1 e 
 jw
1  ae
5  j 5w
ae
5
jw
5
jw
xn  a x2 n  X e   a X 2 e  
 jw
1  ae
jw
136
 j 5w
jw
Ex. 2.27 Determine an inverse Fourier
1
Transform of X e jw 
 jw
 jw
1  ae 1  be
  

a a  b  b a  b 


 jw
 jw
1  ae
1  be
  
X e
jw

 

 a  n
 b  n
xn  
a un  
b un
 a b 
 a b 
137
Ex. 2.28 Determine the impulse response
from the frequency respone:

0,
w

w
c

jw
H hp e    jwn
d , w  w 
e

c

 

 1,
H lp  e   

0,
jw
Hhp  e
jw
e
 jwnd
w  wc
wc  w  
1 H e   e
jw
lp
 jwnd
 jwnd
e
Hlp  e
jw

sin wc  n  nd 
hhp  n    n  nd   hlp n  nd    n  nd  
  n  nd 
138
Ex. 2.29 Determine the impulse response
for a difference equation:
1
1
yn  yn  1  xn  xn  1
2
4
xn   n
Impulse response
1
1
hn  hn  1   n   n  1
2
4
 
He
jw
 
1  jw
1  jw
jw
 e H e  1 e
2
4
 jw
 jw
1
1
1 e
e
1
jw
4
H e  

 4
 jw
 jw
 jw
1
1
1
1 e
1 e
1 e
2
2
2
139
Ex. 2.29 Determine the impulse response
for a difference equation:
1
H e  
 jw
1
1 e
2
jw
 
n
1 u  n
2
n
1 e jw
4

 jw
1
1 e
2
  
 1
4
1
2
n 1
n 1
u  n  1
1
 1  1 
hn    un     un  1
2
 4  2 
140
2.10 Discrete-Time Random Signals
Deterministic: each value of a sequence is
uniquely determined by a mathematically
expression, a table of data, or a rule of
some type.
Stochastic signal: a member of an
ensemble of discrete-time signals that is
characterized by a set of probability density
function.
141
2.10 Discrete-Time Random Signals
For a particular signal at a particular time,
the amplitude of the signal sample at that
time is assumed to have been determined
by an underlying scheme of probability.
That is, xn  is an outcome of some
random variable x n
142
2.10 Discrete-Time Random
Signals
 xn  is an outcome of some random variable
x n ( not distinguished in notation).
The collection of random variables is called a
random process.
 The stochastic signals do not directly have
Fourier transform, but the Fourier transform
of the autocorrelation and autocovariance
sequece often exist.
143
Fourier transform in stochastic signals
The Fourier transform of autocovariance
sequence has a useful interpretation in
terms of the frequency distribution of
the power in the signal.
The effect of processing stochastic
signals with a discrete-time LTI system
can be described in terms of the effect
of the system on the autocovariance
sequence.
144
Stochastic signal as input
Let xn  be a real-valued sequence that is a
sample sequence of a wide-sense stationary
discrete-time random process.
xn 
yn 
145
hn 
yn


k  
k  
 hn  k xk    hnxn  k 
Stochastic signal as input
In our discussion, no necessary to distinguish
between the random variables Xn andYn and
their specific values x[n] and y[n].
mXn = E{xn }, mYn= E(Yn}, can be written as
mx[n] = E{x[n]}, my[n] =E(y[n]}.
The mean of output process
my  E  y  n  
 mx
146

 h k  E x n  k 
k 

 h k   H e  m
j0
k 
x
Stochastic signal as input
The autocorrelation function of output
 yy  m   E  y  n  y  n  m 
  

 E    h  k  h  r  x  n  k  x n  m  r 
k  r 





  h  k  h  r   m  ( r  k )      m  l  c l 
k  r 
l  
where
xx
lk
chh l  
l 

xx
l
 h  k  h l  k 
k 
hh
 chh n is called a deterministic autocorrelation
sequence or autocorrelation sequence of hn 
147
Stochastic signal as input

 yy  m   E  y  n  y  n  m     xx  m  l  chh l 
l 

where
c l    h  k  h l  k 
hh
k 
   C e  e 
 yy e
jw
jw
jw
hh
xx
   H e H e   H e 
the power
 e   H e   e 
spectrum
Chh e
jw
jw
yy

jw
jw
jw 2
jw
2
jw
xx
DTFT of the autocorrelation function of output
148
Total average power in output
 yy  e
jw
  H e
jw

2
 xx  e jw 
provides the motivation for the term
power density spectrum.
1 
2
jw
jw0
E y  n    yy  0 

e
dw
e
yy

2 
2
能量
1 
jw
jw

H
e

e
dw
xx

2 
 total average power in output


 
 
能量有限
Parseval’s E
Theorem
149


 xn
n  
2
1

2
 
  X e 


jw 2
dw
For Ideal bandpass system
jw

m


Since xx
is a real, even, its FT  xx  e  is
   e 
so is  e   H e   e 
1
1
0     e  dw     e  dw
2
2
also real and even, i.e.,
 xx  e
jw 2
jw
能量

xx
jw
yy
 yy
 jw
jw
xx
b
a
b
jw
xx
lim  yy 0  0
(b a ) 0
 xx  e
jw
a
0
jw
xx
for all w
 the power density function of a real signal is
150 real, even, and nonnegative.
Ex. 2.30 White Noise
A white-noise signal is a signal for which
xx m   x2 m
Assume the signal has zero mean. The
power spectrum of a white noise is
 xx  e

jw
     m e
m 
xx
 jwm

2
x
for all w
The average power of a white noise is
1
 xx  0 
2
151
1
  xx  e  dw  2

jw

 

2
x
dw  
2
x
Color Noise
A noise signal whose power spectrum is
not constant with frequency.
A noise signal with power spectrum  yy e jw 
can be assumed to be the output of a LTI
system with white-noise input.
   H e  
 yy e
152
jw
jw 2
2
x
Color Noise
Suppose h  n  anu n
,
1
H e  
 jw
1  ae
jw
 yy  e
jw
  H e 
jw

153
2

2
1
2
 

x
 jw
1  ae
2
x
2
x
1  a  2a cos w
2
Cross-correlation between the
input and output
 xy  m  E  x  n  y  n  m 



 E  x  n   h  k  x  n  m  k 
k 




 h  k   m  k 
k 
xx
 h  k    xx  k 
   H e  e 
xy e
154
jw
jw
jw
xx
Cross-correlation between
the input and output
2
If xx m   x  m
,
 xy  m  h  k    xx  k  

 h  k    m  k    h  m 
k 
2
x
2
x
That is, for a zero mean white-noise input,
the cross-correlation between input and
output of a LTI system is proportional to
the impulse response of the system.
155
Cross power spectrum between
the input and output
    ,   w  
 e    H e 
 xx e
jw
jw
xy
2
x
2
x
jw
The cross power spectrum is proportional
to the frequency response of the system.
156
2.11 Summary
Define a set of basic sequence.
Define and represent the LTI systems
in terms of the convolution, stability and
causality.
Introduce the linear constant-coefficient
difference equation with initial rest
conditions for LTI , causal system.
Recursive solution of linear constantcoefficient difference equations.
157
2.11 Summary
Define FIR and IIR systems
Define frequency response of the LTI
system.
Define Fourier transform.
Introduce the properties and theorems
of Fourier transform. (Symmetry)
Introduce the discrete-time random
signals.
158
Chapter 2 HW
2.1, 2.2, 2.4, 2.5,
2.7, 2.11, 2.12,2.15,
2.20, 2.62,
159

Zhongguo Liu_Biomedical Engineering_Shandong Univ.

```