ELG 3120 Signals and Systems

Chapter 5

Chapter 5 The Discrete-Time Fourier Transform

5.0 Introduction

There are many similarities and strong parallels in analyzing continuous-time and discretetime signals.
There are also important differences. For example, the Fourier series representation of a
discrete-time periodic signal is finite series, as opposed to the infinite series representation
required for continuous-time period signal.
In this chapter, the analysis will be carried out by taking advantage of the similarities
between continuous-time and discrete-time Fourier analysis.

5.1 Representation of Aperiodic Signals: The discrete-Time Fourier

Transform
5.1.1 Development of the Discrete-Time Fourier Transform
Consider a general sequence that is a finite duration. That is, for some integers N 1 and N 2 , x[n]
equals to zero outside the range N 1 n N 2 , as shown in the figure below.

We can construct a periodic sequence ~

x [n] using the aperiodic sequence x[n] as one period. As
~
we choose the period N to be larger, x [n] is identical to x[n] over a longer interval, as N ,
~
x [n] = x[n] .
Based on the Fourier series representation of a periodic signal given in Eqs. (3.80) and (3.81), we
have

1/5

Yao

ELG 3120 Signals and Systems

a e

~
x [ n] =

k =< N >

ak =

jk (2 / N ) n

~x [n]e

Chapter 5

jk (2 / N ) n

(5.1)
.

(5.2)

k= N

If the interval of summation is selected to include the interval N 1 n N 2 , so ~

x [n] can be
replaced by x[n] in the summation,
ak =

1
N

N2

x[n]e jk ( 2 / N ) n =

k = N1

1
N

x[n]e

jk ( 2 / N ) n

(5.3)

k =

Defining the function

j

X (e ) =

x[n ]e

j n

(5.4)

n =

So a k can be written as

ak =

1
X (e jk 0 ) ,
N

(5.5)

Then ~
x [n] can be expressed as
~
x [n] =

1
1
X (e jk 0 )e jk (2 / N ) n =
2
k =< N > N

X (e

k =< N >

jk 0

)e jk ( 2 / N ) n 0 .

(5.6)

As N ~
x [n] = x[n] , and the above expression passes to an integral,

x[n ] =

1
2

X (e j )e jn d ,

(5.7)

The Discrete-time Fourier transform pair:

x[n ] =
j

1
2

X (e ) =

X (e j )e jn d ,

x[n]e

n =

(5.8)

j n

(5.9)

2/5

Yao

ELG 3120 Signals and Systems

Chapter 5

Eq. (5.8) is referred to as synthesis equation, and Eq. (5.9) is referred to as analysis equation
and X (e jk 0 ) is referred to as the spectrum of x[n] .
5.1.2 Examples of Discrete-Time Fourier Transforms
Example: Consider x[n ] = a n u[n] ,

X (e j ) =

x[n]e jn =

n =

a < 1.

n=

n= 0

(5.10)

a n u[n ]e jn = ae j

1
.
1 ae j

(5.11)

The magnitude and phase for this example are show in the figure below, where a > 0 and a < 0
are shown in (a) and (b).

n
Example: x[n] = a , a < 1 .

X (e j ) =

a u[n ]e jn =
n

n =

(5.12)
1

n =

n =0

a n e jn + a n e jn

Let m = n in the first summation, we obtain

X (e j ) =

m =1

n =0

a u[ n]e jn = a m e jm + a n e jn
n

n =

.
=

(5.13)

ae
1
1 a
+
=
j
j
1 ae
1 ae
1 2 a cos + a 2
2

3/5

Yao

ELG 3120 Signals and Systems

Chapter 5

Example: Consider the rectangular pulse

1,
x[n ] =
0,

X ( j ) =

n N1
n > N1
N1

j n

n= N
1

(5.14)

sin (N1 + 1 / 2 )
.
sin ( / 2 )

(5.15)

This function is the discrete counterpart of the sic

function, which appears in the Fourier transform of
the continuous-time pulse.
The difference between these two functions is that
the discrete one is periodic (see figure) with period of 2 , whereas the sinc function is aperiodic.
5.1.3 Convergence
The equation X (e j ) =

