CHAPTER 1:

INTRODUCTION

Lesson #1: A big picture about Digital Signal Processing

Lesson #2: Analog-to-Digital and Digital-to-Analog conversion
Lesson #3: The concept of frequency in CT & DT signals
Duration: 6 hrs

References: Joyce Van de Vegte, “Fundamentals of Digital Signal Processing,” Chap. 1, 2

John G. Proakis, Dimitris G. Manolakis, “Digital Signal Processing,” Chap. 1
 Lecture 1: A big picture about
Digital Signal Processing

 Duration: 2 hr
 Outline:
1. Signals
2. Digital Signal Processing (DSP)
3. Why DSP?
4. DSP applications
*******
Learning Digital Signal Processing is not something you accomplish; it’s a journey
you take.
R.G. Lyons, Understanding Digital Signal Processing
 Signals

 Function of independent variables such as time, distance,

position, temperature
 Convey information
 Examples:
1D signal: speech, music, biosensor…
2D signal: image
2.5D signal: video (2D image + time)
3D signal: animated
 1-D signals
EEG

ECG

Speech signal
Color image
 2-D image signals

Binary image Grey image Color image

2.5-D video signals
3-D animated signals
Lecture 1: A big picture about
Digital Signal Processing

 Duration: 2 hr
 Outline:
1. Signals
2. Digital Signal Processing (DSP)
3. Why DSP?
4. DSP applications
 Discrete-time signal vs.
continuous-time signal

 Continuous-time signal:
- define for a continuous duration of time
- sound, voice…
 Discrete-time signal:
- define only for discrete points in time (hourly, every
second, …)
- an image in computer, a MP3 music file
- amplitude could be discrete or continuous
- if the amplitude is also discrete, the signal is digital.
 Analog signal vs. digital signal

00 10 00 10 11

Analog signal Digital signal

 What is Digital Signal Processing?

 Represent a signal by a sequence of numbers (called a

"discrete-time signal” or "digital signal").
 Modify this sequence of numbers by a computing process
to change or extract information from the original signal
 The "computing process" is a system that converts one
digital signal into another— it is a "discrete-time system” or
"digital system“.
 Transforms are tools using in computing process
 Signal processing systems

Analog signal Analog signal

x(t) Processing y(t)

Analog signal processing

Analog signal Analog signal

x(t) y(t)
A/D Processing D/A

Digital signal processing

 Digital Signal Processing
implementation

Performed by:
 Special-purpose (custom) chips: application-specific integrated
circuits (ASIC)
 Field-programmable gate arrays (FPGA)
 General-purpose microprocessors or microcontrollers (μP/μC)
 General-purpose digital signal processors (DSP processors)
 DSP processors with application-specific hardware (HW)
accelerators
Digital Signal Processing
implementation
 Digital Signal Processing
implementation

 Use basic operations of addition,

multiplication and delay
 Combine these operations to accomplish
processing: a discrete-time input signal 
another discrete-time output signal
 An example of main step:
“DT signal processing”

 From a discrete-time input signal:

{ 1 2 4 -9 5 3 }
 Create a discrete-time output signal:
{ 1/3 1 7/3 -1 0 -1/3 8/3 1 }
What is the relation between input and output signal?
 Two main categories of DSP

Digital Signals

- feature extraction - noise removal

- signal recognition - interference
- signal modeling removal
........ ……
Analysis Filtering

Measurement Digital Signals

Lecture 1: A big picture about
Digital Signal Processing

 Duration: 2 hr
 Outline:
1. Signals
2. Digital Signal Processing (DSP)
3. Why DSP?
4. DSP applications
 Advantages of Digital Signal
Processing

 Flexible: re-programming ability

 More reliable
 Smaller, lighter  less power
 Easy to use, to develop and test (by using the
assistant tools)
 Suitable to sophisticated applications
 Suitable to remote-control applications
 Limitations of Digital Signal
Processing

 A/D and D/A needed  aliasing error and

quantization error
 Not suitable to high-frequency signal
 Require high technology

Mixed Signal Processing

Lecture 1: A big picture about
Digital Signal Processing

 Duration: 2 hr
 Outline:
1. Signals
2. Digital Signal Processing (DSP)
3. Why DSP?
4. DSP applications
Radar
 Biomedical

 Analysis of biomedical signals, diagnosis, patient

monitoring, preventive health care
Speech compression
Speech
recognition
 Communication

Digital telephony: transmission of information in

digital form via telephone lines, modern technology,
mobile phone
 Image processing

Image enhancement: processing an image to be more

suitable than the original image for a specific application

It makes all the difference whether one sees darkness through

the light or brightness through the shadows
David Lindsay
 Image processing
Image compression: reducing the redundancy in the
image data

UW Campus (bmp) 180 kb UW Campus (jpg) 13 kb

 Image processing

Image restoration: reconstruct a degraded image using a

priori knowledge of the degradation phenomenon
 Music

Recording, encoding, storing

Playback
Manipulation/mixing
Finger print recognition
Noise removal
Lecture 2: Analog-to-Digital and
Digital-to-Analog conversion

 Duration: 2 hr
 Outline:
1. A/D conversion
2. D/A conversion
ADC
 Sampling

 Continuous-time signal  discrete-time signal

Analog Digital
Sampling
world world
 Sampling

 Taking samples at intervals and don’t know what happens in

between  can’t distinguish higher and lower frequencies:
aliasing
 How to avoid aliasing?
 Nyquist sampling theory

 To guarantee that an analog signal can be perfectly

recovered from its sample value
 Theory: a signal with maximum of frequency of W Hz must
be sampled at least 2W times per second to make it possible
to reconstruct the original signal from the samples
 Nyquist sampling rate: minimum sampling frequency
 Nyquist frequency: half the sampling rate
 Nyquist range: 0 to Nyquist frequency range
 To remove all signal elements above the Nyquist frequency
 antialiasing filter
magnitude Anti-aliasing filter

Anti-aliasing Analog signal

filter response spectrum

frequency

0 W 2W =fs 3W 4W
magnitude

Filtered analog signal

spectrum

frequency

0 W 2W =fs 3W 4W
 Some examples of sampling frequency

 Speech coding/compression ITU G.711, G.729, G.723.1:

fs = 8 kHz  T = 1/8000 s = 125μs
 Broadband system ITU-T G.722:
fs = 16 kHz  T = 1/16 000 s = 62.5μs
 Audio CDs:
fs = 44.1 kHz  T = 1/44100 s = 22.676μs
 Audio hi-fi, e.g., MPEG-2 (moving picture experts group),
AAC (advanced audio coding), MP3 (MPEG layer 3):
fs = 48 kHz T = 1/48 000 s = 20.833μs
 Sampling and Hold

 Sampling interval Ts (sampling period): time between samples

 Sampling frequency fs (sampling rate): # samples per second

0 1 2 3 4

Analog signal Sample-and-hold signal

 Quantization

 Continuous-amplitude signal  discrete-amplitude signal

Quantization step
 Coding
 Quantized sample  N-bit code word

1.5V
1.1V
1.25V
1.0V

0.82V
0.5V

0.0V
 Example of quantization and coding

Analog pressures Range of

Quantization
are recorded, analog
using a pressure Digital code Level (V) inputs (V)

transducer, as 000 0.0 0.0-0.1875

voltages between
001
0 and 3V. The
signal must be 010
quantized using a 011
3-bit digital code.
100
Indicate how the
analog voltages 101
will be converted 110
to digital values.
111
 Example of quantization and coding

Quantization
An analog voltage Range of analog
Digital code Level (V) inputs (V)
between -5V and 5V
100 -5.0 -5.0 -4.375
must be quantized
101
using 3 bits. Quantize
110
each of the following
111
samples, and record
000
the quantization error
001
for each:
010
-3.4V; 0V; .625V
011
 Quantization parameters

 Number of bits: N
 Full scale analog range: R
 Resolution: the gap between levels Q = R/2N
 Quantization error = quantized value – actual value
 Dynamic range: number of levels, in decibel
Dynamic range = 20log(R/Q) = 20log(2N) = 6.02N dB
 Signal-to-noise ratio SNR = 10log(signal power/noise power)
Or SNR = 20log(signal amplitude/noise amplitude)
 Bit rate: the rate at which bits are generated
Bit rate = N.fs
 Noise removal by quantization

Error
Noise

Q/2
Q

Quantized signal + noise After re-quantization

 Non-uniform quantization

 Quantization with variable quantization step  Q value is

variable
Output Non-
 Q value is directly uniform
proportional to signal
amplitude  SNR is
constant Uniform

 Most used in speech Input

 A-law compression curve

 A s (t ) 1
 1 , 0  s1 ( t ) 

s 2 ( t )  1  ln A A
1  ln(A s1 ( t ) ) s2(t)
1
 ,  s1 ( t )  1
 1  ln A A 1.0

A=87.6
A=5
- 1.0 A=1
0 1.0 s1(t)

- 1.0
 ITU G.711 A-law curve

Code-word format: Sign bit Part 1 (3bits) Part 2 (4bits)

0/1 000  111 0000  1111

1.0
1
7/8
2
6/8
3
5/8
4
4/8
5
3/8
6
2/8
7
1/8
8
0
1/16 1/8 1/4 1/2 1.0
 ITU G.711 standard
Input range Step size Part 1 Part 2 No. code Decoding output
word
0-1 2 000 0000 0 1
... ... ... ...
30-31 1111 15 31

32-33 2 001 0000 16 33

... ... ... ...
62-63 1111 31 63

64-67 4 010 0000 32 66

... ... ... ...
124-127 1111 47 126

128-135 8 011 0000 48 132

... ... ... ...
248-255 1111 63 252

256-271 16 100 0000 64 264

... ... ... ...
496-511 1111 79 504

512-543 32 101 0000 80 528

... ... ... ...
992-1023 1111 95 1008

1024-1087 64 110 0000 96 1056

... ... ... ...
1984-2047 1111 111 2016

2048-2175 128 111 0000 112 2112

... ... ... ...
3968-4095 1111 127 4032
 Example of G.711 code word

 A quantized-sample’s value is +121

Code word: ?
Decoding value: ?
 A quantized-sample’s value is -121
Code word: ?
Lecture 2: Analog-to-Digital and
Digital-to-Analog conversion

 Duration: 2 hr
 Outline:
1. A/D conversion
2. D/A conversion
DAC
 Anti-imaging filter

magnitude
Anti-imaging Images
filter

0 W 2W =fs 4W = 2fs
frequency

Original two-sided
analog signal spectrum
 Lecture 3
The concept of frequency in
CT & DT signals

 Duration: 2 hrs
 Outline:
1. CT sinusoidal signals
2. DT sinusoidal signals
3. Relations among frequency variables
 Mathematical description of CT
sinusoidal signals

 Functions:

x a ( t )  A cos( t  ),    t  
 A cos( 2f t  ),    t  
xa(t)
 Plot: Tp = 1/f
Acosθ

t
 Properties of CT sinusoidal signals

1. For every fixed value of the frequency f, xa(t) is

periodic: xa(t+Tp) = xa(t)
Tp = 1/f: fundamental period
2. CT sinusoidal signals with different frequencies are
themselves different
3. Increasing the frequency f results in an increase in the
rate of oscillation of the signal (more periods in a
given time interval)
 Properties of CT sinusoidal
signals (cont)

 For f = 0  Tp = ∞
 For f = ∞  Tp = 0
 Physical frequency: positive
 Mathematical frequency: positive and negative

A j (  t  ) A  j ( t  )
x a (t )  A cos(  t   )  e  e
2 2
 The frequency range for CT signal:
-∞ < f < +∞
 Lecture 3
The concept of frequency in
CT & DT signals

 Duration: 2 hrs
 Outline:
1. CT sinusoidal signals
2. DT sinusoidal signals
3. Relations among frequency variables
 Mathematical description of DT
sinusoidal signals

 Functions: x (n )  A cos(  n  ),    n  

 A cos( 2Fn  ),    n  
2

1.5

 Plot: 0.5
Amplitude

-0 . 5

-1

-1 . 5

-2
0 5 10 15 20 25 30 35 40
T im e in d e x n
 Properties of DT sinusoidal signals

1. A DT sinusoidal signal x(n) is periodic only if its

frequency F is a rational number

x(n  N)  x(n) n
A cos[ 2F0 ( n  N )  )]  A cos( 2F0 n  ) n
2F0 N  2k
k
F0 
N
 Properties of DT sinusoidal signals

2. DT sinusoidal signals whose frequencies are separated by

an integer multiple of 2 are identical

x ( n )  cos[(  0  2) n  ]  cos(  0 n  2n  )  cos(  0 n  )

 All x k ( n )  A cos( k n  ), k  0, 1, 2, ...

 k   0  2k,     0   
are identical
 Properties of DT sinusoidal signals

3. The highest rate of oscillation in a DT sinusoidal signal is

obtained when:

   (or    )

or, equivalently, 1 1
F (or F   )
2 2
Illustration for x (n )  cos(2 F0 n )
property 3
F = 1/8
0
F = 3/24
FF =03/12= 1/4
1 1

0.5 0.5

0 0

-0.5 -0.5

-1 -1
0 5 10 15 20 25 30 0 5 10 15 20 25 30

F = 1/2
F = 3/6 0
FF =03/4= 3/4
1 1

0.5 0.5

0 0

-0.5 -0.5

-1 -1
0 5 10 15 20 25 30 0 5 10 15 20 25 30

-π ≤ Ω ≤ π or -1/2 ≤ F ≤ 1/2: fundamental range

 Lecture 3
The concept of frequency in
CT & DT signals

 Duration: 2 hrs
 Outline:
1. CT sinusoidal signals
2. DT sinusoidal signals
3. Relations among frequency variables
 Sampling of CT sinusoidal signals

CT signal Sampling DT signal

xa(t) xa(nT)
A cos( 2f nT  )
A cos( 2f t  )  2 f n 
 A cos   
 fS 
f
F Normalized
fs frequency
 Relations among frequency variables

CT signals DT signals

  2f   2F

     
   f  
f      
F
  / T     / T
fs  1 / 2  F  1 / 2

 f s / 2  f  f s / 2
 Exercise 1

Consider the analog signal

x(t )  3 cos100 t , t[ s ]
a) Determine the minimum sampling rate required to avoid aliasing
b) Suppose that the signal is sampled at the rate fs = 200 Hz. What is
the DT signal obtained after sampling?
c) Suppose that the signal is sampled at the rate fs = 75 Hz. What is
the DT signal obtained after sampling?
d) What is the frequency 0 < f < fs/2 of a sinusoidal signal that yields
samples identical to those obtained in part (c)?
 Solution

x(t )  3 cos100 t , t[ s ]
 Solution

x(t )  3 cos100 t , t[ s ]
 Exercise 2

An analog signal is sampled at its Nyquist rate 1/Ts, and

quantized using L quantization levels. The derived signal
is then transmitted on some channels.
(a) Show that the time duration, T, of one bit of the
transmitted binary encoded signal must satisfy

T  Ts /(log2 L)
(b) When is the equality sign valid?
 HW – Problem 1 (20%)
1
n 0 1 2 3 4 5 6 7 8
Sample(V) 0.1111 0.6250 0.9555 3.4373 4.0500 2.8755 1.5625 2.7500 4.9676

A set of analog 2
Quantization
samples, listed in Range of analog
Digital code Level (V) inputs (V)
table 1, is digitized
using the 000 0.0 0.0 0.3125
quantization table 001 0.625 0.31250.9375
2. Determine the 010 1.250 0.93751.5625
digital codes, the
011 1.875 1.56252.1875
quantized level,
100 2.500 2.18752.8125
and the
quantization error 101 3.125 2.81253.4375
for each sample. 110 3.750 3.43754.0625
111 4.375 4.06255.0
 HW – Problem 2 (20%)

Consider that you desire an A/D conversion system, such that the
quantization distortion does not exceed ±1% of the full scale
range of analog signal.
(a) If the analog signal’s maximum frequency is 4000 Hz, and
sampling takes place at the Nyquist rate, what value of sampling
frequency is required?
(b) How many quantization levels of the analog signal are needed?
(c) How many bits per sample are needed for the number of levels
found in part (b)?
(d) What is the data rate in bits/s?
 HW – Problem 3 (20%)

A 3-bit D/A converter produces a 0 V output for the

code 000 and a 5 V output for the code 111, with
other codes distributed evenly between 0 and 5 V.
Draw the zero order hold output from the converter for
the input below:
111 101 011 101 000 001 011 010 100 110
 HW – Problem 4 (20%)

Determine whether or not each of the following signals

is periodic, specify its fundamental period.

a) x(t )  3 cos(5t   / 6)
b) x(n)  3 cos(5n   / 6)
c) y (n)  2 exp[ j (n / 6)   ]
d )h(n)  cos(n / 8) cos(n / 8)
e) w(n)  cos(n / 2)  sin(n / 8)  3 cos(n / 4   / 3)
 HW – Problem 5 (20%)
Consider the following continuous-time sinusoidal signal

xa (t )  sin 2 f 0 t ,    t  

Its sampled version is described by values every T (s) as the formula below
f0
x ( n)  xa ( nT )  sin 2 n,    n  
fs
where fs = 1/T is the sampling frequency.
a) Plot the signal x(n), 0 ≤ n ≤ 99 for fs = 5 kHZ and f0 = 0.5, 2, 3, and 4.5
kHz. Explain the similarities and differences among the various plots.
b) Suppose that f0 = 2 kHz and fs = 50 kHz.
(1) Plot the signal x(n). What is the frequency F0 of the signal x(n).
(2) Plot the signal y(n) created by taking the even-numbered samples of
x(n). Is this a sinusoidal signal? Why? If so, what is its frequency?
 CHAPTER 2:
