errors.
If the impulse response of S is
h(t) = δ(t),
where δ is the Dirac delta function, then the system S is a pass-through system, and the
reconstruction consists of weighted delta functions.
Lee & Varaiya, Signals and Systems
485
11.3. THE NYQUIST-SHANNON SAMPLING THEOREM
11.3
The Nyquist-Shannon sampling theorem
We can now give a precise statement of the Nyquist-Shannon sampling theorem:
If x is a continuous-time signal with Fourier transform X and if X (ω) is zero outside the
range −π/T < ω < π/T radians/second, then
x = IdealInterpolator (
(
T SamplerT x)).
We can state this theorem slightly differently. Suppose x is a continuous-time signal with
no frequency larger than some f0 Hertz. Then x can be recovered from its samples if
f0 < fs/2, the Nyquist frequency.
A formal proof of this theorem involves some technical difficulties (it was first given
by Claude Shannon of Bell Labs in the late 1940s). But we can get the idea from the
following three-step argument (see figure 11.9).
Step 1. Let x be a continuous-time signal with Fourier transform X . At this point we do
not require that X (ω) be zero outside the range −π/T < ω < π/T . We sample x with
sampling interval T to get the discrete-time signal
y = Sampler (
T x).
It can be shown (see box on page 490 ) that the DTFT of y is related to the CTFT of x by
1
∞
ω
Y (ω) =
∑ X
− 2πk .
T
T
T
k=−∞
This important relation says that the DTFT Y of y is the sum of the CTFT X with copies
of it shifted by multiples of 2π/T . Also, the frequency axis is normalized by dividing ω
by T . There are two cases to consider, depending on whether the shifted copies overlap.
First, if X (ω) = 0 outside the range −π/T < ω < π/T , then the copies will not overlap,
and in the range −π < ω < π,
1
ω
Y (ω) =
X
.
(11.5)
T
T
In this range of frequencies, Y has the same shape as X , scaled by 1/T . This relationship
between X and Y is illustrated in figure 11.10, where X is drawn with a triangular shape.
In the second case, illustrated in figure 11.11, X does have non-zero frequency compo-
nents higher than π/T . Notice that in the sampled signal, the frequencies in the vicinity
486
Lee & Varaiya, Signals and Systems
11. SAMPLING AND RECONSTRUCTION
Time
Frequency
x( t)
X(!)
X = CTFT ( x )
x
1
t
!
#"/ T
"/ T
SamplerT
y( n)
Y(!)
Y = DTFT ( y )
1/ T
n
y
!
#2"
#"
"
2"
ImpulseGenT
w( t)
W(!)
W = CTFT ( w )
1/ T
t
!
w
#2"/ T
#"/ T
"/ T
2"/ T
Sinc
z( t)
T
Z(!)
Z = CTFT ( z )
IdealInterpolator
1
T
t
!
z
#"/ T
"/ T
Figure 11.9: Steps in the justification of the Nyquist-Shannon sampling theorem.
Lee & Varaiya, Signals and Systems
487
11.3. THE NYQUIST-SHANNON SAMPLING THEOREM
X(!)
1
!
#"/ T
"/ T
Y(!)
1/ T
...
... !
#3"
#"
"
3"
Figure 11.10: Relationship between the CTFT of a continuous-time signal and
the DTFT of its discrete-time samples. The DTFT is the sum of the CTFT and its
copies shifted by multiples of 2π/T , the sampling frequency in radians per second.
The frequency axis is also normalized.
X(!)
1
!
"#/ T
#/ T
Y(!)
1/ T
!
"#
#
Figure 11.11: Relationship between the CTFT of a continuous-time signal and the
DTFT of its discrete-time samples when the continuous-time signal has a broad
enough bandwidth to introduce aliasing distortion.
488
Lee & Varaiya, Signals and Systems
11. SAMPLING AND RECONSTRUCTION
of π are distorted by the overlapping of frequency components above and below π/T in
the original signal. This distortion is called aliasing distortion.
We continue with the remaining steps, following the signals in figure 11.9.
Step 2. Let w be the signal produced by the impulse generator,
∞
∀ t ∈ R, w(t) = ∑ y(n)δ(t −nT).
n=−∞
The Fourier Transform of w is W (ω) = Y (ωT ) (see box on page 490).
Step 3. Let z be the output of the IdealInterpolatorT . Its Fourier transform is simply
Z(ω)
= W (ω)S(ω)
= Y (ωT )S(ω),
where S(ω) is the frequency response of the IdealInterpolatorT reconstruction filter. As
seen in exercise 21 of Chapter 10,
T
−π/T < ω < π/T
S(ω) =
(11.6)
0
otherwise
Substituting for S and Y , we get
TY (ωT )
−π/T < ω < π/T
Z(ω)
=
0
otherwise
∞
∑
X (ω − 2πk/T ) −π/T < ω < π/T
=
k=−∞
0
otherwise
If X (ω) is zero for |ω| larger than the Nyquist frequency π/T , then we conclude that
∀ ω ∈ R, Z(ω) = X(ω).
That is, w is identical to x. This proves the Nyquist-Shannon result.
However, if X (ω) does have non-zero values for some |ω| larger than the Nyquist fre-
quency, then z will be different from x, as illustrated in figure 11.11.
Lee & Varaiya, Signals and Systems
489
11.3. THE NYQUIST-SHANNON SAMPLING THEOREM
Probing Further: Sampling
We construct a mathematical model for sampling a pulse stream given by
∞
∀ t ∈ R, p(t) = ∑ δ(t −kT),
k=−∞
where δ is the Dirac delta function. Let y(n) = x(nT ) be a sampling of the continuous-
time signal x with sampling period T . Construct first an intermediate continuous-time
signal w(t) = x(t)p(t). We can show that the CTFT of w is equal to the DTFT of y.
This gives us a way to relate the CTFT of x to the DTFT of its samples y. Recall that
multiplication in the time domain results in convolution in the frequency domain (see
table 10.9), so
∞
1
1 Z
W (ω) =
X (ω) ∗ P(ω) =
X (Ω)P(ω − Ω)dΩ.
2π
2π−∞
It can be shown (see box on page 491 that the CTFT of p(t) is
2π
∞
2π
P(ω) =
∑ δ(ω − k
),
so
T
T
k=−∞
∞
1 Z
2π
∞
2π
W (ω)
=
X (Ω)
δ(ω − Ω − k
)dΩ
2
∑
π
T
T
−
k=−∞
∞
∞
1
∞
Z
2π
=
∑
X (Ω)δ(ω − Ω − k
)dΩ
T
T
k=−∞−∞
1
∞
2π
=
∑ X(ω − k
)
T
T
k=−∞
where the last equality follows from the sifting property (9.11). The next step is to
show that Y (ω) = W (ω/T ). We leave this as an exercise. From this, the basic Nyquist-
Shannon result follows,
1
∞
ω − 2πk
Y (ω) =
∑ X
.
T
T
k=−∞
This relates the CTFT X of the signal being sampled x to the DTFT Y of the discrete-
time result y.
490
Lee & Varaiya, Signals and Systems
11. SAMPLING AND RECONSTRUCTION
Probing Further: Impulse Trains
Consider a signal p consisting of periodically repeated Dirac delta functions with period
T ,
∞
∀ t ∈ R, p(t) = ∑ δ(t −kT).
k=−∞
This signal has the Fourier series expansion
∞
∀
1
t ∈ R,
p(t) = ∑
eiω0mt ,
T
m=−∞
where the fundamental frequency is ω0 = 2π/T . This can be verified by applying the
formula from table 10.5. That formula, however, gives an integration range of 0 to the
period, which in this case is T . This integral covers one period of the periodic signal, but
starts and ends on a delta function in p. To avoid the resultant mathematical subtleties,
we can integrate from −T /2 to T /2, getting Fourier series coefficients
T /2
Z
∞
∀
1
m ∈ Z,
Pm =
∑ δ(t − kT ) eiω0mtdt.
T −
k=−∞
T /2
The integral is now over a range that includes only one of the delta functions. The kernel
of the integral is zero except when t = 0, so by the sifting rule, the integral evaluates to
1. Thus, all Fourier series coefficients are Pm = 1/T . Using the relationship between the
Fourier series and the Fourier Transform of a periodic signal (from Section 10.6.3), we
can write the continuous-time Fourier transform of p as
∞
∀
2π
ω ∈ R,
P(ω) =
∑ δ ω − 2π k .
T
T
k=−∞
Lee & Varaiya, Signals and Systems
491
11.4. SUMMARY
11.4
Summary
The acts of sampling and reconstructing signals bridge the world of continuous-time phys-
ical signals with the discrete computational world. The periodicity of frequencies in the
discrete world implies that for each discrete-time sinusoidal signal, there are multiple
corresponding discrete-time frequencies. These frequencies are aliases of one another.
When a signal is sampled, these frequencies become indistinguishable, and aliasing dis-
tortion may result. The Nyquist-Shannon sampling theorem gives a simple condition
under which aliasing distortion is avoided. Specifically, if the signal contains no sinu-
soidal components with frequencies higher than half the sampling frequency, then there
will be no aliasing distortion. Half the sampling frequency is called the Nyquist frequency
because of this key result.
492
Lee & Varaiya, Signals and Systems
11. SAMPLING AND RECONSTRUCTION
Exercises
Each problem is annotated with the letter E, T, C which stands for exercise, requires some
thought, requires some conceptualization. Problems labeled E are usually mechanical,
those labeled T require a plan of attack, those labeled C usually have more than one
defensible answer.
1. E Consider the continuous-time signal
x(t) = cos(10πt) + cos(20πt) + cos(30πt).
(a) Find the fundamental frequency. Give the units.
(b) Find the Fourier series coefficients A0, A1, · · · and φ1, φ2, · · · .
(c) Let y be the result of sampling this signal with sampling frequency 10 Hz.
Find the fundamental frequency for y, and give the units.
(d) For the same y, find the discrete-time Fourier series coefficients, A0, A1, · · ·
and φ1, · · · .
(e) Find
w = IdealInterpolator (
(
T SamplerT x))
for T = 0.1 seconds.
(f) Is there any aliasing distortion caused by sampling at 10 Hz? If there is,
describe the aliasing distortion in words.
(g) Give the smallest sampling frequency that avoids aliasing distortion.
2. E Verify that SamplerT defined by (11.1) and (11.2) is linear but not time invariant.
3. E A real-valued sinusoidal signal with a negative frequency is always exactly equal
to another sinusoid with positive frequency. Consider a real-valued sinusoid with a
negative frequency −440 Hz,
y(n) = cos(−2π440nT + φ).
Find a positive frequency f and phase θ such that
y(n) = cos(2π f nT + θ).
Lee & Varaiya, Signals and Systems
493
EXERCISES
4. T Consider a continuous-time signal x where for all t ∈ R,
∞
x(t) = ∑ r(t − k).
k=−∞
where
1
0 ≤ t < 0.5
r(t) =
.
0
otherwise
(a) Is x(t) periodic? If so, what is the period?
(b) Suppose that T = 1. Give a simple expression for y = Sampler (
T x).
(c) Suppose that T = 0.5. Give a simple expression for y = Sampler (
T x) and
z = IdealInterpolator (
(
T SamplerT x)).
(d) Find an upper bound for T (in seconds) such that
x = IdealInterpolator (
(
T SamplerT x)),
or argue that no value of T makes this assertion true.
5. T Consider a continuous-time signal x with the following finite Fourier series ex-
pansion,
4
∀ t ∈ R, x(t) = ∑ cos(kω0t)
k=0
where ω0 = π/4 radians/second.
(a) Give an upper bound on T (in seconds) such that
x = IdealInterpolator (
(
T SamplerT x)).
(b) Suppose that T = 4 seconds. Give a simple expression for y = Sampler (
T x).
(c) For the same T = 4 seconds, give a simple expression for
w = IdealInterpolator (
(
T SamplerT x)).
6. T Consider a continuous-time audio signal x with CTFT shown in Figure 11.12.
Note that it contains no frequencies beyond 10 kHz. Suppose it is sampled at 40
kHz to yield a signal that we will call x40. Let X40 be the DTFT of x40.
(a) Sketch |X40(ω)| and carefully mark the magnitudes and frequencies.
494
Lee & Varaiya, Signals and Systems
11. SAMPLING AND RECONSTRUCTION
H(2! f)
1
f (kHz)
-10
10
Figure 11.12: CTFT of an audio signal considered in exercise 6.
(b) Suppose x is sampled at 20,000 samples/second. Let x20 be the resulting sam-
pled signal and X20 its DTFT. Sketch and compare x20 and x40.
(c) Now suppose x is sampled at 15,000 samples/second. Let x15 be the resulting
sampled signal and X15 its DTFT. Sketch and compare X20 and X15. Make
sure that your sketch shows aliasing distortion.
7. C Consider two continuous-time sinusoidal signals given by
x1(t) = cos(ω1t)
x2(t) = cos(ω2t),
with frequencies ω1 and ω2 radians/second such that
0 ≤ ω1 ≤ π/T
and
0 ≤ ω2 ≤ π/T.
Show that if ω1 = ω2 then
Sampler (
(
T x1) = SamplerT x2).
I.e., the two distinct sinusoids cannot be aliases of one another if they both have
frequencies below the Nyquist frequency. Hint: Try evaluating the sampled signals
at n = 1.
Lee & Varaiya, Signals and Systems
495
EXERCISES
496
Lee & Varaiya, Signals and Systems
12
Stability
Contents
12.1 Boundedness and stability . . . . . . . . . . . . . . . . . . . . . . . 501
12.1.1 Absolutely summable and absolutely integrable . . . . . . . . 501
12.1.2 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
Probing Further: Stable systems and their impulse response
. . . . . 505
12.2 The Z transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
12.2.1 Structure of the region of convergence . . . . . . . . . . . . . 509
12.2.2 Stability and the Z transform . . . . . . . . . . . . . . . . . . 514
12.2.3 Rational Z tranforms and poles and zeros . . . . . . . . . . . 515
12.3 The Laplace transform . . . . . . . . . . . . . . . . . . . . . . . . 519
12.3.1 Structure of the region of convergence . . . . . . . . . . . . . 521
12.3.2 Stability and the Laplace transform . . . . . . . . . . . . . . 525
12.3.3 Rational Laplace tranforms and poles and zeros . . . . . . . . 526
12.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
The four Fourier transforms prove to be useful tools for analyzing signals and systems.
When a system is LTI, it is characterized by its frequency response H, and its input x and
output y are related simply by
∀ω ∈ R, Y(ω) = H(ω)X(ω),
where Y is the Fourier transform of y, and X is the Fourier transform of x.
497
However, we ignored a lurking problem. Any of the three Fourier transforms, X , Y , or
H, may not exist. Suppose for example that x is a discrete-time signal. Then its Fourier
transform (the DTFT) is given by
∞
∀ ω ∈ R, X(ω) = ∑ x(n)e−iωn.
(12.1)
n=−∞
This is an infinite sum, properly viewed as the limit
N
∀ ω ∈ R, X(ω) = lim ∑ x(n)e−iωn.
(12.2)
N→∞ n=−N
As with all such limits, there is a risk that it does not exist. If the limit does not exist
for any ω ∈ R, then the Fourier transform becomes mathematically treacherous at best
(involving, for example, Dirac delta functions), and mathematical nonsense at worst.
Example 12.1: Consider the sequence
0,
n ≤ 0
x(n) =
,
an−1, n > 0
where a > 1 is a constant. Plugging into (12.1), the Fourier transform should be
∞
∀ ω ∈ R, X(ω) = ∑ an−1e−iωn.
n=0
At ω = 0, it is easy to see that this sum is infinite (every term in the sum is greater
than or equal to one). At other values of ω, there are also problems. For example,
at ω = π, the terms of the sum alternate in sign and increase in magnitude as n gets
larger. The limit (12.2) clearly will not exist.
A similar problem arises with continuous-time signals. If x is a continuous-time signal,
then its Fourier transform (the CTFT) is given by
∞
Z
∀ ω ∈ R, X(ω) =
x(t)e−iωt dt.
(12.3)
−∞
498
Lee & Varaiya, Signals and Systems
12. STABILITY
main rotor shaft
tail
body
M
Figure 12.1: A highly simplified helicopter.
Again, there is a risk that this integral does not exist.
This chapter studies signals for which the Fourier transform does not exist. Such signals
prove to be both common and useful. The signal in example 12.1 gives the bank balance
of example 5.12 when an initial deposit of one dollar is made, and no further deposits or
withdrawals are made (thus, it is the impulse response of the bank account). This signal
grows without bound, and any signal that grows without bound will cause difficulties
when using the Fourier transform.
The bank account is said to be an unstable system, because its output can grow without
bound even when the input is always bounded. Such unstable systems are common, so it
is unfortunate that the frequency domain methods we have studied so far do not appear to
apply.
Example 12.2: A helicopter is intrinsically an unstable system, requiring an elec-
tronic or mechanical feedback control system to stabilize it. It has two rotors, one
above, which provides lift, and one on the tail. Without the rotor on the tail, the
body of the helicopter would start to spin. The rotor on the tail counteract