x[n ]e

j n

converges either if x[n] is absolutely summable, that is

n =

x[n] < ,

(5.16)

n =

or if the sequence has finite energy, that is

x[n] < .

(5.17)

n =

4/5

Yao

ELG 3120 Signals and Systems

Chapter 5

And there is no convergence issues associated with the synthesis equation (5.8).
If we approximate an aperidic signal x[n] by an integral of complex exponentials with
frequencies taken over the interval W ,
x[ n] =

1
2

X ( e j )e j n d ,

(5.18)

and x[n ] = x[n ] for W = . Therefore, the Gibbs phenomenon does not exist in the discrete-time
Fourier transform.

Example: the approximation of the impulse response with different values of W .

For W = / 4, 3 / 8, / 2, 3 / 4, 7 / 8, , the approximations are plotted in the figure below.
)
We can see that when W = , x[n] = x[n ] .

5/5

Yao

ELG 3120 Signals and Systems

Chapter 5

5.2 Fourier transform of Periodic Signals

For a periodic discrete-time signal,
x[n ] = e j 0 n ,

(5.19)

its Fourier transform of this signal is periodic in with period 2 , and is given
+

2 (

X (e ) =

l =

2l ) .

(5.20)

Now consider a periodic sequence x[n] with period N and with the Fourier series representation
x[n ] =

a e

k =< N >

jk ( 2 / N ) n

(5.21)

The Fourier transform is

+

X (e ) =

2a (

k =

2k
).
N

(5.22)

Example: The Fourier transform of the periodic signal

x[n ] = cos 0 n =

1 j0n 1 j0 n
2
e
+ e
, with 0 =
,
2
2
3

(5.23)

is given as

2
2

X (e j ) =
+ +
,
3
3

< .

6/5

(5.24)

Yao

ELG 3120 Signals and Systems

Chapter 5

Example: The periodic impulse train

x[n ] =

[n kN ] .

(5.25)

k =

The Fourier series coefficients for this signal can be calculated

ak =

x[n ]e

jk (2 / N ) n

(5.26)

n =< N >

Choosing the interval of summation as 0 n N 1 , we have

ak =

1
.
N

(5.27)

The Fourier transform is

X (e j ) =

2
N

k =

2k
.
N

(5.28)

7/5

Yao

ELG 3120 Signals and Systems

Chapter 5

5.3 Properties of the Discrete-Time Fourier Transform

Notations to be used
X (e j ) = F {x[n]},

x[n ] = F 1 X (e j ) ,
F
x[n ]
X (e j ) .

5.3.1 Periodicity of the Discrete-Time Fourier Transform

The discrete-time Fourier transform is always periodic in with period 2 , i.e.,

( )

X e j ( +2 ) = X e j .

(5.29)

5.3.2 Linearity
F
F
If x1 [n]
X 1 (e j ) , and x 2 [n]
X 2 (e j ) ,

then
F
ax1[n] + bx2 [n]
aX1 (e j ) + bX 2 (e j )

(5.30)

5.3.3 Time Shifting and Frequency Shifting

F
If x[n ]
X (e j ) ,

then
F
x[ n n0 ]
e jn0 X ( e j )

(5.31)

and
F
e j0n x[ n]
X ( e j ( 0 ) )

(5.32)

8/5

Yao

ELG 3120 Signals and Systems

Chapter 5

5.3.4 Conjugation and Conjugate Symmetry

F
If x[n ]
X (e j ) ,

then
F
x *[n]
X * (e j )

(5.33)

If x[n] is real valued, its transform X (e j ) is conjugate symmetric. That is

X (e j ) = X * (e j )

(5.34)

From this, it follows that Re X (e j ) is an even function of and Im X (e j ) is an odd

function of . Similarly, the magnitude of X (e j ) is an even function and the phase angle is
an odd function. Furthermore,