DISCRETE-TIME SIGNALS & SYSTEMS

Lesson #4: DT signals

Lesson #5: DT systems
Lesson #6: DT convolution
Lesson #7: Difference equation models
Lesson #8: Block diagram for DT LTI systems
Duration: 9 hrs
 Lecture #4
DT signals

1. Representations of DT signals
2. Some elementary DT signals
3. Simple manipulations of DT signals
4. Characteristics of DT signals
 Sampled signals

Converting a CT signal into a DT signal by sampling: given xa(t) to

be a CT signal, xa(nT) is the value of xa(t) at t = nT  DT signal is
defined only for n an integer

-2T -T 0 T 2T 3T 4T 5T 6T 7T . . . nT

x a (t )  x a (nT)  x (n ),    n  
t  nT
 Representations of DT signals

1. Functional representation
1, n  1,3

x[n ]  4, n  2
0, n 


2. Tabular representation

n … -1 0 1 2 3 4…
x[n] … 0 0 1 4 1 0…
 Representations of DT signals

3. Sequence representation

 
x[n]  0 , 1 , 4 , 1


4. Graphical representation 4

1 1

-1 0 1 2 3 4 5 n
 Lecture #4
DT signals

1. Representations of DT signals
2. Some elementary DT signals
3. Simple manipulations of DT signals
4. Classification of DT signals
Some elementary DT signals

1. Unit step sequence

2. Unit impulse signal
3. Sinusoidal signal
4. Exponential signal
 Unit step

1 n  0
u[n]  
0 n  0

1 1 1

-1 0 1 2 3 4 5 6 n
 Time-shifted unit step

1, n  n 0
u[ n  n 0 ]  
0, n  n 0
For n0 > 0

1 1 1

0 -n0-1 n0 n0+1 n
 Time-shifted unit step

1, n  n 0
u[ n  n 0 ]  
0, n  n 0

For n0 < 0

1 1 1

-n0-1 n0 n0+1 0 n
 Unit impulse

1 n  0
 [n]  
0 n  0

-2 -1 0 1 2 n
 Time-shifted unit impulse

1, n  n 0
[ n  n 0 ]  
0, n  n 0
For n0 > 0

0 n0-1 n0 n0+1 n
Time-shifted unit impulse

1, n  n 0
[n  n 0 ]  
0, n  n 0

n0-1 n0 n0+1 0 n
Relation between unit step and
unit impulse

n
u[n ]   [k ]
k  

[ n ]  u[ n ]  u[n  1]
x[n ][ n  n 0 ]  x[n 0 ][n  n 0 ]


 x[n ][n  n
n  
0 ]  x[n 0 ]
 Sinusoidal signal

x (n )  A cos( n  ),    n  
 A cos(2Fn  ),    n  

1.5

0.5

-0 . 5

-1

-1 . 5
-2 0 -1 5 -1 0 -5 0 5 10 15 20
 Exponential signal

n
x[n ]  Ca
1. If C and a are real, then x[n] is a real exponential
a > 1  growing exponential
0 < a < 1  shrinking exponential
-1 < a < 0  alternate and decay
a < -1  alternate and grows
2. If C or a or both is complex, then x[n] is a complex
exponential
An example of real exponential signal

x[n]  (0.2)(1.2) n

120

100

80
Amplitude

60

40

20

0
0 5 10 15 20 25 30 35
Tim e index n
 An example of complex
exponential signal
 1 
   j n
 12 6 
x[n]  2e
Re al part
2

-1

-2
0 5 10 15 20 25 30 35 40

Im aginary pa rt
2

-1
0 5 10 15 20 25 30 35 40
 Periodic exponential signal

 Recall: A DT sinusoidal signal is periodic only if its

frequency is a rational number
 Consider complex exponential signal:

j 0 n
x[n ]  Ce  C cos( 0n )  j sin( 0n )

 It is also periodic only if its frequency is a rational number:

k 0 k
F0  or 
N 2 N
 Fundamental period

 The fundamental period can be found as

k 2
N
0

Where k is the smallest integer such that N is an integer

0
 Step 1: Is rational?
2
 Step 2: If yes, then periodic; reduce to

0 k # cycles
 
2 N # po int s
 Examples

Determine which of the signals below are periodic. For the

ones that are, find the fundamental period and
fundamental frequency 
j n
6
x1[n ]  e
0  1 k
    One cycle in 12 points
2 6(2 ) 12 N
N  12 : fundamental period
2 2  : fundamental frequency
0   
N 12 6
 Examples
Determine which of the signals below are periodic. For the
ones that are, find the fundamental period and
fundamental frequency
 3 
x2 [n ]  sin  n  1
 5 
 Examples

Determine which of the signals below are periodic. For the

ones that are, find the fundamental period and
fundamental frequency

x3[n ]  cos(2n   )
 Examples

Determine which of the signals below are periodic. For the

ones that are, find the fundamental period and
fundamental frequency

x4 [n ]  cos(1.2n )
 Lecture #4
DT signals

1. Representations of DT signals
2. Some elementary DT signals
3. Simple manipulations of DT signals
4. Classification of DT signals
Simple manipulations of DT signals

 Adding and subtracting signals

 Transformation of time:
- Time shifting
- Time scaling
- Time reversal
 Transformation of amplitude:
- Amplitude shifting
- Amplitude scaling
- Amplitude reversal
 Adding and Subtracting signals

 Do it “point by point”
 Can do using a table, or graphically, or by
computer program
 Example: x[n] = u[n] – u[n-4]

n <=-1 0 1 2 3 >=4
x[n] 0 1 1 1 1 0
 Time shifting a DT signal

x[n]  x[n - k]; k is an integer

 k > 0: right-shift x[n] by |k| samples

(delay of signal)
 k < 0: left-shift x[n] by |k| samples
(advance of signal)
Examples of time shifting

x[n] 4

1 1

-1 0 1 2 3 4 n

4
x[n-2]
1 1

-1 0 1 2 3 4 n
Examples of time shifting

x[n] 4

1 1

-1 0 1 2 3 4 n

x[n+1] 4

1 1

-1 0 1 2 3 4 n
 Time scaling a DT signal

x[n]  y[n] = x[an]

 |a| > 1: speed up by a factor of a

a must be an integer
 |a| < 1: slow down by a factor of a
a = 1/K; K must be an integer
 Examples of time scaling

x[n] 4

1 1

-1 0 1 2 3 4 n

x[2n+1] 4 x[2n]

-2 -1 0 1 2 n -1 0 1 2 n
 Examples of time scaling

x[n] 4
n x[n] y[n]=x[n/2]
1 1 0 1 1
1 4 ??
?
-1 0 1 2 3 4 n
2 1 4
3 0 ??
?

How to find y[1] and y[3]??

One solution is linear interpolation used in a simple

compression scheme
 Examples of time scaling
 Given x[n] 2

-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7

 w1[n] = x[2n]

 What does w1[n/2] look like? Just look like x[n]!

 Examples of time scaling
 Given x[n] 2

-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7

 Find w2[n] = x[2n+1]

 What does w2[n/2] look like? Just look like w2[n]!

 Time reversal a DT signal

x[n]  x[-n]

Flip a signal about the vertical axis

Examples of time reversal

x[n] 4

1 1

-1 0 1 2 3 4 n

x[-n] 4

-3 -2 -1 0 1 2 3 4 n
Combining time reversal and time shifting

x[n]  y[n] = x[-n-k]

Method 1: Flip first, then shift

Method 2: Shift first, then flip
 Example – Method 1

x[n]  y[n] = x[-n-k]

Method 1: Flip first, then shift

Ex. Find y[n] = x[-n-2] = x[-(n+2)]
x[n]  x[-n] = w[n]  w[n+2] = x[-(n+2)]
Flip Advance by 2
(left shift)
 4

Example 1
x[n]
Method 1
-1 0 1 2 3 4 5 n
 Example – Method 2

x[n]  y[n] = x[-n-k]

Method 2: Shift first, then flip

Ex. Find y[n] = x[-n-2] =
x[n]  x[n-2] = w[n]  w[-n] = x[-n-2]
Delay by 2 Flip w[n]
(right shift)
 4
x[n]
Example 1

Method 2
-1 0 1 2 3 4 5 n
Combining time shifting and time scaling

x[n]  y[n] = x[an-b]

Method 1: time scale then shift

Method 2: shift then time scale
Be careful!!! For some cases, method 1 or 2 doesn’t work.
To make sure, plug values into the table to check
 Example – Method 1

x[n]  y[n] = x[an-b]

Method 1: time scale then shift

Ex. Find y[n] = x[2-2n]
y[n] = x[-2(n-1)]
x[n]  x[-2n] = w[n]  w[n-1] = x[-2(n-1)]
Time scale Delay
by -2 by 1
 4

Example x[n] 1
Method 1
-1 0 1 2 3 4 5 n

x[-2n] = w[n]

-4 -3 -2 -1 0 1 2 3 4 5 n

w[n-1] = x[-2(n-1)] = x[-2n+2]

-4 -3 -2 -1 0 1 2 3 4 5 n
 Example – Method 2

x[n]  y[n] = x[an-b]

Method 2: shift then time scale

Ex. Find y[n] = x[2-2n]
x[n]  x[n+2] = w[n]  w[-2n] = x[2-2n]
Time
advance by 2 scale
by -2
 4
x[n]
1
Example
Method 2 -1 0 1 2 3 4 5 n
 Example

y[n] = x[2n-3]??

n x[n] y[n]
-1 0 0
0 0 0
y[n] 1 1 1 0
2 4 1
-1 0 1 2 3 4 n 3 1 1
4 0 0
 Exercise

 Find x[ n]  (u[ n  1]  u[ n  5])( nu[2  n])

x[n] 2
1
-1
0 1 2 3 4 5 n
-1
Lecture #4
DT signals

1. Representations of DT signals
2. Some elementary DT signals
3. Simple manipulations of DT signals
4. Characteristics of DT signals
 Characteristics of DT signals

 Symmetric (even) and anti-symmetric (odd)

signals
 Energy and power signals
 Even and odd signals
 A DT signal xe[n] is even if

Even  xe [n]  xe [ n]

And the signal xo[n] is odd if
Odd  xo [n]   xo [ n]
 Any DT signal can be expressed as the sum of an even
signal and an odd signal:
xe [n]  12 ( x[n]  x[n])

xo [n]  12 ( x[n]  x[n])

x[n]  xe [n]  xo [n]

 Even and odd signals

 How to find xe[n] and xo[n] from a given x[n]?

 Step 1: find x[-n]
 Step 2: find
xe [n]  12 ( x[n]  x[n])
 Step 3: find
xo [n]  12 ( x[ n]  x[n])
 Example
 Given x[n] 2

-4 -3 -2 -1 0 1 2 3 4 5 6 7 8

 Find x[-n]
2

-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
 Example

 Find x[n] + x[-n]

-4 -3 -2 -1 0 1 2 3 4 5 6 7 8

 Find xe[n]
 Example
 Find x[n] - x[-n]
2

-4 -3 -2 -1 0 1 2 3 4 5 6 7 8

 Find x0[n]
 Energy and power signals


2
 Define the signal energy: E  x[n]
n  

N
Define the signal power: 1 2
 P  lim
N  2 N  1

n  N
x[ n ]

 E is finite  x[n] is called an energy signal

 E is finite  P = 0
 E is infinite  P maybe finite or infinite. If P is finite and
nonzero  x[n] is called power signal
 Examples

 Determine which of the signals below are energy signals?

Which are power signals?

(a) Unit step 1 n  0

u[n]  
0 n  0
 
2
E  x[n ]  12  
n   n 0

N N
1 2 1 2 N 1
P  lim
N  2 N  1

n N
x[ n ]  lim
N  2 N  1

n 0
1  lim
N  2 N  1
 1/ 2  0

Unit step is a power signal

 Examples
 Determine which of the signals below are energy signals?
Which are power signals?

(1 / 2) n , n  0 
 a n0
(b) x[n ]   n n  if | a | 1
(2) , n  0  a  1  a
n  n0  if | a | 1

 Examples

 Determine which of the signals below are energy signals?

Which are power signals?

 
(c) x[n ]  cos n (u[n ]  u[n  4])
4 
  
cos n  0  n  3 2 2
x[ n ]    4    [n ]   [n  1]   [n  3]
0 2 2
 otherwise
Lecture #5
DT systems

1. DT system
2. DT system properties
 Input-output description of DT systems

Think of a DT system as an operator on DT signals:

• It processes DT input signals, to produce DT output signals

• Notation: y[n] = T{x[n]}  y[n] is the response of the

system T to the excitation x[n]

• Systems are assumed to be a “black box” to the user

x[n] DT system y[n]

T{}
 DT system example
A digital low pass filter:

y[n] = 1/5{x[n]+x[n-1]+x[n-2]+x[n-3]+x[n-4]}
1

Before
0 .5
filtering

0
0 20 40 60 80 1 00 1 20

0 .8

0 .6
After
filtering 0 .4

0 .2

0
0 20 40 60 80 1 00 1 20
 Interconnection of DT systems

System1
T1{ }
x[n] y[n]
System2
Parallel T2{ }
connection

y[n] = y1[n] + y2[n] = T1{x[n]} + T2{x[n]} = (T1 + T2){x[n]}

= T{x[n]}

y[n] = T{x[n]}: notation for the total system

 Interconnection of DT systems

x[n] System1 System2 y[n]

T1{ } T2{ }

Cascade connection

y[n] = T2{y1[n]} = T2{T1{x[n]}} = T{x[n]}

y[n] = T{x[n]}: notation for the total system

 Example
y4[n]
1 3
y3[n]
x[n] y[n]
y2[n]
2

y3[n] = T1{x[n]} + T2{x[n]}

y4[n] = T3{y3[n]} = T3{T1{x[n]} + T2{x[n]}}

y[n] = y2[n] + y4[n] = T2{x[n]} + T3{T1{x[n]} + T2{x[n]}}

Lecture #5
DT systems

1. DT system
2. DT system properties
DT system properties

• Memory

• Invertibility

• Causality

• Stability

• Linearity

• Time-invariance
 Memory

 y[n0] = f(x[n0])  system is memoryless (static)

 Otherwise, system has memory (dynamic), meaning that its
output depends on inputs rather than just at the time of the
output

 Ex:
a) y[n] = x[n] + 5:
b) y[n]=(n+5)x[n]:
c) y[n]=x[n+5]:
 Invertibility

A system is said to be invertible if distinct inputs

result in distinct outputs

Ex.: y[n] = |x[n]| is …

 Invertibility

A system is said to be invertible if distinct inputs

result in distinct outputs

x[n] x[n]
T() Ti()

System Inverse system

Ti[T(x[n])] = x[n]
 Examples for invertibility

Determine which of the systems below are invertible

a) Unit advance y[n] = x[n+1] is invertible

 y[n-1] = x[n] is inverse system

n
b) Accumulator y[n]   x[k ]
k  

c) Rectifier y[n] = |x[n]|

 Causality

 The output of a causal system (at each time) does not

depend on future inputs
 All memoryless systems are causal
 All causal systems can have memory or not
 Examples for causality

Determine which of the systems below are causal:

a) y[n] = x[-n]

b) y[n] = (n+1)x[n-1]

c) y[n] = x[(n-1)2]

d) y[n] = cos(w0n+x[n])

e) y[n] = 0.5y[n-1] + x[n-1]

 Stability

 If a system “blow up” it is not stable

In particular, if a “well-behavior” signal (all values have
finite amplitude) results in infinite magnitude outputs,
the system is unstable
 BIBO stability: “bounded input – bounded output” –
if you put finite signals in, you will get finite signals out
 Examples for stability

Determine which of the systems below are BIBO stable:

a) A unit delay system

b) An accumulator

c) y[n] = cos(x[n])

d) y[n] = ln(x[n])

e) y[n] =exp(x[n])
 Linearity

Scaling signals and adding them, then processing through the system
same as
Processing signals through system, then scaling and adding them

If T(x1[n]) = y1[n] and T(x2[n]) = y2[n]

 T(ax1[n] + bx2[n]) = ay1[n] + by2[n]
 Time-invariance

 If you time shift the input, get the same output, but with the
same time shift
 The behavior of the system doesn’t change with time

If T(x[n]) = y[n]
then T(x[n-n0]) = y[n-n0]
 Examples for linearity and time-
invariance

Determine which of the systems below are linear, which

ones are time-invariant
a) y[ n]  nx[ n]

Linear
Not time-invariant
 Examples for linearity and time-
invariance

Determine which of the systems below are linear, wich

ones are time-invariant
2
b) y[n ]  x [ n ]
 Examples for linearity and time-
invariance

Determine which of the systems below are linear, wich

ones are time-invariant
M
c) y[ n]   br x[ n  r ]
r 0
 Example for DT system properties
2
 n  2.5 
Given the system below: y[ n ]    x[ n ]
 n  1.5 

a) Memoryless ?

b) Invertible ?

c) Causal ?
 Example for DT system properties
2
 n  2.5 
Given the system below: y[ n ]    x[ n ]
 n  1.5 

c) Stable ?
 Example for DT system properties
2
 n  2.5 
Given the system below: y[ n ]    x[ n ]
 n  1.5 
d) time-invariant ?

e) Linear ?
 Lecture #6
DT convolution

1. DT convolution formula
2. DT convolution properties
3. Computing the convolution sum
4. DT LTI properties from impulse response
 Computing the response of DT LTI
systems to arbitrary inputs

Method 1: based on the direct solution of the input-output equation

