which requires significant mathematical skill.
Let X ∈ DiscSignals be the Fourier series for some x ∈ ContPeriodicp. That is, x =
InverseFourierSeriesp(X). Let Y = FourierSeriesp(x). We now show that Y = X, i.e.
Ym = Xm for all m.
p
1 Z
Ym =
x(t)e−imω0t dt, by (10.2)
p
0
p
1 Z
∞
=
[ ∑ Xkeikω0t]e−imω0tdt, by (10.1)
p
k=−
0
∞
p
∞
1
Z
=
∑
Xk
ei(k−m)ω0t dt
p
k=−∞
0
p
1
Z
1
Z
p
=
Xm
dt + ∑ Xk
ei(k−m)ω0t dt
p
p
k=m
0
0
=
Xm,
since for k = m,
Z
p
ei(k−m)ω0t dt = 0.
0
Lee & Varaiya, Signals and Systems
417
10.2. THE FOURIER SERIES (FS)
x( t)
1
t
1
2
Figure 10.2: A square wave.
| X |
m
1/2
1/!
1/3! 1/5!1/7! m
Figure 10.3: Magnitude of the Fourier series coefficients of a square wave.
Example 10.1: Consider a square wave x ∈ ContPeriodic2, shown in Figure 10.2.
It is periodic with period p = 2, so its fundamental frequency is ω0 = 2π/2 = π
radians/second. We can find its continuous-time Fourier series coefficients using
(10.2) as follows,
2
1 Z
Xm =
x(t)e−imπt dt
2
0
1
1 Z
=
e−imπt dt.
2
0
Notice that when m = 0, this integral is easy to evaluate because e0 = 1, so
X0 = 1/2.
The following fact from calculus will help us solve the integral when m = 0,
b
Z
ecωc dω = ecb − eca
(10.5)
a
418
Lee & Varaiya, Signals and Systems
10. THE FOUR FOURIER TRANSFORMS
for real a and b and complex c. Letting c = −imπ, the integral becomes
1
1 Z
Xm =
ect c dt
2c
0
−1
=
(e−imπ − e0)
2imπ
i
=
(e−imπ − 1)
2mπ
where the last step follows from multiplying top and bottom by i, observing that
i2 = −1, and observing that e0 = 1. Notice that
1
if m is even
e−imπ =
−1 if m is odd
Thus, when m = 0,
0
if m is even
Xm =
−i/mπ if m is odd
The magnitude of these Fourier series coefficients is plotted in Figure 10.3. Notice
that the magnitudes of the coefficients decay rather slowly as m gets large (they
decay as 1/m). This accounts for the persistent overshoot (Gibbs phenomenon)
seen in Figure 7.7. Finite Fourier series approximations of this periodic square
wave are not particularly good because the size of the Fourier series coefficients
decays slowly.
Other examples of Fourier series coefficients for various signals are given in table 10.1.
10.3
The discrete Fourier transform (DFT)
The discrete-time Fourier series (DFS) expansion for x ∈ DiscPeriodicp is (see (8.30))
p−1
∀ n ∈ Z, x(n) = ∑ Xkeikω0n,
(10.6)
k=0
Lee & Varaiya, Signals and Systems
419
10.3. THE DISCRETE FOURIER TRANSFORM (DFT)
Signal
Fourier Series
Reference
∀ t ∈ R,
∀ m ∈ Z,
Exercise 2
x(t) = eiω0t ,
1
if m = 1
Xm =
0
otherwise
where ω0 = 0.
∀ t ∈ R,
∀ m ∈ Z,
Exercise 2
x(t) = cos(ω0t),
1/2
if |m| = 1
Xm =
0
otherwise
where ω0 = 0.
∀ t ∈ R,
∀ m ∈ Z,
Exercise 2
x(t) = sin(ω0t),
1/2i
if m = 1
Xm =
−1/2i if m = −1
where ω0 = 0.
0
otherwise
∀ t ∈ R,
∀ m ∈ Z,
Exercise 2
x(t) = 1
1
if m = 0
Xm =
0
otherwise
Square wave:
∀ m ∈ Z,
Exercise 3
∀ t ∈ [0, p],
sin(mω0T )
Xm =
(mπ)
1
if t < T or t > p − T
x(t) =
0
otherwise
Impulse train:
∀ m ∈ Z,
Exercise 4
∀ t ∈ R,
Xm = 1/p
∞
x(t) = ∑ δ(t − np)
n=−∞
Table 10.1: Fourier series coefficients of periodic signals. In all cases, ω0 = 2π/p,
where p is the period. We can obtain Fourier transforms for each of these signals
by using (10.16).
420
Lee & Varaiya, Signals and Systems
10. THE FOUR FOURIER TRANSFORMS
where ω0 = 2π/p (radians/sample). The Fourier series coefficients can be found using
the formula
p−1
∀
1
k ∈ Z,
Xk =
∑ x(m)e−imkω0.
(10.7)
p m=0
For historical reasons, the discrete Fourier transform (DFT) is the DFS with slightly
different scaling. It is defined by
p−1
∀ n ∈ Z, x(n) = 1
X eikω0n,
(10.8)
p ∑
k
k=0
p−1
∀ k ∈ Z, X =
x(m)e−imkω0 .
(10.9)
k
∑
m=0
Obviously, the DFT coefficients are related to the DFS coefficients by
X =
k
pXk.
This scaling is somewhat unfortunate, since it means that the DFT coefficients do not have
the same units as the signal x, but the scaling is firmly established in the literature, so we
stick to it. We omit the prime when it is clear whether we are talking about the Fourier
transform instead of the Fourier series.
Observe that X = DFT p(x) is a discrete signal that is itself periodic with period p. To
verify this, note that for any integer N and for all integers k,
p−1
X
=
k+N p
∑ x(m)e−im(k+Np)ω0
m=0
p−1
=
∑ x(m)e−imkω0e−imNpω0
m=0
p−1
=
∑ x(m)e−imkω0e−imN2π, since ω0 = 2π/p
m=0
p−1
=
∑ x(m)e−imkω0
m=0
=
X .
k
Lee & Varaiya, Signals and Systems
421
10.3. THE DISCRETE FOURIER TRANSFORM (DFT)
x( n)
1
n
Figure 10.4: A discrete square wave.
Note that (10.9) looks like a discrete Fourier series expansion of the periodic function
X . That is, the periodic function is described as a sum of complex exponentials. The
only substantial difference, comparing with (10.6), is the sign of the exponent. This
sign difference can be easily removed with a change of variables. By doing so, you can
discover that x(−m) is the m-th Fourier series coefficient for the function X ! The DFT is
rather special, therefore, in that both the time and frequency domain representations of a
function are Fourier series, and both are periodic.
The DFT therefore is the function
DFT p : DiscPeriodicp → DiscPeriodicp,
given by (10.9). The inverse DFT is the function
InverseDFT p : DiscPeriodicp → DiscPeriodicp,
given by (10.8). As in (10.3), (10.4), DFT p and InverseDFT p are inverses of each other.
This can be verified using methods similar to those in the box on page 417. The DFT and
its inverse are computed by systems that we can represent as shown in Figure 10.1(c) and
(d).
The DFT is the most useful form of the Fourier transform for computation, because the
system DFT p is easily implemented on a computer. Both summations (10.8) and (10.9)
are finite. Moreover, there is an algorithm called the fast Fourier transform (FFT) that
calculates these summations with far fewer arithmetic operations than the most direct
method. Moreover, because the sums are finite, the DFT always exists. There are no
mathematical problems with convergence.
422
Lee & Varaiya, Signals and Systems
10. THE FOUR FOURIER TRANSFORMS
| X' |
k
4
k
0
Figure 10.5: Magnitude of the DFT of a discrete square wave.
Example 10.2:
Consider a discrete square wave x ∈ DiscPeriodic8, shown in
Figure 10.4. It is periodic with period p = 8, so its fundamental frequency is ω0 =
2π/8 = π/4 radians/sample. We can find its DFT using (10.9) as follows,
7
X
=
k
∑ x(m)e−imkω0
m=0
3
=
∑ e−imkπ/4.
m=0
Notice that when k = 0, this sum is easy to evaluate because e0 = 1, so
X =
0
4.
Moreover, when k is any multiple of 8, we get X = 4, as it should, since the DFT is
k
periodic with period 8. The following identity will help us simplify the summation
when k = 0 nor any multiple of 8,
N
∑ am = 1−aN+1 .
(10.10)
1−a
m=0
(To demonstrate the validity of this identity, just multiply both sides by 1 − a.)
Letting N = 3 and a = e−ikπ/4, we get that for k = 0 nor any multiple of 8,
1 − e−ikπ
X =
.
k
1 − e−ikπ/4
Lee & Varaiya, Signals and Systems
423
10.4. THE DISCRETE-TIME FOURIER TRANSFORM (DTFT)
Notice that the numerator is particularly simple, since
0
if k is even
1 − e−ikπ =
2
if k is odd
The magnitude of these DFT coefficients is plotted in figure 10.5.
Other examples of discrete Fourier transform coefficients for various signals are given in
table 10.2.
10.4
The discrete-Time Fourier transform (DTFT)
We have shown in Section 9.2 that the frequency response H of an LTI system is related
to the impulse response h by
∞
∀ ω ∈ R, H(ω) = ∑ h(m)e−iωm.
m=−∞
H is called the discrete-time Fourier transform (DTFT) of h. For any x ∈ DiscSignals (not
just an impulse response), its DTFT is defined to be
∞
∀ ω ∈ R, X(ω) = ∑ x(m)e−iωm.
(10.11)
m=−∞
Of course, this definition is only valid for those x and those ω where the sum converges
(it is not trivial mathematically to characterize this).
Notice that the function X is periodic with period 2π. That is, X (ω) = X (ω + 2πN) for
any integer N, because
e−iωt = e−i(ω+2πN)t
for any integer N. Thus, X ∈ ContPeriodic2 .
π
Note that (10.11) looks like a discrete Fourier series expansion of the periodic function
X . That is, the periodic function is described as a sum of complex exponentials. The
only substantial difference, comparing with (10.1), is the sign of the exponent. This
424
Lee & Varaiya, Signals and Systems
10. THE FOUR FOURIER TRANSFORMS
Signal
DFT
Reference
∀ n ∈ Z,
∀ k ∈ Z,
Exercise 5
x(n) = ei2π f n,
p
if k ∈ A
X =
k
0
otherwise
where f = 0.
∀ n ∈ Z,
∀ k ∈ Z,
Exercise 5
x(n) = cos(2π f n),
p/2
if k ∈ A
X =
p/
k
2
if k ∈ B
where f = 0.
0
otherwise
∀ n ∈ Z,
∀ k ∈ Z,
Exercise 5
x(n) = sin(i2π f n),
p/2i
if k ∈ A
X =
−p/
k
2i
if k ∈ B
where f = 0.
0
otherwise
∀ n ∈ Z,
∀ k ∈ Z,
Exercise 5
x(n) = 1
p
if k ∈ C
X =
k
0
otherwise
Square wave:
∀ k ∈ Z,
Exercise 6
∀ n ∈ {0,1,··· , p − 1},
sin(k(M + 0.5)ω0)
X =
k
sin(kω0/2)
1
if n ≤ M or n ≥ p − M
x(n) =
0
otherwise
Impulse train:
∀ k ∈ Z,
Exercise 7
∀ n ∈ Z,
X =
k
1
∞
x(n) = ∑ δ(n − kp)
k=−∞
Table 10.2: Discrete Fourier transform of periodic signals.
The fundamental
frequency is ω0 = 2π/p, where p is the period.
For the complex exponen-
tial and sinusoidal signals, the frequency f must be rational, and is related to
the period p by f = m/p for some integer m (see Section 7.6.1). The follow-
ing sets are used in this table: A = {· · · m − 2p, m − p, m, m + p, m + 2p, · · · }, B =
{···−m−2p,−m− p,−m,−m+ p,−m+2p,···}, and C = {···−2p,−p,0, p,2p,···}.
Lee & Varaiya, Signals and Systems
425
10.4. THE DISCRETE-TIME FOURIER TRANSFORM (DTFT)
sign difference can be easily removed with a change of variables. By doing so, you can
discover that x(−n) is the n-th Fourier series coefficient for the function X!
The DTFT (10.11) has similar structure to the DFT (10.9). In fact, the DTFT can be viewed as a generalization of the DFT to signals that are neither periodic nor finite. In
other words, as p approaches infinity, ω0 approaches zero, so instead of a discrete set of
frequencies spaced by ω0 we have a continuum.
The DTFT is a system
DTFT : DiscSignals → ContPeriodic2π
and its inverse is
InverseDTFT : ContPeriodic2 → DiscSignals.
π
The inverse is given by
2π
∀ n ∈
R
Z,
x(n) = 1
X (
2
ω)eiωndω.
(10.12)
π 0
Notice that because X is periodic, this can equivalently be written as
π
Z
∀
1
n ∈ Z,
x(n) =
X (ω)eiωndω.
2π−π
We integrate over one cycle of the periodic function, so it does not matter where we start.
These are depicted graphically in Figure 10.1(e) and (f).
DTFT and InverseDTFT are inverses of each other. This follows from the fact that
FourierSeriesp and InverseFourierSeriesp are inverses of each other.
Example 10.3: Consider a discrete rectangle x ∈ DiscSignals, shown in Figure
10.6. We can find its DTFT using (10.11) as follows,
∞
X (ω)
=
∑ x(m)e−iωm
m=−∞
3
=
∑ e−iωm.
m=0
426
Lee & Varaiya, Signals and Systems
10. THE FOUR FOURIER TRANSFORMS
x( n)
1
n
Figure 10.6: A discrete rectangle signal.
| X(!)|
4
!
"/2
"
2"
0
Figure 10.7: Magnitude of the DTFT of a discrete rectangle.
Notice that when ω = 0, this sum is easy to evaluate because e0 = 1, so
X (0) = 4.
Moreover, when ω is any multiple of 2π, we get X (ω) = 4, as it should, since the
DTFT is periodic with period 2π. We can again use the identity (10.10), Letting
N = 3 and a = e−iω, we get
1 − e−i4ω
X (ω) =
.
1 − e−iω
The magnitude of this function is plotted in figure 10.5.
Other examples of DTFTs for various signals are given in table 10.3.
Lee & Varaiya, Signals and Systems
427
10.4. THE DISCRETE-TIME FOURIER TRANSFORM (DTFT)
Signal
DTFT
Reference
∀ n ∈ Z, x(n) = δ(n)
∀ ω ∈ R, X(ω) = 1
Example
∀ n ∈ Z,
∀ ω ∈ R, X(ω) = e−iωN
Example
x(n) = δ(n − N)
∀ n ∈ Z, x(n) = K
∀ ω ∈ R,
Section
∞
X (
ω) = 2πK
∑
δ(ω − k2π)
k=−∞
∀ n ∈ Z,
∀ ω ∈ R,
Exercise 18
x(n) = anu(n),
|a| < 1
1
X (ω) = 1−ae−iω
∀ n ∈ Z,
∀ ω ∈ R,
Exercise 8
1
if |n| ≤ M
sin(ω(M + 0.5))
x(n) =
X (ω) =
0
otherwise
sin(ω/2)
∀ n ∈ Z,
∀ ω ∈ [−π,π],
–
sin(W n)
1
if |
x(n) =
, 0 < W <
ω| ≤ W
π
X (ω) =
πn
0
otherwise
Table 10.3: Discrete time Fourier transforms of key signals. The function u is the
unit step, given by (2.16).
428
Lee & Varaiya, Signals and Systems
10. THE FOUR FOURIER TRANSFORMS
x( t)
1
t
1
Figure 10.8: A rectangular pulse.
10.5
The continuous-time Fourier transform
The frequency response and impulse response of a continuous-time LTI system are re-
lated by the continuous-time Fourier transform (CTFT), more commonly called simply
∞
∀
R
ω ∈ R,
X (ω) =
x(t)e−iωt dt.
(10.13)
−∞
The CTFT can be defined for any function x ∈ ContSignals where the integral exists. It
need not be the impulse response of any system, and it need not be periodic or finite. The
inverse relation is
∞
∀ t ∈
R
R,
x(t) = 1
X (
2
ω)eiωt dω.
(10.14)
π −∞
It is true but difficult to prove that the CTFT and the inverse CTFT are indeed inverses.
The CTFT can be viewed as a generalization of both the FS and DTFT where neither the
frequency domain nor the time domain signal needs to be periodic. Alternatively, it can
be viewed as the last remaining Fourier transform, where neither time nor frequency is
discrete. Graphically, the CTFT is a system as shown in Figure 10.1(g) and (h).
Example 10.4: Consider a rectangular pulse x ∈ ContSignals, shown in Figure
10.8. We can find its continuous-time Fourier transform using