F
Ev{x[n]}
Re X (e j ,

(5.35)

and

F
Od {x[ n]}
j Im X (e j .

(5.36)

5.3.5 Differencing and Accumulation

F
If x[n ]
X (e j ) ,

then

F
x[n] x[n 1]
1 e j X (e j ) .

(5.37)

For signal

y[ n] =

x[ m] ,

(5.38)

m =

its Fourier transform is given as

9/5

Yao

ELG 3120 Signals and Systems

Chapter 5

+
1
j
j0
x[ m]
X ( e ) + X (e ) ( 2k ) .

j
1e
m =
m =
n

(5.39)

The impulse train on the right-hand side reflects the dc or average value that can result from
summation.
For example, the Fourier transform of the unit step x[n ] = u[n ] can be obtained by using the
accumulation property.
F
We know g[n ] = [n]
G(e j ) = 1 , so

x[n ] =

F
g[m]

m =

+
+
1
1
j
j0
G
e
+
G
e

k
=
+
(
)
(
)
(
2
)

( 2k ) .
1 e j
1 e j
k =
k =
(5.40)

5.3.6 Time Reversal

F
If x[n ]
X (e j ) ,

then
F
x[n]
X (e j ) .

(5.41)

5.3.7 Time Expansion

For continuous-time signal, we have
F
x( at)

1 j
X
.
a a

(5.42)

For discrete-time signals, however, a should be an integer. Let us define a signal with k a
positive integer,
x[n / k ],
x( k ) [n] =
0,

if n is a multiple of k
.
if n is not a multiple of k

(5.43)

x( k ) [n] is obtained from x[n] by placing k 1 zeros between successive values of the original
signal.
The Fourier transform of x( k ) [n] is given by
10/5

Yao

ELG 3120 Signals and Systems

X ( k ) (e j ) =

x( k ) [n ]e jn =

n =

Chapter 5

x ( k ) [rk ]e jrk =

r =

x[r ]e

j ( k ) r

= X (e jk ) .

(5.44)

r =

That is,
F
x(k ) [n]
X (e jk ) .

(5.45)

For k > 1 , the signal is spread out and slowed down in time, while its Fourier transform is
compressed.
Example: Consider the sequence x[n] displayed in the figure (a) below. This sequence can be
related to the simpler sequence y[n] as shown in (b).

x[n ] = y( 2 ) [n ] + 2 y (2 ) [ n 1] ,
where
y[n / 2],
y2 [ n ] =
0,

if n is even
if n is odd

The signals y (2 ) [ n] and 2 y ( 2) [n 1] are depicted in (c) and (d).

As can be seen from the figure below, y[n] is a rectangular pulse with N 1 = 2 , its Fourier
transform is given by
Y (e j ) = e j 2

sin( 5 / 2)
.
sin( / 2)

Using the time-expansion property, we then obtain

11/5

Yao

ELG 3120 Signals and Systems

F
y ( 2) [n]
e j 4

Chapter 5

sin( 5 )
sin( )

F
2 y ( 2) [n 1]
2e j 5

sin( 5 )
sin( )

Combining the two, we have

sin( 5 )
X (e j ) = e j 4 (1 + 2e j )
.
sin( )
5.3.8 Differentiation in Frequency
F
If x[n ]
X (e j ) ,

Differentiate both sides of the analysis equation X (e j ) =

x[n ]e

jn

n =

dX (e ) +
= jnx[n]e jn .
d
n=

(5.46)

The right-hand side of the Eq. (5.46) is the Fourier transform of jnx[n] . Therefore, multiplying
both sides by j , we see that

dX (e j )
nx[n] j
d .
F

(5.47)

5.3.9 Parsevals Relation

F
If x[n ]
X (e j ) , then we have

x[n] =

n =

1
2

X (e j ) d

(5.48)

12/5

Yao

ELG 3120 Signals and Systems

Chapter 5

Example: Consider the sequence x[n] whose Fourier transform X (e j ) is depicted for
in the figure below. Determine whether or not, in the time domain, x[n] is periodic,
real, even, and /or of finite energy.

The periodicity in time domain implies that the Fourier transform has only impulses located
at various integer multiples of the fundamental frequency. This is not true for X (e j ) . We
conclude that x[n] is not periodic.
Since real-valued sequence should have a Fourier transform of even magnitude and a phase
function that is odd. This is true for X (e j ) and X (e j ) . We conclude that x[n] is real.
If x[n] is real and even, then its Fourier transform should be real and even. However, since

X (e j ) = X (e j ) e j 2 , X (e j ) is not real, so we conclude that x[n] is not even.

Based on the Parsevals relation, integrating X (e j )

from to will yield a finite

quantity. We conclude that x[n] has finite energy.

5.4 The convolution Property
If x[n] , h[n] and y[n] are the input, impulse response, and output, respectively, of an LTI
system, so that

y[ n] = x[n ] h[n] ,

(5.49)

then,
Y (e j ) = X (e j ) H (e j ) ,

(5.50)

13/5

Yao

ELG 3120 Signals and Systems

Chapter 5

where X (e j ) , H (e j ) and Y (e j )
respectively.

are the Fourier transforms of x[n] , h[n] and y[n] ,

Example: Consider the discrete-time ideal lowpass filter with a frequency response H (e j )
illustrated in the figure below. Using as the interval of integration in the synthesis
equation, we have

h[ n] =

1
2

1
2

H (e j )e jn d

e jn d =

sin c n
n

The frequency response of the discrete-time

ideal lowpass filter is shown in the right figure.
Example: Consider an LTI system with impulse response
h[n ] = n u[n] ,

< 1,

and suppose that the input to the system is

x[n ] = n u[n] ,

< 1.

The Fourier transforms for h[n] and x[n] are

H (e j ) =

1
,
1 e j

and

X (e j ) =

1
,
1 e j

so that

Y (e j ) = H (e j ) X (e j ) =

(1 e

1
.
)(1 e j )

14/5

Yao

ELG 3120 Signals and Systems

Chapter 5

If , the partial fraction expansion of Y (e j ) is given by

A
B

Y (e j ) =
+
+
=
,
j
j
j
(1 e ) (1 e ) (1 e ) (1 e j )
We can obtain the inverse transform by inspection:
y[ n] =

1
n u[n]
n u[n ] =
n +1u[n ] n +1u[n ] .

For = ,

Y (e j ) =

1
, which can be expressed as
(1 e j ) 2

j j d
1
.

e
j

d 1 e
Using the frequency differentiation property, we have
Y (e j ) =

n n u[n] j
F

d
1

d 1 e j

To account for the factor e j , we use the time-shifting property to obtain

(n + 1) n +1u[n + 1] je j
F

d
1

d 1 e j

Finally, accounting for the factor 1 / , we have

y[ n] = (n + 1) n u[n + 1] .
Since the factor n + 1 is zero at n = 1 , so y[n] can be expressed as
y[ n] = (n + 1) n u[n] .
Example: Consider the system shown in the figure below. The LTI systems with frequency
response H lp (e j ) are ideal lowpass filters with cutoff frequency / 4 and unity gain in the
passband.

15/5

Yao

ELG 3120 Signals and Systems

Chapter 5

w1 [n] = (1) n x[ n] = e j n x[n]

W1 (e j ) = X (e j ( ) ) .

W2 (e j ) = H lp (e j ) X (e j ( ) ) .

w3 [ n] = (1) n w2 [n ] = e jn w2 [ n]

W3 (e j ) = W2 (e j ( ) ) = H lp (e ( j ) ) X (e j ( 2 ) ) .

W3 (e j ) = W2 (e j ( ) ) = H lp (e j ) ) X (e j ) (Discrete-Fourier

transforms

are

always

periodic with period of 2 ).

W4 (e j ) = H lp (e j ) ) X (e j ) .