for the system

Method 2:

• Decompose the input signal into a sum of elementary signals

• Find the response of system x[n]   ck xk [n]
to each elementary signal k

• Add those responses to obtain xk [ n ]  y k [ n]

the total response of the system x[n]  y[ n]   ck yk [n]
to the given input signal k
 DT convolution formula

Convolution: an operation between the input signal to a

system and its impulse response, resulting in the output signal

CT systems: convolution of 2 signals involves integrating the

product of the 2 signals – where one of signals is flipped and
shifted

DT systems: convolution of 2 signals involves summing the

product of the 2 signals – where one of signals is flipped and
shifted
 Impulse representation of DT signals


We can describe any DT signal x[n] as: x[n]   x[k ] [n  k ]
k 
Example: x[n]

-1 0 1 2 3 n

x[0]δ[n-0] + x[1]δ[n-1] + x[2]δ[n-2]

-1 0 1 2 n -1 0 1 2 n -1 0 1 2 n
 Impulse response of DT systems

Impulse response: the output results, in response to a unit impulse

Denotation: hk[n]: impulse response of a system, to an impulse at
time k

δ[n] Time-invariant h[n]

DT system

δ[n-k] Time-invariant h[n-k]

DT system

Remember: the impulse response is a sequence of values that may

go on forever!!!
 Response of LTI DT systems to
arbitrary inputs

δ[n-k] LTI DT system h[n-k]

 

x[n]   x[k ] [n  k ] y[ n]   x[k ]h[n  k ]

k  
k 
LTI DT system
Convolution sum

Notation: y[n] = x[n] * h[n]

 Convolution sum in more details

y[0] = x[0] * h[0]

= … + x[-2]h[2] + x[-1]h[1] + x[0]h[0]
+ x[1]h[-1] + x[2]h[-2] + … +
The general output:
y[n] = … + x[-2]h[n+2] + x[-1]h[n+1] + x[0]h[n]
+ x[1]h[n-1] + x[2]h[n-2] + … + x[n-1]h[1]
+ x[n]h[0] + x[n+1]h[-1] + x[n+2]h[-2]

Note: the sum of the arguments in each term is always n

 Lecture #6
DT convolution

1. DT convolution formula
2. DT convolution properties
3. Computing the convolution sum
4. DT LTI properties from impulse response
 Convolution sum properties

 δ[n] * x[n] = x[n]

δ[n-m] * x[n] = x[n-m]
δ[n] * x[n-m] = x[n-m]
 Commutative law
 Associative law
 Distributive law
 Commutative law

x[n] * h[n]  h[n] * x[n]

h[n]
x[n] y[n]

x[n]
h[n] y[n]
 Associative law

( x[n] * h1[ n]) * h2 [n]  x[ n] * (h1[n] * h2 [ n])

h1[n] h2[n]
x[n] y[n]

h1[n]*h2[n]
x[n] y[n]

h2[n] h1[n]
x[n] y[n]
 Distributive law

x[n] * (h1[ n]  h2 [n])  ( x[n] * h1[n])  ( x[n] * h2 [n])

h1[n] + h2[n]
x[n] y[n]

h1[n]

x[n] y[n]

h2[n]
 Lecture #6
DT convolution

1. DT convolution formula
2. DT convolution properties
3. Computing the convolution sum
4. DT LTI properties from impulse response
 Computing the convolution sum
 
y[ n ]   x[k ]h[n  k ]
k  
 y[n0 ]   x[k ]h[n
k  
0  k]

1. Fold h[k] about k = 0, to obtain h[-k]

2. Shift h[-k] by n0 to the right (left) if n0 is positive (negative), to

obtain h[n0-k]

3. Multiply x[k] and h[n0-k] for all k, to obtain the product

x[k].h[n0-k]

4. Sum up the product for all k, to obtain y[n0]

Repeat from 2-4 fof all of n

 The length of the convolution sum result

y [ n ]  x[ n ]  h [ n ]  
k  
x [ k ] h[ n  k ]

Suppose:
Length of x[k] is Nx  N1 ≤ k ≤ N1 + Nx – 1
Length of h[n-k] is Nh  N2 ≤ n-k ≤ N2 + Nh – 1
 N1 + N2 ≤ n ≤ N1 + N2 + Nx + Nh – 2

Length of y[n]:

Ny = Nx + Nh – 1
 Example 1

Find y[n] = x[n]*h[n] where

x[ n]  u[ n  1]  u[ n  3]   [n] h[n]  2  u[n]  u[n  3]

x[n]

-1 0 1 2 3
h[n]
n
-1 0 1 2 3
 Ex1 (cont)
x[k]

-1 0 1 2 3 k

h[k]

-1 0 1 2 3 k

h[-k]

y[0] = 6;
-2 -1 0 1 k
 Ex1 (cont)

x[k]

-1 0 1 2 3 k
h[-k]

-2 -1 0 1 k

h[-1-k]

y[-1] = 2;
-4 -3 -2 -1 0 k
 Ex1 (cont)
x[k]

-1 0 1 2 3 k
h[-k]

-2 -1 0 1 k

y[1] = ?
 Ex1 (cont)
x[k]

-1 0 1 2 3 k
h[-k]

-2 -1 0 1 k

y[2] = ?
 Ex1 (cont)
x[k]

-1 0 1 2 3 k
h[-k]

-2 -1 0 1 k

y[3] = ?
 Ex1 (cont)
x[k]

-1 0 1 2 3 k
h[-k]

-2 -1 0 1 k

y[4] = ?
 Example 2
Find y[n] = x[n]*h[n] where x[ n]  a nu[ n] h[n]  u[n]

Try it both ways (first flip x[n] and do the convolution and then flip
h[n] and do the convolution). Which method do you prefer?
n0

 a
Remember! n  if | a | 1
 a  1  a
n  n0  if | a | 1

n1 ( n1  n0 1)
n 1 an0

n  n0
a a
1 a
 Example 2
Factor out an to
First flip x[n] and do the convolution get form you know

Therefore  a n 1  1 
y[n ]   u[n ]
 a 1 
 Example 2

First flip h[n] and do the convolution

you know this
form

Therefore  a n 1  1 
y[n ]   u[n ]
 a 1 

Tip: first flip the simpler signal!!!

 Example 3

Find y[n] = x[n]*h[n] where x[n] = bnu[n] and h[n] = anu[n+2]

|a| < 1, |b| < 1, a ≠ b
 Example 4
Compute output of a system with impulse response
h[n] = anu[n-2], |a| < 1 when the input is x[n] = u[-n]

Flipping x[n] because it is simpler

 Lecture #6
DT convolution

1. DT convolution formula
2. DT convolution properties
3. Computing the convolution sum
4. DT LTI properties from impulse response
 Recall impulse response

 System output, in response to the unit impulse input:

h[n] = T{δ[n]}
 May go on forever  there are 2 kinds of LTI systems:
1. Finite Impulse Response (FIR) system
2. Infinite Impulse Response (IIR) system
 Be one of system representations
 Be convolved with the input to result in the output
 Calculation of the impulse response
 Applying the unit impulse function to the input-output equation
 Ex.: 1 1 1
y[n ]  y[ n  1]  x[ n ]  x[n  1]
4 2 2
1 1 1 1
Suppose this h[0]  h[1]   [0]   [1] 
4 2 2 2
system is causal 0
1 1 1 1 1 1 5 51
h[1]  h[0]   [1]   [0]  x     
4 2 2 4 2 2 8 84
1
1 1 1 51
h[2]  h[1]   [2]   [1]   
4 2 2 84
2
1 1 1 1 1 5 51
h[3]  h[2]   [3]   [2]  x x   
4 2 2 4 4 8 84

y[n]  (1 / 2) [n]  (1 / 4) n 1 (5 / 8)u[n  1]

 DT LTI properties from impulse response

 Memoryless system: impulse response must have the form

below
h[n] = Kδ[n]

 Invertible system: system with h[n] is invertible if there

exists another impulse response hi[n] such that

h[n]*hi[n] = δ[n]
 DT LTI properties from impulse response

 Causal system: h[n] is zero for all time n<0

The system is causal  output does not depend on future

inputs 

  1
y[n0 ]   h[k ]x[n
k  
0  k ]   h[k ]x[n0  k ] 
k 0
 h[k ]x[n
k  
0  k]

 {h[0]x[n0 ]  h[1]x[n0  1]  ...}  {h[1] x[n0  1]  h[2]x[n0  2]  ...}

Present and past inputs Future inputs

Thus, the second term should be zero  h[n] = 0 n < 0

 DT LTI properties from impulse response

 Causal system: h[n] is zero for all time n<0

 DT LTI properties from impulse response

 BIBO stable system: finite input, finite output

 If x[n] is bounded then:

| x[n ] | M x  
 
Take the
absolute:
| y[n ] |  h[k ]x[n  k ] | y[n] |  h[k ]x[n  k ]
k   k  

| y[n ] | M x  h[k ]
k  
The output is bounded if the impulse response satisfies:


 h[n]
n  
 
 Examples

1. Is h[n] = 0.5nu[n] BIBO stable? Causal?

Stable Causal

2. Is h[n] = 3nu[n] BIBO stable? Causal?

3. Is h[n] = 3nu[-n] BIBO stable? Causal?

 Lecture #7
Difference equation model

1. LTI systems characterized by linear constant

coefficient difference equations
2. Recursive solution of difference equations
3. Closed form solution of difference equations
Linear constant coefficient difference equations

General form:

y[n]  a1 y[ n  1]  ...  a N y[ n  N ]  b0 x[ n]  b1 x[n  1]  ...  bM x[n  M ]

N M
  a k y[n  k ]   b r x[n  r ], a 0  1
k 0 r 0

N, M: non-negative integers
N: order of equation
ak, br: real constant coefficients
Linear constant coefficient difference equations

Two common ways to write:

N M

a
k 0
k y[n  k ]   br x[n  r ], a0  1
r 0
N M
y[n ]   ak y[n  k ]   br x[n  r ]
k 1 r 0

Solving the equation in 2 ways:

1. Solving the equation recursively, one value at a time. Need to start

the iteration with initial conditions

2. Finding a formula for y[n] (a closed form)

 Recursive solution of difference equations

1) Put y[n] on the left hand side by itself

y[n] = -a1y[n-1] - … - aNy[n-N] + b0x[n] + … + bMx[n-M]

2) To calculate a given output at time n = n0, that is y[n0], we add

the weighted M+1 inputs b0x[n0] + … + bMx[n0-M] to the
weighted N past outputs –a1y[n0-1] - … - aNy[n0-N]

3) Increase the time index to n = n0+1 and recursively calculate the

next output. This can continue forever.

To start this recursion somewhere, for example at n0 = 0, we need to

know the N initial conditions y[n0-1], y[n0-2], …, y[n0-N]
 Example 1

Solve iteratively to find the 1st 3 terms of

y[n] – 2y[n-1] = x[n-1]

with initial condition y[-1] = 10, and with the input x[n] = 2u[n]

n x[n] y[n]
-1 0 10 (initial condition)
0 2 y[0] = x[-1]+2y[-1] = 20
1 2 y[1] = x[0]+2y[0] = 2+2(20) = 42
2 2 y[2] = x[1]+2y[1] = 2+2(42) = 86
 Example 2
Find the 1st 3 terms of y[n+2] – y[n+1] +0.24y[n] = x[n+2] -2x[n+1]

with initial condition y[-1] = 2, y[-2] = 1, and input x[n] = nu[n]

This system is time invariant, so it is equivalent to

y[n] – y[n-1] +0.24y[n-2] = x[n] -2x[n-1]

n x[n] y[n]
-2 0 1 (initial condition)
-1 0 2 (initial condition)
0 0 y[n] = x[n]-2x[n-1]+y[n-1]-0.24y[n-2]
y[0] = 1.76
1 1 y[1] = 2.28
2 2 y[2] = 1.8576
 Closed form solutions of difference equations

Total response = zero-input component + zero-state component

= natural response + forced response
= complementary response + particular response

1. Find the complementary response, assume input = 0.

2. Find the particular response, assume all initial conditions = 0.
Choose the form of the particular response same as the form of
input
3. Total response = complementary + particular. Use initial conditions
to find N constants from the complementary response
 Example

Given y[n] – 0.3y[n-1] = x[n] with y[-1] = 0 and x[n] = (0.6)n

 Example (cont)

Combining particular and complementary solutions:

 Lecture #8
Block diagram for DT LTI systems

1. Components for block diagram

2. Direct form I realization of a system
3. Direct form II realization of a system
 Components for block diagram

Components: branch points, summation, delays, gains,

LTI systems
• Signals travel along lines, arrows point direction of inputs
and outputs
• Each component acts the same way, no matter how
many components are connected to it
• For linear system, the order of operation does not matter
responses to obtain
 Components for block diagram

EX: an averaging system y[n] = 0.5(x[n] + x[n-1])

 Lecture #8
Block diagram for DT LTI systems

1. Components for block diagram

2. Direct form I realization of a system
3. Direct form II realization of a system
 Direct form I realization of a system
y[n]  a1 y[n  1]  ...  aN y[n  N ]  b0 x[n]  b1 x[n  1]  ...  bM x[n  M ]
 y[n]  b0 x[n]  b1 x[n  1]  ...  bM x[n  M ]  (a1 ) y[n  1]  ...  (a N ) y[n  N ]

b0
x[n] y[n]
Z-1 Z-1

b1 -a1

Z-1 Z-1

b2 -a2

bM -aN
 Lecture #8
Block diagram for DT LTI systems

1. Components for block diagram

2. Direct form I realization of a system
3. Direct form II realization of a system
 Direct form II realization of a system

To get another realization, we reverse the order of these two systems

“violet” and “yellow” without altering the input-output relation

b0
x[n] y[n]
Z-1 Z-1
b1 -a1

Z-1 Z-1

b2 -a2

bM -aN
 Direct form II realization of a system
We observe that: these two delays contain the same input and hence
the same output  these two delays can be merged into one delay

x[n] b0 y[n]
Z-1 Z-1
-a1 b1

Z-1 Z-1

-a2 b2

-aN bM
 Direct form II realization of a system

x[n] b0 y[n]
Z-1
-a1 b1

Z-1

-a2 b2

Suppose
-aN bN M=N
Example of realization LTI system
 CHAPTER 3:
THE Z-TRANSFORM & ITS APPLICATION TO
THE ANALYSIS OF LTI SYSTEMS

Lesson #9: The Z-transform

Lesson #10: Z-transform properties
Lesson #11: Inversion of Z-transform
Lesson #12: Analysis of LTI systems in the z-domain
 Lecture #9
The Z-transform

1. Definition of the Z-transform

2. Region of convergence
3. Examples of Z-transform
 Introduction to Z-Transform (ZT)
Recall the Laplace Transform:


 f (t )e
 st
F ( s)  dt


Z-Transform is the discrete-time counterpart of the Laplace

Transform: 
F ( z)   f [
n  
n ] z n
 From Laplace Transform to Z-Transform
Take a CT signal f(t) and sample it:

f (t )  

sampling
f s (t )
 
f s (t )   f (t ) (t  nT )   f (nT ) (t  nT )
n   n  
 From Laplace Transform to Z-Transform

Take the Laplace Transform of the sampled signal:

     st  
L[ f s (t )]     f (nT ) (t  nT )  e dt    f (nT ) (t  nT )e  st dt

 n   n 


  
 
n 
f (nT )   (t  nT )e  st dt 


n 
f (nT )e  snT

Let f(nT) = f[n] and esT = z then:

 Definition of the Z-transform

For a DT signal x[n] = …, x[-2], x[-1], x[0], x[1], x[2], …

The bilateral Z-transform of x[n] is defined to be

 Sum goes
X ( z )  ZT x[n]   x[ n ] z n over all
integer
n  
values

Assume that values of z exist such that the summation

converges. z takes values in the complex plane
 Poles and Zeros of Z-transform


X ( z )  ZT x[n]   x[ n ] z n

n  

Poles pk  X(pk) = ∞
Zeros zk  X(zk) = 0

Poles are roots of denominator polynomial

Zeros are roots of numerator polynomial
Note: find these after canceling any common factors – and do this
for polynomial in z (not in z-1)
 Lecture #9
The Z-transform

1. Definition of the Z-transform

2. Region of convergence
3. Examples of Z-transform
 Region of convergence (ROC)

ROC: set of all values of z, for which X(z) converges

We will find the ROC for these cases:
1. Right-sided signal (x[n] = 0, n<n0)
2. Left-sided signal (x[n] = 0, n>n0)
3. Two-sided signal (-∞<n<+∞)
4. Finite-duration signal
Right-sided signal

Sum goes
from n0 to
infinity
Right-sided signal

Infinite Egg White!!!

 Right-sided signal

If x[n] is not causal then X(z) will not converge at z = ∞

 we can’t include ∞ in the ROC
Ex: x[n] = u[n+1]

ROC: rmax < |z| < ∞

Left-sided signal
Left-sided signal

Egg Yolk!!!
 Left-sided signal

If x[n] has values at some times > 0, then X(z) does not
converge at z = 0  we can’t include 0 in the ROC
Ex: x[n] = u[-n+1]

ROC: 0 < |z| < rmin

 Two-sided signal

Two-sided signal = Left-sided signal + right-sided signal

Donut!!!

Note: if |a| ≥ |b| then X(z) does not exist

 Finite-duration signal

For x(n)  (n  m) X( z )   ( n
n  
 m ) z n
 z m

n2 n2
x[n]   x[k ] [n  k ]  X ( z )   x[ k ] z k

k n1 k n1

ROC: all of z, except:

