Lecture X: Discrete-time Fourier transform

Maxim Raginsky

BME 171: Signals and Systems

Duke University

October 15, 2008

Maxim Raginsky Lecture X: Discrete-time Fourier transform

This lecture

Plan for the lecture:

1 Recap: Fourier transform for continuous-time signals
2 Frequency content of discrete-time signals: the DTFT
3 Examples of DTFT
4 Inverse DTFT
5 Properties of the DTFT

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Recap: Fourier transform

Recall from the last lecture that any sufficiently regular (e.g.,
finite-energy) continuous-time signal x(t) can be represented in frequency
domain via its Fourier transform
Z ∞
X(ω) = x(t)e−jωt dt.
−∞

We can recover x(t) from X(ω) via the inverse Fourier transform formula:
Z ∞
1
x(t) = X(ω)ejωt dω.
2π −∞

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Spectral content of discrete-time signals

In this lecture, we will look at one way of describing discrete-time signals

through their frequency content: the discrete-time Fourier transform
(DTFT).

Any discrete-time signal x[n] that is absolutely summable, i.e.,

∞
X
|x[n]| < +∞,
n=−∞

has a DTFT X(Ω), −∞ < Ω < ∞, given by

∞
X
X(Ω) = x[n]e−jnΩ
n=−∞

Note that, even though the underlying signal x[n] is discrete-time, the
DTFT is a function of a continuous frequency Ω.

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Periodicity of the DTFT

The first thing to note is that the DTFT X(Ω) of x[n] is 2π-periodic:
∞
X
X(Ω + 2π) = x[n]e−jn(Ω+2π)
n=−∞
X∞
= x[n]e−jnΩ |e−j2πn
{z }
n=−∞ =1
∞
X
= x[n]e−jnΩ
n=−∞
= X(Ω).

This periodicity is due to the discrete-time nature of the signal. Thus,

when working with DTFT’s, we only need to look at the range
0 ≤ Ω ≤ 2π (or −π ≤ Ω ≤ π).

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Computing DTFT’s: an example
Consider 
an , q1 ≤ n ≤ q2
x[n] =
0, otherwise
Then
q2
X
X(Ω) = an e−jnΩ
n=q1
Xq2
= (ae−jΩ )n
n=q1

(ae−jΩ )q1 − (ae−jΩ )q2 +1

=
1 − ae−jΩ
In the last step, we used the formula
q2
X rq1 − rq2 +1
rn = ,
n=q1
1−r

valid whenever q1 and q2 are integers with q2 > q1 and r is any real or
complex number.
Maxim Raginsky Lecture X: Discrete-time Fourier transform
Computing DTFT’s: another example
Consider the signal
x[n] = an u[n],
where |a| < 1. Then
∞
X
X(Ω) = an e−jnΩ
n=0
X∞
= (ae−jΩ )n
n=0
1
= ,
1 − ae−jΩ
where we used the formula
∞
X 1
rn = ,
n=0
1−r

valid for any real or complex number r satisfying |r| < 1.

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Computing DTFT’s: another example
Consider the rectangular pulse

1, n = −q, −q + 1, . . . , q − 1, q
x[n] =
0, otherwise

Then
q
X
X(Ω) = e−jnΩ
n=−q

(e−jΩ )−q − (e−jΩ )q+1

=
1 − e−jΩ
jqΩ
e − e−jqΩ e−jΩ ejΩ/2
= · jΩ/2
1 − e−jΩ e
j(q+1/2)Ω −j(q+1/2)Ω
e −e
=
ejΩ/2 − e−jΩ/2
sin[(q + 1/2)Ω]
=
sin(Ω/2)

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Inverse DTFT
We can recover the original signal x[n] from its DTFT X(Ω) via the
inverse DTFT formula
Z 2π
1
x[n] = X(Ω)ejnΩ dΩ.
2π 0
Proof: use orthonormality of complex exponentials –
Z Z ∞
!
2π 2π
1 jnΩ 1 X
X(Ω)e dΩ = x[m]e −jmΩ
ejnΩ dΩ
2π 0 2π 0 m=−∞
∞ Z 2π
X 1
= x[m] · ej(n−m)Ω dΩ
m=−∞
2π 0
| {z }
=δ[n−m]
∞
X
= x[m]δ[n − m],
m=−∞
= x[n]

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Properties of the DTFT