Y (e j ) = W3 (e j ) + W4 (e j ) = H lp (e ( j ) ) + H lp (e j ) X (e j ) .

The overall system has a frequency response

H lp (e j ) = H lp (e ( j ) ) + H lp (e j ) X (e j ) ,

which is shown in figure (b).

The filter is referred to as bandstop filter, where
the stop band is the region / 4 < < 3 / 4 .
It is important to note that not every discrete-time LTI system has a frequency response. If an
LTI system is stable, then its impulse response is absolutely summable; that is,
+

h[n] < ,

(5.51)

n =

5.5 The multiplication Property

Consider y[n] equal to the product of x1 [n] and x 2 [n] , with Y (e j ) , X 1 (e j ) , and X 2 (e j )
denoting the corresponding Fourier transforms. Then

16/5

Yao

ELG 3120 Signals and Systems

F
y[ n] = x1 [n] x2 [n ]

Chapter 5

1
2

X 1 (e j ) X 2 (e j ( ) ) d

(5.52)

Eq. (5.52) corresponds to a periodic convolution of X 1 (e j ) and X 2 (e j ) , and the integral in

this equation can be evaluated over any interval of length 2 .

Example: Consider the Fourier transform of a signal x[n] which the product of two signals; that
is
x[n ] = x1 [n] x2 [n]