z = 0 if k > 0
z = ∞ if k < 0
 Lecture #9
The Z-transform

1. Definition of the Z-transform

2. Region of convergence
3. Examples of Z-transform
 Examples of Z-transform

Find the ZT of the right-sided and the left-sided sequences

x1[n]  a nu[n] and x2 [n]  (a n )u[n 1]

 1 1
 
 | az | 1
X1 (z)   a z n n
  (az )  1  az 1
1 n

n 0 n 0  1
| az | 1

z
 , |z||a|
za
 Examples of Z-transform
Find the ZT of the right-sided and the left-sided sequences

x1[n]  a nu[n] and x2 [n]  (a n )u[n 1]

 a 1
z 1
 
  | a z | 1
X 2 (z)    a n z  n    (a z )   1  a z
1 n 1

n  1 n 1   1
z | 1
 | a
z
 , |z||a|
za

The ROC must be specified for the bilateral Z-Transform to be unique

 Examples of Z-transform

Find the ZT of the left-sided signal

x[n]  3n u[n  1]  4n u[n  1]

 Examples of Z-transform

n
Find the ZT of the two-sided signal x[n]  a
 Examples of Z-transform

Find the ZT of the two-sided signal

h[n]  (5) u[n  1]  3 u[n  1]

n n
 Examples of Z-transform

Find the ZT of the signal

x[n] =
 Examples of Z-transform
Find the ZT of the right-sided-sided signal

x[n]  r n sin(bn)u[n]
1 n jbn 1 n  jbn
x (n )  r e u (n )  r e u (n )
2j 2j
1 1
 (r e ) u (n )  (re  jb ) n u (n )
jb n

2j 2j
1 z z 
 X(z)     jb 
2j z  r e jb
zr e 
Z rz sin b
r sin(bn )u (n ) 
n
, |z||r|
z  2rz cos b  r
2 2
Lecture #9
Z-transform properties

1. Linearity
2. Time shifting
3. Frequency scaling
4. Multiplication by n
5. Convolution in time
6. Initial value
7. Final value
 Linearity

Z
ax[n]  by[n]  aX ( z )  bY ( z )

The new ROC is the intersection of ROC{X(z)} and ROC{Y(z)}

If aX(z) + bY(z) cancels pole then the new ROC is bigger

Lecture #9
Z-transform properties

1. Linearity
2. Time shifting
3. Frequency scaling
4. Multiplication by n
5. Convolution in time
8. Initial value
9. Final value
 Time shifting
Z
x[n  n0 ]  z  n0 X ( z )

The new ROC is the same as ROC{X(z)} except for z = 0 if

n0>0 and z = ∞ if n0<0
Proof:

Delay of k means that the Z-transform is multiplied by z-k

 Example of applying the time-
shifting property

Determine the ZT of the signal:

1
 
w[n]  (1) n  (3) n 5 u[n  5]
4
Lecture #9
Z-transform properties

1. Linearity
2. Time shifting
3. Frequency scaling
4. Multiplication by n
5. Convolution in time
6. Initial value
7. Final value
 Frequency scaling
Z
z
a x[n] 
n
X 
a
The new ROC is the scaled ROC{X(z)} with factor |a|
(bigger or smaller)
Proof: 
ZT {a n x[n ]}   a n

n  
x[ n ] z n

 n
z z
  x[n ]   X 
n   a a
Multiplication by an results in a complex scaling in the z-domain
 Example of applying the
frequency-scaling property

Determine the ZT of the signal:

x[n]  a u[n]
n
Lecture #9
Z-transform properties

1. Linearity
2. Time shifting
3. Frequency scaling
4. Multiplication by n
5. Convolution in time
6. Initial value
7. Final value
 Multiplication by n
Z dX ( z )
nx[n]   z
dz
The new ROC is the same ROC{X(z)}
Proof:

 
dX ( z ) 1 
X ( z)   x[n]z
n  
n

dz
   nx[n ]z
n  
 n 1
   nx[n ]z n
z n 

dX ( z )
 ZT {nx[n ]}   nx[n]z
n  
n
 z
dz
 Example of applying the
multiplication-by-n property

Determine the ZT of the signal:

x[n]  na nu[n]
Lecture #9
Z-transform properties

1. Linearity
2. Time shifting
3. Frequency scaling
4. Multiplication by n
5. Convolution in time
6. Initial value
7. Final value
 Convolution in time

Z
y[n]  x[n]  h[n]  X ( z ) H ( z )

The new ROC is the intersection of ROC{X(z)} and ROC{Y(z)}

If poles cancel zeros then the new ROC is bigger

Proof: Z  
y[n]  x[n]  h[n]   [  x[k ]h[n  k ]]z  n
n  k 

 
Switching the order of
the summation:
Y ( z)   
x[ k
k  
] h[ n  k ]
n  
z n

 
  x[k ]z
k  
k
 h[ n
n  k  
 k ] z ( n  k )

 X ( z ).H ( z )
 Application of the convolution property

ZT
x[n] X(z)
ZT-1
x[n]*h[n]
ZT
h[n] H(z)
 Example

Compute the convolution of the signals:

x1[n] = δ[n] - 2δ[n-1] + δ[n-2]
x2[n] = δ[n] + δ[n-1] + δ[n-2] + δ[n-3] + δ[n-4] + δ[n-5]
Lecture #9
Z-transform properties

1. Linearity
2. Time shifting
3. Frequency scaling
4. Multiplication by n
5. Convolution in time
6. Initial value
7. Final value
 Initial value theorem

If x[n] is causal then x[0] is the initial value of the function x[n]

x[0]  lim X ( z )
z 

Proof:


X ( z )   x[n]z n  x[0]  x[1]z 1  x[2]z 2  ...
n 0

Obviously, as z  , z n  0
 Initial value theorem

If x[n] = 0 with n < n0 then x[n0] is the initial value, and

x[n0 ]  lim[ z X ( z )]
n0
z 
Proof:

X ( z)   x[ n
n  n0
] z n
 x[ n0 ] z  n0
 x[ n0  1] z ( n0 1)
 x[ n0  2 ] z ( n0  2 )
 ...

z n0 X ( z )  x[n0 ]  x[n0  1]z 1  x[n0  2]z 2  ...

As z  , z n0 X ( z )  x[n0 ]
 Initial value theorem

Ex 1: Find the initial value of x[n] where X(z) = z/(z-0.6)

Ex 2: Find the initial value of x[n] where X(z) = (z^3)/(z-0.6)

Lecture #9
Z-transform properties

1. Linearity
2. Time shifting
3. Frequency scaling
4. Multiplication by n
5. Convolution in time
6. Initial value
7. Final value
 Final value theorem

If this limit exists then x[n] has a final value (steady-state

value)

lim x[n]  x[]  lim[ ( z  1) X ( z )]

n z 1

Proof: Exercise
 Examples
Ex1: unit step u[n]
𝑧
𝑍𝑇 𝑢 𝑛 =
𝑧−1
𝒛
⇒ lim 𝒛 − 𝟏 . = 1=> Ok !
𝒛→𝟏 𝒛−𝟏

Ex2: sinusoidal signal

𝜋𝑛
𝑍𝑇 𝑠𝑖𝑛 𝑢𝑛 =⋯
2
 Examples
Ex3: the impulse response of an LTI system is h[n] = anu[n], |a|<1.
Determine the value of the step response of the system as n∞

The step response of the system is:

y[n] = h[n]*u[n]  Y(z) = X(z).H(z)
 Lecture #10
Inversion of Z-transform

1. Inverse Z-transform formula

2. Using partial fraction expansion to invert the ZT
3. Using power series expansion to invert ZT
 FT formula building

Using the Cauchy theorem:

1 1 if z  0

n 1
I z dz  
2j C 0 if z  0

Z: complex variable

Counterclockwise contour integral is along a closed path in

the z plane
 FT formula building
1
Multiplying two sides of ZT definition formula by z l 1
2 j

1 1
2 j
X ( z ) z l 1   x[
2 j n 
n ] z n l 1
z

Taking the integral:

1 1 
 n l 1 

l 1
X ( z ) z dz     x[n ] z z dz Applying the
2 j C 2 j C  n    Cauchy theorem


1
  x[n ]  z ( l  n ) 1
dz
n   2 j C
 x[l ]
 Inverse ZT formula

The inverse ZT is defined by

1

n 1
x[n ]  X(z)z dz
2j C

Counterclockwise contour integral is along a closed path in

the z plane.

LTI case: can avoid integration – use easier methods

 Lecture #10
Inversion of Z-transform

1. Inverse Z-transform formula

2. Using partial fraction expansion to invert the ZT
3. Using power series expansion to invert ZT
 Partial fraction expansion

Similar to what you saw for Laplace transforms

Y ( z)
Distinct poles: rk  ( z  pk )
z z  pk
 Partial fraction expansion

Repeated poles:
 Z-Transform table

1 (n )  1
2 (n  m)  z  m
z
3 a u[n ] 
n

za
az
4 na u[n ] 
n

(z  a ) 2
az (z  a )
5 n a u[n ] 
2 n

(z  a ) 3
z ( z  a cos )
6 a cos(n)u[n]  2
n

z  2az cos   a 2
az sin 
7 a sin(n)u[n]  2
n

z  2az cos   a 2
 Examples of partial fraction expansion

2 z  5z
2
Distinct poles X ( z)   z  3
( z  2)( z  3)
Divide X(z) by z, to “save” z for later
X(z) 2z  5 (z  2)  (z  3)
 
z (z  2)(z  3) (z  2)(z  3)
1 1
  , | z | 3
z 3 z 2
 x (n )  (3n  2 n )u (n )
 Examples (cont)
2z
Repeated poles X( z )  , z 2
(z  2)(z  1) 2

X( z ) 1 A B C
    , | z | 2
2z (z  2)(z  1) 2
z  2 z  1 (z  1) 2

A(z  1) 2  B(z  1)(z  2)  C(z  2)  1

A  1; B  1; C  1;
 z z z 
X( z)  2    2
, | z | 2
 z  2 z  1 (z  1) 
x(n)  2(2  1  n)u(n)
n
 Examples (cont)
z
Complex poles X( z )  2 |z| > 0.5
z  0.5z  0.25
az sin 
a sin(n)u[n]  2
n

z  2az cos   a 2


(0.5)z sin
4 3
X(z)  x | z | 0.5
3 z 2  2(0.5)z cos   (0.5) 2
3
4  
x (n )  (0.5) sin n u (n )
n

3 3 
 Examples (cont)

z 4
Time-shift W ( z)  2  z  3
property z  2z  3

Divide W(z) by z, to “save” z for later

W(z) z 5 z 5   14 1
 5
 2    4
z
z z  2z  3 (z  1)(z  3)  z  1 z  3 

1 n 5 1 n 5
w[n ]   (1) u[n  5]  (3) u[n  5]
4 4
 Examples (cont)

Given h(n) = anu(n) (|a|<1) and x(n) = u(n).

Find y(n) = x(n)*h(n)

1  a n 1
y[n ]  u[n ]
1 a
 Examples (cont)
Find the output y(n) to an input x(n) = u(n) and an LTI
system with impulse response h(n) = -3nu(-n-1)

1 3 n
y[n]   u[n]  (3) u[n  1]
2 2
 Lecture #10
Inversion of Z-transform

1. Inverse Z-transform formula

2. Using partial fraction expansion to invert the ZT
3. Using power series expansion to invert ZT
 Power series expansion

If you can expand X(z) as a series in z-1


X ( z)   x[ n
n  
] z n
 ...  x[ 2] z 2
 x[ 1] z 1
 x[ 0] z 0
 x[1] z 1
 x[ 2] z 2
 ...

1 2
X ( z)  ...  a2 z  a1 z  a0 z  a1 z  a2 z  ...
2 1 0

you can pick off x(n) as the coefficients of the series

an  x[n]
Examples of power series expansion

Find the inverse Z-transform of

1 2
X ( z )  1  2 z  3z ROC : | z | 0

x (0)  1
x (1)  2
x (2)  3
x (n )(n  0,1,2)  0
 Examples (cont)

1
X( z)  1
, ROC : z  a
1  az
1 2 2 3 3
Long division X(z)  1  az  a z  a z  ...
x (0)  1
x (1)  a
x ( 2)  a 2
x (3)  a 3

...
x (n )(n  0)  0
Lecture #11
Analysis of LTI systems in the Z-domain

1. Transfer function
2. LTI system properties from transfer function
3. Unilateral Z-transform
4. Using unilateral Z-Transform to solve the difference
equations
 Transfer function

For system impulse response h(n), its ZT is often called

Transfer Function H(z)

Consider H(z) = N(z)/D(z)

The roots of N(z): system zeros

The roots of D(z): system poles

D(z) = 0: characteristic equation

 Determination of transfer function
1. From impulse response h(n): Just take Z-Transform

2. From difference equation:

- Take Z-Transform for both side

- Put the Y(z) on left side

- Divide both side by X(z)

3. From block diagram:

(1) Find the difference equation, then find H(z) from equation

(2) Put X(z) as input, then directly find Y(z) from block diagram
Transfer function from difference equation

N M

a
k 0
k y[n  k ]  b r x[n  r ]
r 0
ZT
N M

-Linear
a
k 0
k z Y( z )  b r z X( z )
k

r 0
r

-Time-shift M

Y(z)  r
b z r

Y(z) = X(z) . H(z) H(z)   r 0

N

a
X(z) k
k z
k 0
Transfer function from difference equation

Suppose M = N

Multiply num. and den. by zN:

M N

Y ( z) b z r
r
b z r
r

H ( z)   r 0
N
 r 0
N

 k k
X ( z) k k
a z a z
k 0 k 0
 Example
For the α-filter:
y(n)  (1   ) y(n  1)   x(n)
M
Its transfer function: r
b z r

H ( z)  r 0

N
1  (1   ) z 1
 k
a
k 0
z k

For example: y[n] – 0.9y[n-1] = 0.1x[n]  α = 0.1

0.1z
H ( z) 
z  0.9
 Transfer function from block diagram

Find the transfer function of the delay unit

D
x[n] y[n]

y[n] = x[n-1]  Y(z) = z -1X(z)  H(z) = z -1

Z-1
X(z) Y(z)
 Transfer function from block diagram
Find the transfer function of this feedback system
w[n]
x[n] H1(z) y[n]

H2(z)

y[n] =( x[n]+y[n]*h2[n] ) * h1[n]

Y (z) = [X(z)+Y(z).H2(z)].H1(z)

Y ( z) H1 ( z )
H ( z)  
X ( z ) 1  H1 ( z ).H 2 ( z )
Lecture #11
Analysis of LTI systems in the Z-domain

1. Transfer function
2. LTI system properties from transfer function
3. Unilateral Z-transform
4. Using unilateral Z-Transform to solve the difference
equations
 Causality

 Recall:
Causal system  h[n]  0 n  0
 h(n) is right-sided signal  ROC of transfer function is

| z | rmax
 An LTI system is causal if and only if the ROC of the transfer
function is the exterior of a circle of radius rmax < ∞
including the point z = ∞
 Causality (cont)

 Consider the system:

z 2  0.4 z  0.9 z  0.9

H ( z)   z
z  0.6 z  0.6

Unit advance y[n]=x[n+1]

 noncausal

 For the causal system, the numerator of H(z) can not be of

higher order than the denominator
 If the numerator order is less equal to the denominator
order then the system is causal??? NOT SURE!!!
 Example

 Consider this system:

h[n ]  u[n  1]
z
H ( z)  ROC :| z | 1
z 1

 Numerator order is 1; denominator order is 1; but it is non-

causal!!!
 Stability

 Recall:

Stable system   h[n]
n  
 

 Its transfer function:

  
H( z )   h[
n 
n ]z n
| H(z) |  | h
n 
[ n ]z n
|   | h
n 
[ n ] | | z n
|

Unit circle |z| = 1  | H(z) | | h[n] |
n  
The ROC includes |z| = 1

 An LTI system is BIBO stable if and only if the ROC of the

transfer function includes the unit circle.
 Causality and Stability

 The conditions for causality and stability are different and

one does not imply the other
 4 cases:
- Causal and stable system
- Non-causal and stable system
- Causal and unstable system
- Non-causal and unstable system
 A causal system is BIBO stable, provided that all poles of
H(z) lie inside the unit circle.
 Examples

Ex1: Given an LTI system:

2 z 2  1.6 z  0.9
H ( z)  3
z  2.5 z  1.96 z  0.48
2

The poles of H(z):

den = [1 -2.5 1.96 -0.48];  p = 1.2 0.8 0.5

p = roots(den)
1. |z|>1.2: causal, unstable
2. 0.8<|z|<1.2: non-causal, stable
3. 0.5≠|z|<0.8: non-causal, unstable
 Examples
Ex2: A LTI system is characterized by:

3  4 z 1 z ( 3 z  4) z 2z
H ( z)  1 2
 2  
1  3.5z  1.5z z  3.5z  1.5 z  0.5 z  3

Specify the ROC of H(z) and find h[n] for the following conditions:
1. The system is stable
2. The system is causal
3. The system is anticausal
 Examples
Ex2: A LTI system is characterized by:

3  4 z 1 z ( 3 z  4) z 2z
H ( z)  1 2
 2  
1  3.5z  1.5z z  3.5z  1.5 z  0.5 z  3
 Invertibility

The inverse of a system H(z) is a second system Hi(z) that,

when cascaded with H(z), yields the identity system

H(z).Hi(z) = 1
Hi(z) = 1/H(z)

X(z) X(z)
H(z) Hi(z)
 Invertibility

H(z) = N(z)/D(z)  Hi(z) = D(z)/N(z)