Like its continuous-time counterpart, the DTFT has several very useful
properties. These are listed in any text on signals and systems. We will
take a look at a couple of them.

First of all, the DTFT is linear: if

x1 [n] ↔ X1 (Ω) and x2 [n] ↔ X2 (Ω),

then
c1 x1 [n] + c2 x2 [n] ↔ c1 X1 (Ω) + c2 X2 (Ω)
for any two constants c1 , c2 .

The proof is obvious from definitions.

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Convolution in time domain
If x[n] ↔ X(Ω) and v[n] ↔ V (Ω), then

x[n] ⋆ v[n] ↔ X(Ω)V (Ω).

Proof: let y[n] = x[n] ⋆ v[n]. Then

∞ ∞ ∞
!
X X X
−jnΩ
Y (Ω) = (x[n] ⋆ v[n])e = x[k]v[n − k] e−jnΩ
n=−∞ n=−∞ k=−∞
∞ ∞
!
X X
= x[k] v[n − k]e−jnΩ
k=−∞ n=−∞
∞ ∞
!
X X
′ −j(n′ +k)Ω
= x[k] v[n ]e
k=−∞ n′ =−∞
∞
! ∞
!
X X
= x[k]e−jkΩ v[n]e−jnΩ
k=−∞ n=−∞
| {z }| {z }
=X(Ω) =V (Ω)

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Parseval’s theorem
If x[n] and v[n] are real-valued signals, then
∞ Z 2π
X 1
x[n]v[n] = X(Ω)V (Ω)dΩ.
n=−∞
2π 0

Proof:
∞ ∞  Z 2π 
X X 1 jΩn
x[n]v[n] = x[n] V (Ω)e dΩ
n=−∞ n=−∞
2π 0
Z !
2π ∞
1 X
jΩn
= V (Ω) x[n]e dΩ
2π 0 n=−∞
Z !
2π ∞
1 X
−j(−Ω)n
= V (Ω) x[n]e dΩ
2π 0 n=−∞
| {z }
=X(−Ω)
Z 2π
1
= V (Ω)X(Ω)dΩ
2π 0

where we used the fact that x[n] is real-valued.

Maxim Raginsky Lecture X: Discrete-time Fourier transform
Parseval’s theorem: cont’d

An important consequence of Parseval’s theorem is that the signal energy

∞
X
x2 [n]
n=−∞

can be computed also in the frequency domain:

∞ Z 2π
X 1
x2 [n] = |X(Ω)|2 dΩ
n=−∞
2π 0

Maxim Raginsky Lecture X: Discrete-time Fourier transform

Summary of the DTFT
The discrete-time Fourier transform (DTFT) gives us a way of
representing frequency content of discrete-time signals.

The DTFT X(Ω) of a discrete-time signal x[n] is a function of a

continuous frequency Ω. One way to think about the DTFT is to view
x[n] as a sampled version of a continuous-time signal x(t):

x[n] = x(nT ), n = . . . , −2, −1, 0, 1, 2, . . . ,

where T is a sufficiently small sampling step. Then X(Ω) can be thought

of as a discretization of X(ω).

Due to discrete-time nature of the original signal, the DTFT is

2π-periodic. Hence, Ω = 2π is the highest frequency component a
discrete-time signal can have.

The DTFT possesses several important properties, which can be

exploited both in calculations and in conceptual reasoning about
discrete-time signals and systems.
Maxim Raginsky Lecture X: Discrete-time Fourier transform