where

x1 [n] =

sin( 3n / 4)
, and
n

x 2 [n ] =

sin(n / 2)
.
n

Based on Eq. (5.52), we may write the Fourier transform of x[n]

X (e j ) =

1
2

X 1 (e j ) X 2 (e j ( ) )d .

(5.53)

Eq. (5.53) resembles aperiodic convolution, except for the fact that the integration is limited to
the interval of < < . The equation can be converted to ordinary convolution with
integration interval < < by defining
X (e j )
X 1 (e j ) = 1
0

for < <

otherwise

Then replacing X 1 ( e j ) in Eq. (5.53) by X 1 (e j ) , and using the fact that X 1 (e j ) is zero for
< < , we see that
X (e j ) =

1
2

X 1 (e j ) X 2 (e j ( ) )d =

1
2

X 1 (e j ) X 2 (e j ( ) )d .

Thus, X (e j ) is 1 / 2 times the aperiodic convolution of the rectangular pulse X 1 (e j ) and the
periodic square wave X 2 (e j ) . The result of thus convolution is the Fourier transform X (e j ) ,
as shown in the figure below.

17/5

Yao

ELG 3120 Signals and Systems

Chapter 5

5.6 Tables of Fourier Transform Properties and Basic Fourier Transform

Paris

18/5

Yao

ELG 3120 Signals and Systems

Chapter 5

19/5

Yao

ELG 3120 Signals and Systems

Chapter 5

5.7 Duality
For continuous-time Fourier transform, we observed a symmetry or duality between the analysis
and synthesis equations. For discrete-time Fourier transform, such duality does not exist.
However, there is a duality in the discrete-time series equations. In addition, there is a duality
relationship between the discrete-time Fourier transform and the continuous-time Fourier
series.
5.7.1 Duality in the discrete-time Fourier Series
Consider the periodic sequences with period N, related through the summation
f [m ] =

1
g (r )e jr ( 2 / N ) m .

N r =< N >

(5.54)

If we let m = n and r = k , Eq. (5.54) becomes

f [ n] =

1
g ( r )e jr ( 2 / N ) n .
N
k =< N >

(5.55)

Compare with the two equations below,

a e

x[n] =

jk ( 2 / N ) n

k= N

ak =

1
N

we fond that

FS
f [n]

x[n]e

(3.80)

jk ( 2 / N ) n

k= N

(3.81)

1
g ( r ) corresponds to the sequence of Fourier series coefficients of f [n ] . That is
N
1
g[ k ] .
N

(5.56)

This duality implies that every property of the discrete-time Fourier series has a dual. For
example,
FS
x[n n 0 ]
a k e jk ( 2 / N ) n 0

(5.57)

FS
e jm ( 2 / N ) n
a k m

(5.58)

20/5

Yao

ELG 3120 Signals and Systems

Chapter 5

are dual.
Example: Consider the following periodic signal with a period of N = 9 .
1 sin( 5n / 9)
9 sin(n/9) ,
x[n ] =
5 ,
9

n multiple of 9

(5.59)
n = multiple of 9