H(z) is causal  M≤N and if Hi(z) is causal  N≤M.

Hence, for both systems to be causal  M = N

H(z) is stable: all poles lie inside the unit circle.

Hi(z) is stable: all poles (zeros of H(z)) lie inside the unit circle.

Hence, for both systems to be stable, both the poles and

zeros of H(z) must lie inside the unit circle
Lecture #11
Analysis of LTI systems in the Z-domain

1. Transfer function
2. LTI system properties from transfer function
3. Unilateral Z-transform
4. Using unilateral Z-Transform to solve the difference
equations
 Unilateral Z-Transform

 In control applications, causal systems are interested in:

h[n] = 0 with all n < 0
 When considering CT causal systems, the Unilateral
Laplace Transform is used
Similarly, when considering DT causal systems, the
Unilateral Z-transform is used

 In difference equations, the initial conditions are non-zero

 the Unilateral Z-Transform is used
 Unilateral ZT

X  ( z )   x[n ]z n
n 0
Z

Notation : x[n ]  X ( z)

1. It does not contain information about the signal x[n] for n<0

2. Unilateral X+(z) is identical to the bilateral X(z) of the signal

x[n].u[n]

3. ROC of X+(z) is always outside a circle  no need to refer to

ROC
 Time shifting property of unilateral ZT
Z

If x[n ]  X ( z)
Z 1
then k 
x(n  k )  z X ( z )  z k
 x[i ]z
i  k
i
,k  0

Ex.: x(n-1)  x(-1) + z-1X+(z)

x(n-2)  x(-2) + z-1x(-1) + z-2X+(z)
Lecture #11
Analysis of LTI systems in the Z-domain

1. Transfer function
2. LTI system properties from transfer function
3. Unilateral Z-transform
4. Using unilateral Z-Transform to solve the
difference equations
 Using Z-transform to solve the
difference equation

N M

a
k 0
k
y[n  k ]   br x[n  r ]
r 0

1. Take the unilateral ZT of equation

2. Find the output in the Z-domain, Y(z)
3. Use inverse ZT to get the output y(n) from Y(z)
 Example

Find the output, y[n], n  0

of the system

y[n]  3y[n  1]  2y[n  2]  x[n]

in two cases:
a) n 2
x[n]  3 u[n], y[2]  0, y[1]  0
b)
n 2 4 1
x[n ]  3 u[n ], y[2]   , y[1]  
9 3
 Example

a) Take the bilateral ZT of the equation:

y[n ]  3y[n  1]  2 y[n  2]  x[n ]

 Y(z)  3z 1Y(z)  2z  2 Y(z)  X(z)
1 z
 Y(z)(1  3z  2z ) 
1 2

9 z3
1 z 1
 Y(z) 
9 z  3 1  3z  2z
1 2

1 z z2
 Y(z) 
9 z  3 z 2  3z  2
 Example

b) Take the unilateral ZT of the equation:

y[n ]  3y[n  1]  2 y[n  2]  x[n ]

 Y(z)  3[z 1Y(z)  y(1)]  2[z 2 Y(z)  z 1y(1)  y(2)]  X(z)
1 z
 Y(z)(1  3z  2z ) 
1 2
 3y(1)  2z 1y(1)  2 y(2)
9 z3
1 z 2 1 8  1 
 Y(z)    1  z   2 
9 z 3 9  1  3z  2z 
1
3
z2 z2
 Y(z) 
z(z  3) (z  3z  2)
2
 Homework 3

E1. Find x(n)*h(n) using the Z-transform

a) x[n ]   4 u[n  1] ,
1 n
h[n ]  [1  ( ) ]u[n ]
1 n
2

b) x[n ]  u[n ] , h[n ]   [n ]  ( 12 )n u[n ]

c) x[n ]  nu[n ] , h[n ]  2n u[n  1]

 Homework 3
E2
We want to design a causal LTI system with the property that if
the input is x[n] = (0.5)nu[n] -0.25(0.5)n-1u[n-1]
then the output is y[n] = (1/3)nu[n]
a) Find H(z) and then h(n) of a system that satisfies the
foregoing conditions
b) Find the difference equation that characterizes this system
c) Determine a realization of the system that requires the
minimum possible amount of memory
d) Determine if the system is stable
 Homework 3

E3. Use the Z-transform to evaluate the following

series:
∞ 𝑛
a) 𝑥 = 𝑛=0 0.2

∞ 𝑛
b) 𝑥 = 𝑛=4 0.2

∞ 𝑛 cos(0.2n)
c) 𝑥 = 𝑛=0 0.2
 Homework 3

E4. A causal linear, time-invariant system is

described by this difference equation:
𝑦 𝑛 =𝑥 𝑛 +𝑦 𝑛−1
a) Find the system impulse response
1 𝑛
b) Find y[n] for an input 𝑥 𝑛 = 𝑢 𝑛 . Label
2

the natural and forced responses in y[n]

c) Is the system BIBO stable ?
 Homework 3

E5. Find the inverse of the bilateral Z-transform:

1.5𝑧 2 − 1.3
𝐹 𝑧 =
(𝑧 − 1)(𝑧 − 9)
for the following regions of convergence.
a) 𝑧 < 0.9
b) 𝑧 > 1
c) 0.9 < 𝑧 < 1
d) Find the final values of the functions of parts (a)
through (c)
 CHAPTER 4:
FREQUENCY ANALYSIS OF
SIGNALS AND SYSTEMS

Lesson #13: Review of CTFT and Sampling

Lesson #14: Discrete-Time Fourier Transform (DTFT) & Inverse
DTFT
Lesson #15: DTFT properties
Lesson #16: Frequency spectrum of DT signals
Lesson #17: Frequency-domain characteristics of LTI systems
Lesson #18: Digital filters
 Lecture #13
Review of CTFT and Sampling

1. The Fourier series for CT periodic signals

2. The Fourier Transform for CT aperiodic signals (CTFT)
3. Sampling of CT signals
4. Aliasing
 The Fourier series of CT periodic signal

x(t) is periodic and satisfies the Dirichlet conditions

T
x(t)

 2

a e
j nt
Fourier series: x (t )  n
T
t
n  
T /2 2
1 j nt
Fourier coefficients: an 
T 
T / 2
x (t )e T
dt
 Power density spectrum of periodic signal
A periodic signal has infinite energy and finite average power, which is
T /2 T /2
1 1
Px   | x (t ) | dt   x(t ). x * (t )dt
2

T T / 2
T T / 2
2
1
T /2
   nt 
x (t )  an e
j
  dt
* T
T T / 2  n   
 
* 1
T /2
j
2
 
  an  dt    | an |2
nt

n   T

T / 2
x (t )e T

 n  
T /2 
1
Parseval’s relation: Px 
T  | x ( t ) |2
dt   n
| a
n  
|2

T / 2
 Lecture #13
Review of CTFT and Sampling

1. The Fourier series for CT periodic signals

2. The Fourier Transform for CT aperiodic signals
(CTFT)
3. Sampling of CT signals
4. Aliasing
The Fourier transform of CT aperiodic signal

x(t) is aperiodic and satisfies the Dirichlet conditions

Fourier transform pair:


X( )   x (t )e
 jt
dt  FT x (t )


x (t ) 
1
 X ( )e
jt
d  FT 1
X ( )
2 
 Fourier transform properties

F
Linearity: ax(t)  by(t)  aX ( )  bY ( )
F
- j 
Time shift: x (t   )  e X ( )
F
Time reverse: x ( t )  X (  )
F
Convolution in
time domain:
x (t ) * y (t )  X ( ).Y ( )
F 1
Multiplication in x (t ). y (t )  X ( ) * Y ( )
time domain: 2
 Energy density spectrum of aperiodic signal
Let x(t) be finite energy signal, which is
 
Ex   dt   x(t ). x * (t )dt
2
| x ( t ) |
 

 1 

  x (t )  X * ( )e
 jt
d dt
  2  
1

 
 1


 X * ( )  x (t )e dt d   | X ( ) |
 jt
 2
d
2     2 

 
1
Parseval’s relation: E x   | x(t ) | dt 
2
 | X ( ) |2
d

2 
 Lecture #13
Review of CTFT and Sampling

1. The Fourier series for CT periodic signals

2. The Fourier Transform for CT aperiodic signals (CTFT)
3. Sampling of CT signals
4. Aliasing
 Sampling of CT signals
Define the CT impulse train as:

x(t) is CT signal we want to sample:

To sample x(t), we will multiply x(t) by p(t)

 Sampling of CT signals

Let xs(t) be the sampled signal. Then,

x(t )  
 xs (t )
sampling

 
xs (t )   x(t ) (t  nT )   x(nT ) (t  nT )
n   n  

Signal xs(t) consists

of a train of CT
impulses – take off
the arrow heads to
get x(n) – a DT
signal
 Spectrum of sampled signals

Consider y(t) = xs(t) = x(t).p(t) in the frequency domain

Take Fourier transform of x(t)

X(ω) = FT{x(t)} and P(ω) = FT{p(t)}

 Spectrum of sampled signals

Finding FT{p(t)}, using the continuous-time FT of periodic signals

 
p(t )    (t
n  
 nT ) 
FT
P( )   2an (  ns )
n  

1 T /2 1
an    (t )e dt 
T T / 2
 jt

T
 P( )     (  n )
n  
s s

A CT impulse train has a FT that is an impulse train in frequency

Spacing between pulses in time is T
Spacing between pulses in frequency is 2π/T
Increasing period in time domain decreases it in frequency domain
 Spectrum of sampled signals
Back to Xs(ω); with ωs: the sampling frequency

1   
X s ( )  X ( ) *   s (  ns )
2 n   
s 
1 

2

n  
X (  ns )   X (  ns )
T n  
The effect of sampling is an infinite sum of scaled, shifted
copies of the continuous time signal's Fourier Transform
 Lecture #13
Review of CTFT and Sampling

1. The Fourier series for CT periodic signals

2. The Fourier Transform for CT aperiodic signals (CTFT)
3. Sampling of CT signals
4. Aliasing
 Aliasing

Note that the triangles don’t overlap – so with an ideal

low pass filter with cut-off frequency ω=π/T, we could
filter xs(t) to perfectly recover x(t)
 Aliasing (cont)

- The triangles overlap  can’t recover x(t)

- Happens when ωs = 2π/T < 2ωb

0 ωb ωs
Aliasing (cont)

Avoid
aliasing:
sampling faster
than twice the
highest
frequency
component –
The Nyquist-
Shannon
sampling
theorem
Examples
Examples
Examples
Examples
 Lecture #14
Discrete-Time Fourier Transform (DTFT)

1. From CTFT to DTFT

2. Convergence of the DTFT
3. The relation between DTFT and ZT
4. DTFT of signals with poles on the unit circle
5. Inverse DTFT
 From CTFT to DTFT

Take a CT signal x(t) and sample it:


x(t ) sampling
  xs (t )   x(nT ) (t  nT )
n  
The CTFT of the sampled signal is:

FTx s ( t )   x(nT)FT(t  nT)
n  
 
 
n  
x (nT)  ( t  nT)e  jt dt

 T 1 
  x (
n  
nT ) e  jnT

T  
 x (
n  
n ) e  jn
 X ()
 DTFT formula


X()  DTFTx[n ]   x[n] e  j n

n  

• Discrete in time, but continuous in frequency and periodic

with period of 2
• Gives the complex frequency spectrum of DT signal
• Not all DTFT is converge
 Lecture #14
Discrete-Time Fourier Transform (DTFT)

1. From CTFT to DTFT

2. Convergence of the DTFT
3. The relation between DTFT and ZT
4. DTFT of signals with poles on the unit circle
5. Inverse DTFT
 Convergence of the DTFT
We always have:  

 x[n ]e
n  
 jn
  x[n ]e
n  
 jn


  x[n ] e
n  
 jn

 DTFT exists when:

  x[n ]
n  


 x[n ]  
absolutely
summable
n  
 Examples

1) Find DTFT of x(n) where x[n]  a u[n]

n

  j
1 e
X()   a e n  jn
  (ae ) 
 j n
 j
 DTFT nexists
0 when: n 0 1  ae  j
e a
if |a| < 1
 Examples

2) Find DTFT of x(n) where y[n]  a u[n]

n

0 
1 a
Y()  a e
n  
n  jn
  (a e ) 
n 0
1 j n

1 a e
1 j
 j
e a
if |a| > 1
 Examples

3) Find DTFT of p(n) where p[n]  u[n]  u[n  N ]

Show that this DTFT has a linear phase term
N 1
1 e  jN

P()  1.e  jn


n 0 1 e  j

Phase: -Ω(N-1)/2  linear in phase

 Examples

4) Find DTFT of h(n) where h[n]   [n]  2 [n 1]  2 [n  2]   [n  3]

Show that this DTFT has a linear phase term
3
H()   h[n ]e  jn
 1  2e  j
 2e  j2 
e  j3 

n 0

Phase: -3Ω/2  linear in phase

 Lecture #14
Discrete-Time Fourier Transform (DTFT)

1. From CTFT to DTFT

2. Convergence of the DTFT
3. The relation between DTFT and ZT
4. DTFT of signals with poles on the unit circle
5. Inverse DTFT
 From ZT to DTFT

Recall ZT of x(t):

X( z)   x[n]z
n  
n

Evaluating X(z) on the unit circle, if the unit circle is in the

ROC of X(z)


X( z )
z e j 
  x[n]e
n  
 j n
 X()
 From ZT to DTFT

DTFT is the Z-transform of x(n) evaluated on the unit circle

X ()  X ( z )
z e j 

If the ROC of the ZT contains the unit circle, we can get the
DTFT from the ZT by substitution z = ejΩ
 Example

Find DTFT of x(n) where x[n]  a u[n] n

z
X ( z)  ROC :| z || a |
za
 DTFT exists when ROC includes the unit circle, which
means |a| < 1:
e j
X ( )  X ( z )  j
z  e j e a
 Lecture #14
Discrete-Time Fourier Transform (DTFT)

1. From CTFT to DTFT

2. Convergence of the DTFT
3. The relation between DTFT and ZT
4. DTFT of signals with poles on the unit circle
5. Inverse DTFT
DTFT of signal with poles on the unit circle

DTFT of x[n] can be determined by evaluating its ZT

X(z) on the unit circle, provided that the unit circle lies
within the ROC, or none of poles is on the unit circle

Rescue: just extend the DTFT!!!

Allowing the DTFT to contain impulses at certain
frequencies corresponding to the location of the poles
 Examples
Ex1: Consider this signal x[n] = u[n]
z
X ( z)  ROC :| z | 1  DTFT does not exist
z 1
Evaluate X(z) on the unit circle, except at z = 1 = ejk2π:
j j / 2 j / 2 j / 2
e e .e e
X ()  j  j / 2 j / 2  j / 2    k 2
e  1 e (e e ) 2 j sin( / 2)

1
X ( )    k 2
2 | sin( / 2) |

At Ω = k2π, X(Ω) contains impulses

 Examples
Ex2: Consider this signal x[n] = (-1)nu[n]
z
X ( z)  ROC :| z | 1  DTFT does not exist
z 1
Evaluate X(z) on the unit circle, except at z = -1 = ej(2k+1)π

e j e j / 2 .e j / 2 e j / 2
X ()  j  j / 2 j / 2  j / 2    (2k  1)
e  1 e (e e ) 2 cos( / 2)

1
X ( )    (2k  1)
2 | cos( / 2) |

At Ω = (2k+1)π, X(Ω) contains impulses

 Examples
Ex3: Consider this signal x[n] = (cosΩ0n)u[n]
z  cos 0
X ( z)  2 ROC :| z | 1  DTFT does not exist
z  2 z cos 0  1

Evaluate X(z) on the unit circle, except at

 Lecture #14
Discrete-Time Fourier Transform (DTFT)

1. From CTFT to DTFT

2. Convergence of the DTFT
3. The relation between DTFT and ZT
4. DTFT of signals with poles on the unit circle
5. Inverse DTFT
 The inverse of DTFT

X()   x[ n
n  
] e  j n

 
1 1  
 j n  j l

2  
j l
X()e d    
2   n  
x[n ]e 

e d

  1  j ( l n ) 
  x[n ]  e d  x[l]
n    2   

1

j n
x[n ]  X() e d
2  
 Examples

1,    c
Ex1. Find x(n) from its DTFT X(Ω): X ( )  
0,  c    


1 c
1 jn c sin c n
x[n ]   1.e d  
jn c
.e c
2   c
2jn  c n
0.7

0.6

0.5

0.4

0.3

0.2

0.1

-0.1
-π -Ωc 0 Ωc π Ω -0.2
-20 -15 -10 -5 0 5 10 15 20
 Examples

Ex2. Find x(n) from its DTFT X(Ω): X()  cos 2 

2
 e  e  1 j2  1 1  j2 
j  j

X ()     e   e
 2  4 2 4
1 1 1
 x[n ]  [n  2]  [n ]  [n  2]
4 2 4
1 0.5

0.9 0.45

0.8 0.4

0.7 0.35

0.6 0.3

0.5 0.25

0.4 0.2

0.3 0.15

0.2 0.1

0.1 0.05

0 0
-2 0 2 -5 0 5
 Examples

e j
Ex3. Find x(n) from its DTFT X(Ω): X() 
e j  2

z
X(z)  | z | 2
z2
 x[n ]  2 u[n  1]
n
SUMMARY
Lecture #15
DTFT properties

1. Linearity
2. Time shifting
3. Frequency shifting and modulation
4. Differentiation in the frequency domain
5. Convolution in time domain
6. Convolution in frequency domain
7. Symmetry
 Linearity

DTFT
ax[n ]  by[n]  aX()  bY()

The DTFT of a linear combination of two or more signals is

equal to the same linear combination of the DTFT of the
individual signals.
 Example
n
Determine the DTFT of the signal x[n]  a if |a| < 1

a n  0
n
 1 
n

x[n ]   n  a u[n ]     u[n  1]

n

a n0   a  
z z 1
X ( z)   ROC :| a || z |
z  a z  1/ a |a |
j j j j
e e e ae
 X ()  j  j  j  j
e  a e  1 / a e  a ae  1
1  a2 1  a2
 j  j

1  ae  ae  a 2
1  2a cos   a 2
 Example (cont)
1 For a = 0.8

0.5

0
-20 -15 -10 -5 0 5 10 15 20

10

0
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
Lecture #15
DTFT properties

1. Linearity
2. Time shifting
3. Frequency shifting and modulation
4. Differentiation in the frequency domain
5. Convolution in time domain
6. Convolution in frequency domain
7. Symmetry
 Time shifting

DTFT
x[n  n 0 ]  e  j n 0
X()
Proof: infer from the shifting property of ZT, then
evaluate ZT on the unit circle
ZT
x[n  n 0 ]  z X(z) n 0

 A shift in time causes a linear phase shift in

frequency – no change in DTFT magnitude
Lecture #15
DTFT properties

1. Linearity
2. Time shifting
3. Frequency shifting and modulation
4. Differentiation in the frequency domain
5. Convolution in time domain
6. Convolution in frequency domain
7. Symmetry
 Frequency shifting and modulation
DTFT
e j 0 n
x[n ]  X (   0 )
DTFT
1 1
cos(0 n ) x[n ]  X (   0 )  X (   0 )
2 2
Proof:
DTFT  
e j 0 n
x[n]   (e
n  
j 0 n
x[n])e  jn
  x[ n
n  
]e  j (   0 ) n
 X (   0 )

1 j 0 n 1  j  0 n
cos( 0 n)  e  e  ...
2 2

Modulation causes a shift in frequency

 Example

y1[n]  x[n] cos 0.5n and y2 [n]  x[n] cos n

X(Ω)

-2π -π -π/2 0 π/2 π 2π Ω

Lecture #15
DTFT properties

1. Linearity
2. Time shifting
3. Frequency shifting and modulation
4. Differentiation in the frequency domain
5. Convolution in time domain
6. Convolution in frequency domain
7. Symmetry
 Differentiation in the frequency domain
DTFT dX ()
nx[n]  j
d

Proof: infer from the differentiation-in-the-z-domain property

of ZT, then evaluate ZT on the unit circle

Z dX ( z )
nx[n ]   z
dz
j dX () j dX () dX ()
DTFT
nx[n ]   e j
 e j
 j
d (e ) je d d
Lecture #15
DTFT properties

1. Linearity
2. Time shifting
3. Frequency shifting and modulation
4. Differentiation in the frequency domain
5. Convolution in time domain
6. Convolution in frequency domain
7. Symmetry
 Convolution in time domain

DTFT
x1[n ]  x 2 [n]  X1 ().X2 ()

Proof:

Infer from the convolution-in-time-domain property

of ZT, then evaluate ZT on the unit circle

Convolution in time  Multiplication in frequency

 Example
Given h[n] = anu[n], |a| < 1

Find its inverse system hi[n] but don’t use ZT

j
e
H ()  j
e a
j
e a  j
 H i()  j
 1  ae
e
 hi [n ]   [n ]  a [n  1]
Lecture #15
DTFT properties

1. Linearity
2. Time shifting
3. Frequency shifting and modulation
4. Differentiation in the frequency domain
5. Convolution in time domain
6. Convolution in frequency domain
7. Symmetry
 Convolution in frequency domain
DTFT
1 1
x1[n ].x 2 [n ]  
2 2 
X1 ()X 2 (  )d  X1 ()  X 2 ()
2
DTFT 
x1[n ].x 2 [n ]   1
( x
n  
[ n ].x 2
[ n ])e  jn

Multiplication 
 1 
in time    X (  ) e j n
d  2
x [ n ]e  jn

n    2 2  
1

1  x [n ] e  j(  ) n d

  X (  ) 2 
2 2   n  
1

1

2 2 
 X1
(  ) X 2
(    ) d Convolution in
frequency
Lecture #15
DTFT properties

1. Linearity
2. Time shifting
3. Frequency shifting and modulation
4. Differentiation in the frequency domain
5. Convolution in time domain
6. Convolution in frequency domain
7. Symmetry
 Symmetry properties
Consider x[n] and X(Ω) are complex-valued functions

X ()   x[
n  
n ]e  jn


 (x
n  
R [n ]  jx I [n ])(cos n  j sin n )

 X R ()  jX I ()

 X R()  (x
n  
R [n ] cos n  xI [n ] sin n )

 X I()    ( xR [n ] sin n  x I [n ] cos n )
n  
 Symmetry properties
Consider x[n] and X(Ω) are complex-valued functions

1

jn
x[n ]  X (  ) e d
2 

1

2 
[ X R ()  jX I ()](cos n  j sin n )d

 xR [n ]  jx I [n ]

1
 xR [n ] 
2 [ X

R () cos n  X I () sin n ]d


1
 x I [n ] 
2 [ X

R () sin n  X I () cos n ]d
 Real signal
x[n ]  xR [n ] and x I [n ]  0

 X R()   x[n] cos n  X
n  
( ) : even
R


 X I()    x[n ] sin n   X I( ) : odd
n  

 X * ()  X ( )
| X () | X 2 ()  X 2 () | X ( ) |: even
 R i
 X I ()
X ()  arctg  X ( ) : odd
 X R ()
 Real signal (cont)

x[n ] even :

X R ()  x[0]  2 x[n ] cos n; X I ()  0
n 1

1
x[n ] 
  X
0
R () cos n d

x[n ] odd :

X I ()  2 x[n ] sin n; X R ()  0
n 1

1
x[n ]  
  X
0
I () sin n d
 x[ n ] X ()
Symmetry x * [n ] X * ( )
properties x * [  n ]
X * ()
x R [n ] X e ()
jx I [n ] X o ()
xe [ n ] X R ()
xo [n ] jX I ()
X ()  X * ( )
any real signal | X () || X ( ) |
X ()  X ( )
real and even real and even
real and odd imaginary and odd
 Lecture #16
Frequency spectrum of DT signals

1. Frequency spectrum
2. Amplitude spectrum and phase spectrum
3. Energy spectral density (ESD)
4. Bandwidth
 Frequency spectrum

 Representation of the signal in the frequency domain

 Being generated via frequency analysis tools:
- CTFT for aperiodic CT signal
- CT Fourier series for periodic CT signal
- DTFT for aperiodic DT signal
- DT Fourier series for periodic DT signal
 Frequency spectrum analysis

 The technical process of decomposing a complex signal into

simpler parts.
 The process of quantifying the various amounts (e.g. amplitudes,
powers, intensities, or phases), versus frequency.
 Summary:
- Aperiodic CT signals have aperiodic continuous-frequency spectra
- Periodic CT signals have aperiodic discrete-frequency spectra
- Aperiodic DT signals have periodic continuous-frequency spectra
- Periodic DT signals have periodic discrete-frequency spectra
Frequency range of some biological signals
Type of signal Frequency range (Hz)
Electroretinogram 0-20
Pneumogram 0-40
Electrocardiogram (ECG) 0-100
Electroencephalogram (EEG) 0-100
Electromyogram 10-200
Sphygmomanogram 0-200
100-4000
Frequency range of some biological signals

Type of signal Frequency range (Hz)

Wind noise 100-1000
Seismic exploration signals 10-100
Earthquake and nuclear explosion signals 0.01-10
Seismic signals 0.1-1
 Frequency range of some EM signals
Type of signal Frequency range (Hz)
Radio broadcast 3x10-4 – 3x106
Shortwave radio signals 3x106 – 3x1010
Radar, satellite communications… 3x108 – 3x1010
Infrared 3x1011 – 3x1014
Visible light 3.7x1014 – 7.7x1014
Ultraviolet 3x1015 – 3x1016
X-rays 3x1017 – 3x1018
 Frequency spectrum representation

 Real and imaginary parts:

X ()  X R ()  jX I ()

 Absolute and argument:

 X () 
jarctg I 

X () | X () | e j (  )  [ X R ()]2  [ X I ()]2 e  R 
X ( )

 Magnitude and phase:

X ()  A()e j (  )
A() can be positive, negative or zero
 ()  2k if A()  0
 ()  
 ()  ( 2k  1) if A()  0
 Example

 Consider this even signal:

1,  2  n  2
x[n ]  
0, elsewhere
 Its frequency spectrum:
2
X ()  X R ()  1  2 cos n
n 1

 1  2 cos n  2 cos 2n

 Magnitude and phase:  A()  1  2 cos n  2 cos 2n
 ()  0
 Absolute and argument:| X () || 1  2 cos n  2 cos 2n |
0 if X ()  0
 ()  
 if X ()  0
 Lecture #16
Frequency spectrum of DT signals

1. Frequency spectrum
2. Amplitude spectrum and phase spectrum
3. Energy spectral density (ESD)
4. Bandwidth
 Amplitude spectrum and phase spectrum

j (  )
X ()  X () e
Amplitude spectrum Phase spectrum
 
X ( )   x[n]e
n  
 jn
; X (  )   x[n]e
n  
jn

 X ( )  X (  )
*

 | X() || X() | and X()  X()

 Example

Find and plot amplitude spectrum and phase spectrum:

x[n] = u[n] - u[n - 4]

 Using Matlab to plot amplitude
spectrum and phase spectrum

w = -2*pi:pi/255:2*pi; % freq. -2π  2π, resolution of π/255

X =4*sinc(2*w/pi)./sinc(w/(2*pi)).*exp(-j*1.5*w);
subplot(2,1,1);
plot(w/pi,abs(X)); % plot amplitude spectrum
subplot(2,1,2);
plot(w/pi,phase(X)); % plot phase spectrum
 Amplitude spectrum
6

0
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

-2

-4
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

Phase spectrum
 Lecture #16
Frequency spectrum of DT signals

1. Frequency spectrum
2. Amplitude spectrum and phase spectrum
3. Energy spectral density (ESD)
4. Bandwidth
 Energy spectral density (ESD)


    1 
E   | x[n] |   x[n]x [n]   x[n]
2 *
 X
*
()e  jn
d
n   n   n    2  

Changing the order of summation & intergral:

 
1  
 jn  1
E  X ()   x[n ]e d   X() d
* 2

2    2  
n  
Energy spectral density
 Example

Given x[n] = anu[n], -1<a<1

1
X ( ) 
1  ae  j
 Example
3

2.5
mat do pho nang luong

E
S 1.5

D
1

0.5

0
-3 -2 -1 0 1 2 3
tan so omega
 Lecture #16
Frequency spectrum of DT signals

1. Frequency spectrum
2. Amplitude spectrum and phase spectrum
3. Energy spectral density (ESD)
4. Bandwidth
 Bandwidth of a signal

 Bandwidth: the range of frequencies over which

the power or energy density spectrum is
concentrated.
 Ex: a signal has 95% of its ESD or PSD concentrated
in the range from F1 to F2 then the 95% bandwidth
of the signal is (F2-F1).
 Similarly, we may define 75% or 90% or 99%
bandwidth of the signal
 Frequency-domain classification of signals

 Low-frequency signal: PSD or ESD concentrates about zero

frequency
 High-frequency signal: PSD or ESD concentrates at high
frequencies
 Bandpass signal: PSD or ESD concentrates somewhere in the
broad frequency range between low frequency and high frequency
- Narrowband signal: the bandwidth (F2-F1) is much smaller (by a
factor of 10+) than (F1+F2)/2
- Wideband signal
 Frequency-domain classification of signals

Low-frequency High-frequency
signal signal

Ω Ω

Narrowband signal Wideband signal

Ω Ω
Lecture #17
Frequency-domain characteristics of LTI systems

1. Frequency response function

2. Response to complex exponential and sinusoidal
signals
3. Steady-state and transient response
4. Response to aperiodic input signals
 Frequency response

 For impulse response, h(n), its DTFT is often called frequency

response H(Ω)
 H(Ω) completely characterizes a LTI system in the frequency
domain
 H(Ω) allows us to determine the steady-state response of the
system to any arbitrary weighted linear combination of sinusoids or
complex exponential
 H(Ω) exists if the system is BIBO stable

H ()  H () e j ()

Amplitude response Phase response

 Determination of frequency response
1. From impulse response: Just take DTFT of h[n]

2. From difference equation:

- Take DTFT for both side
- Put the Y(Ω) on left side
- Divide both side by X(Ω)

3. From block diagram:

(1) Find the difference equation, then find H(Ω) from equation
(2) Put X(Ω)=1 as input, then directly find Y(Ω)=H(Ω)

4. From transfer function:

Evaluate H(z) on the unit circle
 Example of frequency response

 A LTI causal system is described by the following equation:

y[n]  0.1y[n 1]  0.85 y[n  2]  x[n]  0.3x[n 1]

 First, checking the stability of the system (by using Matlab):
b = [1 -0.3];
a = [1 0.1 0.85];
zplane(b,a) % plot zeros and poles to check if all poles are
inside the unit circle

 Second, take DTFT for two sides:

1  0.3e  j
H () 
1  0.1e  j  0.85e  j 2
Example of amplitude and phase responses
1
H() 
1  0.4e  j
Example of amplitude and phase responses
1
H() 
1  0.4e  j
2

1.5

0.5
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

0.5

-0.5
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
 Example of moving average filter
1
y[n ]  ( x[n  1}  x[n ]  x[n  1])
3
1 j  j 1
H ()  ( e  1  e )  (1  2 cos )
3 3
Hence
1
| H () | | 1  2 cos  |
3
0, 0    2 / 3
H ()  
 , 2 / 3    
Example of moving average filter
1

0.5

0
0 0.2 0.4 0.6 0.8 1

0
0 0.2 0.4 0.6 0.8 1
Lecture #17
Frequency-domain characteristics of LTI systems

1. Frequency response function

2. Response to complex exponential and
sinusoidal signals
3. Steady-state and transient response
4. Response to aperiodic input signals
Response to complex exponential signals


x[n]  Ae j0 n
,   n   y[n ]   h[k] x[n  k]
k  

 

y[n]   h[ k
k  
] Ae j 0 ( n  k )

 
 A  h[k ] e  
 j 0 k  j  0 n
e
k   
j 0 n
 ( Ae ) H ( 0 )  x[n]H ( 0 )

y[n]  x[n]H (0 )  Ae j0n H (0 )

eigenfunction eigenvalue
 Example
Determine the output signal of system h[n]  (1 / 2) n u[n]

j n
to this input signal x[n ]  Ae 2
,   n  

1
H ()   h[n ]e  jn

1  j
n   1 e
2
   1 2  j 26.60
At n  : H     e
2  2  1 j 2
1
5

    
2  j26.6 2A
j n j n  26.60 
y[n ]  x[n ]H   Ae . e 
0
2 
2
e
2 5 5
 Response to sinusoidal signals
A j n A  j n
x[n ]  A cos(0 n )  e  e 0
, n  0

2 2
A j0n A  j0n
y[ n ]  e H (  0 )  e H (  0 )
2 2
A j0n jH ( 0 ) A  j0n
 e | H (0 ) | e  e | H (0 ) | e  jH ( 0 )
2 2
A
 | H (0 ) | e e
2

j0n jH ( 0 )
e  j0n  jH ( 0 )
e 
y[n]  A | H (0 ) | cos0n  H (0 )
 Example

Determine the response of the system h[n]  (1 / 2) n u[n]

to the input signal

x[n ]  10  5 sin n  20 cos n,    n  
2
 One more example

 A LTI causal system is described by the following equation:

y[n] = ay[n-1] + bx[n], a real and 0<a<1
a) Determine the amplitude and phase responses
b) Choose b so that the maximum value of |H(Ω)| is unity,
and sketch |H(Ω)| and <H(Ω) for a = 0.9
c) Determine the output of the system to the input:

  
x[n]  5  12 sin n  20 cos  n  ,    n  
2  4
 One more example

a) The frequency response is:

b
H ( ) 
1  ae  j
The amplitude response and phase response are:
 One more example

Choose a = 0.9 and b = 1-a :

1 a 0.1
| H () | 
1  a 2  2a cos  1.81  1.8 cos 
0.9 sin 
H ()  0  arctg
1  0.9 cos 
 One more example
b) 1

0.5

0
0 0.2 0.4 0.6 0.8 1

-0.5

-1

-1.5
0 0.2 0.4 0.6 0.8 1
 One more example
c) The amplitude and phase response at Ω=0, π/2, and π
respectively:

The output:
Lecture #17
Frequency-domain characteristics of LTI systems

1. Frequency response function

2. Response to complex exponential and sinusoidal
signals
3. Steady-state and transient response
4. Response to aperiodic input signals
 Steady-state and transient response

The system response can be considered as a sum of 2 terms:

y[n]  yss[n]  ytr [n]

yss[n]: steady-state response
.

ytr[n]: transient response, decays toward zero as n  ∞

In many practical applications, the transient response is
unimportant and therefore, it is usually ignored
 Example

The LTI system described by first-order equation:

y[n]  ay[n  1]  x[n] |a| < 1

jn
Its response to the input: x[n]  Ae ,n0
is determined as
.

n 1  j ( n 1)
Aa e A
y[n ]  a y[1] 
n 1
e jn
 e jn