We know that a rectangular square wave has Fourier coefficients in a form much as in Eq. (5.59).
Duality suggests that the coefficients of x[n] must be in the form of a rectangular square wave.
Let g[n] be a rectangular square wave with period N = 9 ,
1,
g[ n ] =
0,

n 2
2< n 4

(5.60)

The Fourier series coefficients b k for g[n] can be given (refer to example on page 27/3)
1 sin( 5k / 9)
9 sin(k/9) ,
bk =
5 ,
9

k multiple of 9

(5.61)

k = multiple of 9

The Fourier analysis equation for g[n] can be written

1 2
bk = (1)e j 2nk / 9 .
9 n =2

(5.62)

Interchanging the names of the variable k and n and noting that x[n ] = bk , we find that

x[n ] =

1 2
(1)e j 2nk / 9 .

9 k =2

Let k ' = k in the sum on the right side, we obtain

x[n ] =

1 2
(1)e + j 2nk ' / 9 .

9 k =2

21/5

Yao

ELG 3120 Signals and Systems

Chapter 5

Finally, moving the factor 1 / 9 inside the summation, we see that the right side of the equation
has the form of the synthesis equation for x[n] . Thus, we conclude that the Fourier coefficients
for x[n] are given by
1 / 9,
ak =
0,

k 2
2< k 4

with period of N = 9 .

5.8 System Characterization by Linear Constant-Coefficient Difference

Equations
A general linear constant-coefficient difference equation for an LTI system with input x[n] and
output x[n] is of the form
N

a
k =0

k y[n k ] = bk x[n k ] ,

(5.63)

k =0

which is usually referred to as Nth-order difference equation.

There are two ways to determine H (e j ) :

The first way is to apply an input x[n ] = e jn to the system, and the output must be of the
form H (e j )e j n . Substituting these expressions into the Eq. (5.63), and performing some
algebra allows us to solve for H (e j ) .
The second approach is to use discrete-time Fourier transform properties to solve for
H (e j ) .

Based on the convolution property, Eq. (5.63) can be written as

Y (e j )
H (e ) =
.
X (e j )
j

(5.64)

Applying the Fourier transform to both sides and using the linearity and time-shifting properties,
we obtain the expression
N

k =0

k =0

a k e jk Y (e j ) = bk e jk X (e j ) .

(5.65)

22/5

Yao

ELG 3120 Signals and Systems

Chapter 5

or equivalently
Y (e j )
H (e ) =
=
X (e j )
j

k =0
N

bk e jk

a e jk
k =0 k

(5.66)

Example: Consider the causal LTI system that is characterized by the difference equation,

y[ n] ay[n 1] = x[n] ,

a < 1.

The frequency response of this system is

H (e j ) =

Y (e j )
1
=
.
j
X (e ) 1 ae j

The impulse response is given by

h[n ] = a n u[n] .
Example: Consider a causal LTI system that is characterized by the difference equation

y[ n]

3
1
y[n 1] + y[n 2] = 2 x[n] .
4
8

1. What is the impulse response?

n

1
2. If the input to this system is x[n ] = u[n] , what is the system response to this input signal?
4
The frequency response is
H (e j ) =

1 12 e

1
2
.
=

j
2

3
+ 18 e
(1 4 e )(1 14 e j )

After partial fraction expansion, we have

H (e j ) ==

4
2
,

1 12 e
1 14 e j

The inverse Fourier transform of each term can be recognized by inspection,

n

1
1
h[n ] = 4 u[n] 2 u[n ] .
2
4

23/5

Yao

ELG 3120 Signals and Systems

Chapter 5

Using Eq. (5.64) we have

2
1
Y (e j ) = H (e j ) X (e j ) =

3 j
1 j
1 j
(1 4 e )(1 4 e ) 1 4 e
.
=

(1 e
3
4

2
)(1 e j )(1 14 e j )
1
4

After partial-fraction expansion, we obtain

Y (e j ) = H (e j ) X (e j ) =

4
2

1 14 e
1 14 e j

8
1 12 e j

The inverse Fourier transform is

n
2
1 n
1
1
y[ n] = 4 2( n + 1) + 8 u[n ] .
2
2
4

24/5

Yao