, n0
1  ae  j 1  ae  j

where y[-1] is the initial condition

 Example

n 1  j ( n 1)
Aa e A
y[n ]  a y[1] 
n 1
e jn
 e jn

1  ae  j
1  ae  j

Transient response Steady-state response

yss[n]  AH ()e jn

 AH (e )e j jn

M M
x[n ]   A k z n
k  yss[n ]   A k H(z k )z n
k
k 1 k 1
Lecture #17
Frequency-domain characteristics of LTI systems

1. Frequency response function

2. Response to complex exponential and sinusoidal
signals
3. Steady-state and transient response
4. Response to aperiodic input signals
 Response to aperiodic input signals
x[n] y[n]
LTI
X(Ω) Y(Ω)

 From the convolution property, we have:

Y ( )  X ( ) H ( ) For   0 :
| Y () || X (
. ) || H ( ) | | Y (0 ) || X (0 ) || H (0 ) |
Y ()  X ()  H () Y (0 )  X (0 )  H (0 )

 The LTI system attenuates some frequency components and

amplifies other frequency components of the input
 The output can’t contain frequency components that are not
contained in the input
 Example
 A LTI causal system is described by the following equation:
y[n] – 0.5y[n-1] = x[n]
Determine the spectrum and the ESD of the output when the
n
input signal is: 1
x[n ]    u[n ]
4
 The frequency response: H ()  1
1  12 e  j
The input spectrum: 1
 X () 
1  14 e  j
The output spectrum: 1
Y ()  X (). H () 
1  14 e j 1  12 e j 


1
ESD | Y () |  2

 45  cos  1716  12 cos  

 Example

1.6 2

1.4
X(Ω) 1.5 H(Ω)
1.2
1
1

0.8 0.5
0 0.5 1 0 0.5 1

3 80
Y(Ω) 60 ESD
2
40
1
20

0 0
0 0.5 1 0 0.5 1
Lecture #18
Digital filters

1. Digital filters
2. Ideal filters
 Filters

 Provide a convenient means to change the nature of a signal.

 Change the frequency characteristics of a signal in a specific way,
letting some frequencies in the signal pass while blocking others
 4 basic types:
.
- Low pass filter (LPF): lets low frequencies pass while blocking
high frequencies
- High pass filter (HPF): does the opposite
- Band pass filter (BPF): allows a band of frequencies to pass
- Band stop filter (BSF): block all frequencies inside a band
 Digital filters

 DT systems that perform mathematical operations on

a DT signal to reduce or enhance certain aspects of that
signal.
 Digital filters are difference equations defined by a list
of filter coefficients
.

 Ex: Moving average filter:

y[n] = 1/3{x[n+1]+x[n]+x[n-1]}
 Typical applications of digital filters

 Noise suppression: radio signal, biomedical signal, analog

media signal...
 Enhancement of selected frequency range: treble/bass
control, equalizers in audio, image edge enhancement…
 Bandwidth limiting:
.
aliasing prevention, interference
avoidance…
 Removal of specific frequencies: DC removal, 60 Hz signal
removal, notch filter…
 Special operations: differentiation, integration, phase shift…
Example of signal after lowpass filtering

.
Example of signal after highpass filtering

.
Lecture #18
Digital filters

1. Digital filters
2. Ideal filters
 Ideal digital filters

Cx[n  n 0 ], 1    2
y[n ]  
0 , 

Y()  CX()e  j n 0
 X()H(), 1    2

Ce  j n , 1    2
0

H ( )  
0,  
| H() | C, 1    2 - Constant gain
()   n 0 , 1    2 - Linear phase
 Amplitude responses for some
ideal digital filters
| H() | | H() |

 
c c

| H() | | H() |

 
a b a b
 Ideal digital lowpass filters

1,   c
Frequency response: H L ( )  
0, c    


c
1 c sin c n
 1.e
jn
hL [n]  d 
2 c
 c n
0.7

0.6

0.5

0.4

0.3

0.2

0.1

-0.1
-π -Ωc 0 Ωc π Ω -0.2
-20 -15 -10 -5 0 5 10 15 20
 Ideal digital highpass filters
Frequency response: 1, c    

H H ( )  
0,   c


sin  n c sin c n
H H ()  H L 2 ()  H L1 ()  h[n]  
n  c n
0.4

HL1
HL2
0.3

0.2

0.1

-0.1

-π -Ωc 0 Ωc π Ω -0.2

-0.3
-20 -15 -10 -5 0 5 10 15 20
 Ideal digital bandpass filters
Frequency response: 1, c1    c 2  
H B ( )  
0, elsewhere

c 2 sin c 2n c1 sin c1n

H H ()  H L 2 ()  H L1 ()  h[n]  
 c 2 n  c1n
0.1

HL1 0.08

HL2 0.06

0.04

0.02

-0.02

-0.04

-π -Ωc2 0 Ωc1 π Ω -0.06

-0.08
-20 -15 -10 -5 0 5 10 15 20
 Ideal digital bandstop filters
1,   c1
Frequency response: 
H B ()  0, c1    c 2

1, c 2    
c1 sin c1n c 2 sin c 2n
H H ()  H L ()  H H ()  h[n]    [n ] 
 c1n  c 2 n
0.6

HH HL 0.5

0.4

0.3

0.2

0.1

-π -Ωc2 0 Ωc1 π Ω 0

-0.1
-20 -15 -10 -5 0 5 10 15 20
Amplitude responses for some actual digital filters
 CHAPTER 5:
DISCRETE FOURIER TRANSFORM (DFT)

Lesson #19: DTFT of DT periodic signals

Lesson #20: DFT and Inverse DFT
Lesson #21: DFT properties
Lesson #22: Fast Fourier Transform (FFT)
Lesson #23: Applications of DFT/FFT
Lesson #24: Using of DFT/FFT
 Lecture #19
DTFT of periodic signals

1. Review of Fourier Transforms (FT)

2. Fourier Series expansions
3. DTFT of periodic signals
 FT of CT periodic signals

1 2
x(t )  a e
k  
k
jk0t
; ak   x(t )e
TT
 jk0t
dt; 0 
T

Continuous and periodic Discrete and aperiodic in

in time domain frequency domain
 FT of CT aperiodic signals

Continuous and aperiodic Continuous and aperiodic in

in time domain frequency domain
 FT of DT aperiodic signals

Discrete and aperiodic Continuous and periodic in

in time domain frequency with period 2π
Recapitulation
Can guess?
 Lecture #19
DTFT of periodic signals

1. Review of Fourier Transforms (FT)

2. Fourier Series expansions
3. DTFT of periodic signals
 Fourier Series expansion

• CT periodic signals with period T:


1 2
x(t )  a e
k  
k
jk0t
; ak   x(t )e  jk0t dt
TT
0 
T

• DT periodic signals with period N:

1 2
x[n]  a e
k N 
k
jk0 n
; ak 
N
 x[n]e
n N 
 jk 0 n 0 
N

Note: finite sums over an interval length of one periodic N

2 2
jk n j( k  N ) n
e jk0 n
e N
e N
e j( k  N ) 0 n
 Example of Fourier Series expansion

Given a DT periodic signals with period N: p[n]    [n  kN ]

k 

. . . -2N -N 0 N 2N . . . . .
N 1 2
p[n]   ak e
jk n
N

k 0

1 N1 1
a k   p[n ]e  jk 2 n / N

N n 0 N
 Lecture #19
DTFT of periodic signals

1. Review of Fourier Transforms (FT)

2. Fourier Series expansions
3. DTFT of periodic signals
 DTFT of periodic signals

• CT periodic signals with period T:

 F 
x(t)  a e
k  
k
jk0 t
 X()  2  a k (  k0 )
k  

• DT periodic signals with period N:

F 
x[n ]  X()  2  a k (  k0 )
k  
 Example of calculating DTFT of
periodic signals
Height = 1
Spacing = N

. . . -2N -N 0 N 2N . . . . . . . . n


2   2 
P()  2  a k   k0       k 
k   N k   N
2π/N 2π/N 2π/N 2π/N 2π/N Height = 2π/N
Spacing = 2π/N

. . . -4π/N -2π/N 0 2π/N 4π/N . . . . Ω

 Another approach to get DTFT of
periodic signals

x(n) is periodic signal; x0(n) is a part of x(n) that is repeated

0 N-1

 x[n] 0  n  N  1
x0 [n]  
 0 otherwise
 Another approach (cont)

 x[n] 0  n  N  1
x0 [n]  
 0 otherwise

  
x[n]   x [n  kN ]   x [n]   [n  kN ]  x [n]    [n  kN ]
k 
0
k 
0 0
k 

p(n) in previous
example
F
x[n]  x0 [n]  p[n]  X 0 () P()  X ()
 Another approach (cont)
F
x[n]  x0 [n]  p[n]  X 0 () P()  X ()

 2 2 
X ()  X 0 ()
 N k
  (  k ) 
N 
2 2 2

N k
 X 0 (k
N
) (  k
N
)

 It has N distinct values at k = 0, 1, …, N-1

 Inverse DTFT
2
DFT X ()  x[n ] 
1

1 jn
X (  ) e d
2 0
2
1  2 
2 2  jn

2 0  N 
k  
X 0 (k
N
) (  k )e d
N 
2 k 2n
1 
2 2 jn 1 N 1
2 j

N

k  
X 0 (k
N 0
)   (  k
N
)e d 
N

k 0
X 0 (k
N
)e N

This is obtained from this property of the impulse:

b
 f (t0 ) a  t0  b

a
f (t ) (t  t0 )dt  
0 elsewhere
Summary
 Procedure to calculate DTFT of
periodic signals

Step 1:
Start with x0(n) – one period of x(n), with zero everywhere else
Step 2:
Find the DTFT X0(Ω) of the signal x0[n] above
Step 3:
Find X0(Ω) at N equally spacing frequency points X0(k2π/N)
Step 4:
2 2 2
Obtain the DTFT of x(n): X () 
N
k X 0 (k N ) (  k N )
Example of calculating DTFT of
periodic signals

0 1 2 3
3
X 0 ()   x0 (n)e  jn
 1 e  j
 2e  j 3

n 0

k = 0  X0(0) = 4; k = 1  X0(1) = 1+j

k = 2  X0(2) = -2; k = 3  X0(3) = 1-j
Example (cont)
Example (cont)
 DTFT and DFS example

a) Draw the magnitude plot of the FT of a CT sinusoid x(t), that

has a frequency of 24 Hz
b) Sample this signal x(t) at 40 Hz. Draw the magnitude plot of
the FT of the sampled signal
c) Reconstruct a CT signal from the samples above with a LPF, it
will look like a CT sinusoid of what frequency?
d) Consider DT signal that is obtained by the sampling x(t) at a
sampling frequency of 40 Hz is x(n). Is x(n) a periodic signal?
If yes, what is its period?
e) Specify the DTFT of the DT signal x(n).
 DTFT and DFS examples
a) Draw the magnitude plot of the FT of a CT sinusoid x(t), that has
a frequency of 24 Hz
 DTFT and DFS examples
b) Sample this signal x(t) at 40 Hz. Draw the magnitude plot of the
FT of the sampled signal
 DTFT and DFS examples
c) Reconstruct a CT signal from the samples above with a LPF, it will
look like a CT sinusoid of what frequency?
 DTFT and DFS examples

d) Consider DT signal that is obtained by the sampling x(t) at

a sampling frequency of 40 Hz is x(n). Is x(n) a periodic
signal? If yes, what is its period?
 DTFT and DFS examples

e) Specify the DTFT of the DT signal x(n).

 Lecture #20
DFT and inverse DFT

1. DFT and inverse DFT formulas

2. DFT and inverse DFT examples
3. Frequency resolution of the DFT
 DFT to the rescue!

Could we calculate the frequency spectrum of a signal

using a digital computer with CTFT/DTFT?

 Both CTFT and DTFT produce continuous function of

frequency  can’t calculate an infinite continuum of frequencies
using a computer

 Most real-world data is not in the form like anu(n)

DFT can be used as a FT approximation that can calculate a finite

set of discrete-frequency spectrum values from a finite set of
discrete-time samples of an analog signal
 Building the DFT formula
Continuous time
signal x(t)
“Window” x(n) is like multiplying
the signal by the finite length
sample
rectangular window

Discrete time
signal x(n)

window

Discrete time
signal x0(n)
Finite length
 Building the DFT formula (cont)
Continuous time
signal x(t)

sample

Discrete time
signal x(n)
 N 1

window X 0 ()  0
x [ n
n  
]e  jn
 0
x [
n 0
n ]e  jn

DTFT
Discrete time
signal x0(n)
Finite length
 Building the DFT formula (cont)
Continuous time
signal x(t)
Discrete Fourier Transform DFT X(k)
Discrete + periodic with period N
sample
Sample
Discrete time at N
signal x(n) values
around
window the unit
circle

DTFT
Discrete time X0(Ω)
signal x0(n) Continuous + periodic
Finite length with period 2π
Notation conventions
Notation conventions (cont)
 DFT and inverse DFT formulas
2
j
Notation WN  e N

You only have to store N points

 Lecture #20
DFT and inverse DFT

1. DFT and inverse DFT formulas

2. DFT and inverse DFT examples
3. Frequency resolution of the DFT
 DFT and IDFT examples

Ex.1. Find the DFT of x(n) = 1, n = 0, 1, 2, …, (N-1)

k = 0  X(k) = X(0) = N
k ≠ 0  X(k) = 0
 DFT and IDFT examples

Ex.2. Given y(n) = δ(n-2) and N = 8, find Y(k)

 DFT and IDFT examples

Ex.3. Find the IDFT of X(k) = 1, k = 0, 1, …, 7.

 DFT and IDFT examples

Ex.4. Given x(n) = δ(n) + 2δ(n-1) +3δ(n-2) + δ(n-3) and

N = 4. Find X(k).
 DFT and IDFT examples

Ex.5. Given X(k) = 2δ(k) + 2δ(k-2) and N = 4. Find x(n).

 DFT in matrix forms
N 1
X [k ]   x[n ]WNkn k  0,1,..., N  1
n 0

Let ' s define :

 x[0]   X [ 0]  The N-point DFT
 x[1]   X [1]  may be expressed
xN    XN    in matrix form as:
     
   
 x[ N  1]  X [ N  1] XN = WNxN
1 1 1 1 
 1 2 ( N 1) 
 1 W WN WN 
WN 
N
 
 N 1 2 ( N 1) ( N 1)( N 1)

1 WN WN WN 
 IDFT in matrix forms
1 N 1
x[n ]   X [k ]WNkn n  0,1,..., N  1
N k 0
Let ' s define :
The N-point DFT
 x[0]   X [ 0]  may be expressed
 x[1]   X [1]  in matrix form as:
xN    XN   
      1 *
    1
xN  W X N  WN X N
 x[ N  1]  X [ N  1]
N
N
1 1 1 1   WNWN*  NI N
 1 2 ( N 1)  I N : identity matrix
 1 W WN WN 
WN 
N
 
 N 1 2 ( N 1) ( N 1)( N 1)

1 WN WN WN 
Example of calculation of DFT in matrix form
Let ' s define :
0 
Find DFT of the signal 1 
x4  
x[n] = 2
 
δ[n-1] + 2δ[n-2] + 3δ[n-3] 3 
1 1 1 1  1 1 1 1 
 
 1 W41 W42 W43  1  j  1 j 
W4   
1 W42 W44 W46
1  1 1 1
   
1 W43 W46 W4  1 j
9 1  j
6 
 2  2 j 
Then X 4  W4 . x 4   
 2 
 
  2  2 j 
 Lecture #20
DFT and inverse DFT

1. DFT and inverse DFT formulas

2. DFT and inverse DFT examples
3. Frequency resolution of the DFT
 Frequency resolution of the DFT
Discrete frequency spectrum computed from DFT has the
spacing between frequency samples of:

fs 2
f   
N N
 The choice of N determines the resolution of the frequency
spectrum, or vice-versa

 To obtain the adequate resolution:

1. Increasing of the duration of data input to the DFT

2. Zero padding, which adds no new information, but effects a better

interpolator
 Examples of N = 5 and N = 15

0
0 0.5 1 1.5 2 2.5 3 3.5 4

0
0 1 2 3 4 5 6 7 8 9 10

0
0 5 10 15 20 25 30
 Examples of N = 15 and N = 30
6

0
0 0.5 1 1.5 2 2.5 3 3.5 4

0
0 5 10 15 20 25 30

0
0 10 20 30 40 50 60
Lecture #21
DFT properties

1. Periodicity and Linearity

2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parseval’s theorem
 DFT properties

x(n) N periodic extension xp(n) DTFT Xp(Ω)

Finite length Periodic Periodic
truncate DTFT-1
DFT-1
DFT

X(k)
N periodic extension Xp(k)
Finite length
Periodic
truncate
 DFT properties

x(n) N periodic extension xp(n) DTFT Xp(Ω)

Finite length Periodic Periodic
truncate DTFT-1
DFT-1
DFT

X(k)
N periodic extension Xp(k)
Finite length
Periodic
truncate
 Periodicity

If x[n] and X[k] are an N-point DFT pair, then

x[n+N] = x[n] for all n

X[k+N] = X[k] for all k

 Linearity

DFT
a1 x1[n]  a2 x2 [n]  a1 X 1[k ]  a2 X 2 [k ]

Note: The length of x1[n] is same with the length of x2[n]

Proof:

Infer from the definition formula of DFT

Lecture #21
DFT properties

1. Periodicity and Linearity

2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parseval’s theorem
 Circular time shift property

DFT
x[n  m]  W X[k ] km

Proof:
Infer from the relation between DFT and DTFT
DTFT
x[n  m]  e  jm X ()
2
k :
N
2
 jk m
e  jm X ()  e N
X [k ]  W km X [k ]
 x(n)

Circular
xp(n)
time
xp(n+2)
shift

x(n+2)

Circular shift by m is the same as a shift by m modulo N

Lecture #21
DFT properties

1. Periodicity and Linearity

2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parseval’s theorem
 Circular frequency shift property

DFT
ln
x[n]W  X [k  l ]

Proof:
Similar to the circular time shift property
Lecture #21
DFT properties

1. Periodicity and Linearity

2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parseval’s theorem
 Circular convolution property

DFT N 1
X 1[k ]. X 2 [k ]  x1[n]  x2 [n]   x1[ p]x2 [n  p]
p 0

 The non-zero length of x1(n) and x2(n) can be no longer

than N
 The shift operation is circular shift
 The flip operation is circular flip

The circular convolution is not the linear convolution in chapter 2

 Direct method to calculate circular
convolution

1. Draw a circle with N values of x(n) with N equally spaced angles

in a counterclockwise direction.
2. Draw a smaller radius circle with N values of h(n) with equally
spaced angles in a clockwise direction. Superimpose the centers of 2
circles, and have h(0) in front of x(0).
3. Calculate y(0) by multiplying the corresponding values on each
radial line, and then adding the products.
4. Find succeeding values of y(n) in the same way after rotating the
inner disk counterclockwise through the angle 2πk/N
Example to calculate circular convolution

Evaluate the circular convolution, y(n) of 2 signals:

x1(n) = [ 1 2 3 4 ]; x2(n) = [ 0 1 2 3 ]
1 1

0 1
2 3 1 4 2 0 2 4
2 3

3 3

y(0) = 16 y(1) = 18
 Example (cont)

Evaluate the circular convolution, y(n) of 2 signals:

x1(n) = [ 1 2 3 4 ]; x2(n) = [ 0 1 2 3 ]
1 1

2 3
2 1 3 4 2 2 0 4
0 1

3 3

y(2) = 16 y(3) = 10
Another method to calculate circular convolution

x1(n) DFT X1(k)

IDFT y(n)

x2(n) DFT X2(k)

Ex. x1(n) = [ 1 2 3 4 ]; x2(n) = [ 0 1 2 3 ]

X1(k) = [ 10, -2+j2, -2, -2-j2 ];
X2(k) = [ 6, -2+j2, -2, -2-j2 ];
Y(k) = X1(k).X2(k) = [ 60, -j8, 4, j8 ]
y(n) = [ 16, 18, 16, 10 ]
Lecture #21
DFT properties

1. Periodicity and Linearity

2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parseval’s theorem
 Multiplication

DFT N 1
1 1
x1[n]. x2 [n]  X 1[k ]  X 2 [k ] 
N N
 X [l ] X [ k  l ]
l 0
1 2

 The non-zero length of X1(k) and X2(k) can be no longer

than N
 The shift operation is circular shift
 The flip operation is circular flip
Lecture #21
DFT properties

1. Periodicity and Linearity

2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parseval’s theorem
 Parseval’s theorem

 The general form:

N 1 N 1
1

n 0
x[n] y * [n] 
N
 X [k ]Y * [k ]
k 0

 Special case:

N 1 N 1
1

n 0
| x[n] | 
2

N
 |
k 0
X [ k ] |2
 Parseval’s theorem example

Given x(n) = δ(n) + 2δ(n-1) +3δ(n-2) + δ(n-3) and N = 4.

N 1

 |
n 0
x[ n ] |2
 12
 2 2
 32
 12
 15
N 1
1 1 2 60
N

k 0
| X [k ] |  (7  2  1  1  2  1 ) 
2

4
2 2 2 2 2

4
 15
 Lecture #22
Fast Fourier Transform (FFT)

1. What is FFT?
2. The decomposition-in-time Fast Fourier
Transform algorithm (DIT-FFT)
3. The decomposition-in-frequency Fast
Fourier Transform algorithm (DIF-FFT)
 Recall DFT and IDFT definition

N 1
X[k ]   x[n ]W nk
N 0  k  N 1 Nth complex
root of unity:
n 0
2
j
1 N 1 WN  e
x[n ]   X[k ]WN nk
N
0  n  N 1
N n 0

Using some "tricks" and choosing the appropriate N value, the DFT
can be implemented in a very computationally efficient way – this is
the Fast Fourier Transform (FFT) - which is the basis of lots of
contemporary DSP hardware
 Fast Fourier Transform (FFT)

 What does it take to compute DFT or IDFT?

N2 complex multiplications for all N points of X(k) or x[n]
 FFT: the algorithm to optimize the computational process by
breaking the N-point DFT into smaller DFTs
 Ex.: N is a power of 2: split N-point DFT into two N/2-point DFTs,
then split each of these into two of length N/4, etc., until we
have N/2 subsequences of length 2
 Cooley and Tukey (1965):

N
 log N complex multiplications
2
N 2 2
Comparison of DFT and FFT efficiency
10000
Complex multiplication numbers

8000

6000

4000

2000

FFT
0

N
-2000
0 10 20 30 40 50 60 70 80 90 100
 Comparison of DFT and FFT efficiency

Number of Complex multiplications Complex multiplications Speed improvement

points N in direct DFT in FFT factor

4 16 4 4.0
8 64 12 5.3
16 256 32 8.0
32 1,024 80 12.8
64 4,096 192 21.3
128 16,384 448 36.6
256 65,536 1,024 64.0
512 262,144 2,304 113.8
1024 1,048,576 5,120 204.8
 FFT (cont)
 Some properties of W  can be exploited in performing
nk
N
FFT:

W
k ( N n)
N
W N
 kn
  *
 W kn , complex conjugate symmetry
N
k ( n N ) (k  N )n
W N W N
kn
W N
, periodicit y in n and k

 Other useful properties:

N
(k  )n
nN
 jn
 kn
W N , if n even
W N W W N e 
kn kn
W 2 2

W N , if n odd
kn

N N

W
2 kn kn
W N
N
2
 Lecture #22
Fast Fourier Transform (FFT)

1. What is FFT?
2. The decomposition-in-time Fast
Fourier Transform algorithm (DIT-FFT)
3. The decomposition-in-frequency Fast
Fourier Transform algorithm (DIF-FFT)
 DIT-FFT with N as a 2-radix number

 We divide X(k) into 2 parts:

X [k ]  
neven
x[n]W kn   x[n]W kn
nodd

X(k)  G(k)  WN H(k), k  0,1,..., N  1

k

 G(k) is N/2 points DFT of the even numbered data: x(0),

x(2), x(4), …., x(N-2).
 H(k) is the N/2 points DFT of the odd numbered data:
x(1), x(3), …, x(N-1).
 DIT-FFT (cont)
N 1 N 1

X [k ]   x[2m]W 2 mk   x[2m  1]W k (2 m1) 

2 2

m0 m0
N 1 N 1

 
2 2

= x[2 m](W 2 mk
)  W k
x[2 m  1](W ) 
2 mk

m0 m0

Note: W  e
2
N

 j2  / N 2
e  j 2  /( N / 2 )
 WN / 2
N
1 N
1

X (k )   g[m]W  h[m]W
2 2

W  G(k )  W N H (k )
mk k mk k
N /2 N N /2
m 0 m 0

G(k) and H(k) are of length N/2; X(k) is of length N

G(k)=G(k+N/2) and H(k)=H(k+N/2)
 DIT-FFT of length N = 8

X[k]8  G[k]4  W H[k]4

8
k

X[0]  G[0]  W H[0]

8
0
X[4]  G[0]  W H[0]
8
4

X[1]  G[1]  W H[1]

1
8 X[5]  G[1]  W H[1]
8
5

X[2]  G[2]  W H[2]

8
2
X[6]  G[2]  W H[2]
8
6

X[3]  G[3]  W83H[3] X[7]  G[3]  W87 H[3]

Signal DFT
flow N=4
graph
for
8-point
FFT
DFT
N=4

# complex multiplications are reduced: 82 = 64  2x(4)2 + 8 = 40

 DIT-FFT of length N = 4

X [k ]4  G[k ]2  W H [k ]2
4
k

x[0]
X [0]  G[0]  W40 H [0]
X [0]  G[0]  W40 H [0]
X [1]  G[1]  W41H [1] W0
DFT
X [2]  G[0]  W H [0]
4
2

NX [3=]  G2[1]  W H [1]

3
X [1]  G[1]  W41H [1]
x[2] 4

W1

x[1] X [2]  G[0]  W42 H [0]

W2
DFT
N=2 X [3]  G[1]  W43H [1]
x[3]
W3

# multiplications are reduced: 42 = 16  2x(2)2 + 4 = 12

 DIT-FFT of length N = 2
1 2
j
X [k ]   x[n ]W nk , 0  k  1, W  e 2
 1
n 0

 X [0]  x[0]W 0.0  x[1]W 1.0  x[0]  x[1]

X [1]  x[0]W 0.1  x[1]W 1.1  x[0]  x[1]

Butterfly diagram x[0] X[0]

# multiplications are
reduced: 22 = 4  0;
just 2 additions!!! x[1] -1 X[1]
Example
DFT
of N=4

8-point

FFT

DFT
N=4

First step: split 8-point DFT into two 4-point DFTs

 G[0]
W0
Example DFT N = 2
G[1]
W2
of G[2]
W4
DFT N = 2
G[3]
8-point W6

0
H[0]
W0 W
FFT DFT N = 2
H[1]
W2

(cont) W0 H[2]
W4
DFT N = 2
H[3]
W6

Second step: split each of 4-point DFT into two 2-point DFTs
 W0 W0
Example
W2 W1
of
W4 W2

8-point W6 W3

W0 W0 W4
FFT
W2 W5

(cont) W0
W4 W6

W6 W7

Third step: combine all signal flow graphs of step 1 and step 2

There are 3 = log28 stages; 4 butterfly diagrams in each stage

Butterfly diagram

Wr -1

Wr+N/2 = -Wr
The
overall
signal
flow
graph
for
8-point
DIT-FFT
Now the overall computation is reduced to:

N
 log N complex multiplications
2
N 2 2
 In-place computation
a A

b B
Wr -1

 Each butterfly takes (a,b) to produce (A,B)  no need to save

(a,b)  can store (A,B) in the same locations as (a,b)
 We need 2N store registers to store the results at each stage and
these registers are also used throughout the computation of the
N-point DFT
 The order of the input: bit-reversed order
 The order of the output: natural order
 Lecture #22
Fast Fourier Transform (FFT)

1. What is FFT?
2. The decomposition-in-time Fast Fourier
Transform algorithm (DIT-FFT)
3. The decomposition-in-frequency Fast
Fourier Transform algorithm (DIF-FFT)
 DIF-FFT with N as a 2-radix number
 We divide X(k) in half – first half and second half
( N / 2 ) 1 N 1
X (k )  
n 0
x(n)W  kn
N  x ( n )
n ( N / 2 )
W kn
N , k  0,1,..., N  1

 Rewrite the second half:

N 1 ( N / 2 ) 1 ( N / 2 ) 1
 N  k n  2   N  kn
   WN  x n  WN
N N

N  x n  WN
kn k2
x ( n )W
n ( N / 2 ) n 0  2 n 0  2

Since: k N2  j ( k 2 / N )( N / 2 )  j
e e  ( 1)
 k
W N

then

 x(n)  (1) 
( N / 2 ) 1
X (k )  k
x(n  N / 2) WNkn , k  0,1,..., N  1
n 0
 DIF-FFT (cont)
 Decompose X(k) into two frequency sequences, even and odd:
( N / 2 ) 1

 x(n)  x(n  N / 2)W

N
X ( 2k )  2 kn
N , k  0,1,...,  1
n 0 2
( N / 2 ) 1

 x(n)  x(n  N / 2)W ( 2 k 1) n N

X (2k  1)  N , k  0,1,...,  1
n 0 2
Since:
 2
WN  WN / 2
1

then,
( N / 2 ) 1

 x(n)  x(n  N / 2)W

N
X ( 2k )  kn
N /2 , k  0,1,...,  1
n 0 2
( N / 2 ) 1

 x(n)  x(n  N / 2)W W

N
X (2k  1)  n
N
kn
N /2 , k  0,1,...,  1
n 0 2
 DIF-FFT butterfly

x[n] x[n] + x[n+N/2]

x[n+N/2] (x[n] - x[n+N/2])WNn

-1 WNn
 DIF-FFT of length N = 4

x[0] + x[2]
x[0] X[0]

x[1] X[2]
x[1] + x[3] -1

(x[0] - x[2])W40
-1
x[2] X[1]
W40

-1
x[3] X[3]
W41 (x[1] - x[3])W41 -1
 Lecture #23
DFT applications

1. Approximation of the Fourier Transform

of analog signals
2. Linear convolution
 Approximation of Fourier Transform

Using DFT as a discrete-frequency approximation of the DTFT

and also an approximation of the CTFT

Step1. Determine the resolution ΔΩ = 2π/N required for the DFT to

be useful for its intended purpose  determine N (N often = 2n)
Step 2. Determine the sampling frequency required to sample the
analog signal so as to avoid aliasing ωs ≥ 2ωM
Step 3. Accumulate N samples of the analog signal over N.T
seconds (T = 2π/ωs)
Step 4. Calculate DFT directly or using FFT algorithm
 Example
1
f(t) = rect[(t-1)/2]
F(ω) = 2sinc(ω)e-jω
f[n]

0.5
Ts = 1s

0
0 0.5 1 1.5 2 2.5 3
n
3
%Error of sample 1 = 50%
magnitude

0
0 1 2 3 4 5
omega
 Example

1
f(t) = rect[(t-1)/2]
F(ω) = 2sinc(ω)e-jω
f[n]

0.5
Ts = 0.2s
0
0 5 10 15
n
3
%Error of sample 1 = 10%
magnitude

0
0 5 10 15 20 25 30
omega
 Example

1 f(t) = rect[(t-1)/2]
F(ω) = 2sinc(ω)e-jω
f[n]

0.5 Ts = 0.1s

0
0 5 10 15 20 25 30 35
n
3
%Error of sample 1 = 5%
magnitude

0
0 10 20 30 40 50 60 70
omega
 Windowing
 Source of error: truncation or “windowing” of the periodic
extension of the DT sequence implied in the DFT development
 Windowing = multiplying the periodic extension of x[n] by a
rectangular function with duration N.T  DFT involves a convolution
DFT = sampled(DTFT*sinc)
 This multiplication causes spectrum-leakage distortion
 To reduce the affect of spectrum-leakage distortion:
- Increase the sampling frequency
- Increase the number of samples
- Choose an appropriate windowing function (Hamming, Hanning)
 Lecture #23
DFT applications

1. Approximation of the Fourier Transform of

analog signals
2. Linear convolution
 Recall linear convolution


y[n]  x1[n] * x2 [n]   x [ p]x [n  p]
p  
1 2

 N1: the non-zero length of x1(n); N2: the non-zero

length of x2(n); Ny = N1 + N2 -1
 The shift operation is the regular shift
 The flip operation is the regular flip
 Recall circular convolution

N 1
y[n]  x1[n]  x2 [n]   x1[ p]x2 [n  p]
p 0

 The non-zero length of x1(n) and x2(n) can be no longer

than N
 The shift operation is circular shift
 The flip operation is circular flip
 Calculation of the linear convolution

The circular convolution of 2 sequences of length N1 and N2

can be made equal to the linear convolution of 2 sequences
by zero padding both sequences so that they both consists
of N1+N2-1 samples.

Zero padding
x1(n) x’1(n) DFT
(N2-1) zeros
N1 samples IDFT
Zero padding x1(n)*x2(n)
x2(n) x’2(n) DFT
(N1-1) zeros
N2 samples
Example of calculation of the linear convolution

x1(n) = [ 1 2 3 4 ]; x2(n) = [ 0 1 2 3 ]
x’1(n) = [ 1 2 3 4 0 0 0 ]; x’2(n) = [ 0 1 2 3 0 0 0 ]
X’1(k) = [ 10, -2.0245-j6.2240, 0.3460+j2.4791, 0.1784-
j2.4220, 0.1784+j2.4220, 0.3460-j2.4791, -2.0245-j6.2240 ];
X’2(k) = [ 6, -2.5245-j4.0333, -0.1540+j2.2383, -0.3216-
j1.7950, -0.3216+j1.7950, -0.1540-j2.2383, -2.5245+j4.0333];
Y’(k) = [ 60, -19.9928+j23.8775, -5.6024+j0.3927, -5.8342-
j0.8644, -4.4049+j0.4585, -5.6024-j0.3927, -19.9928
+j23.8775 ]
IDFT{Y’(k)} = y’(n) = [ 0 1 4 10 16 17 12 ]
 Lecture #24
Using DFT/FFT in filtering

 The response, y(n) of a filter with the impulse response, h(n)

to an input, x(n) can be calculated by using the DFT
 Limitations: All sample values of the signal must be
accumulated before the process begins
 Great memory
 Long time delay
 Not suitable for long duration input
 Solution: block filtering
Overlap-add technique in block filtering

 Divide long input signal, x(n) into non-overlapped blocks,

xb(n) of appropriate length for FFT calculation.
 Convolve each block xb(n) and h(n) to get the output,
yb(n)
 Overlap-add outputs, yb(n) together to form the output
signal, y(n)
Example of overlap-add technique

h(n)

x(n)
Example of overlap-add technique

x0(n)

x1(n)

x2(n)
Example (cont)

y0(n)

y1(n)

y2(n)