Signals & System

Lecture 11
Discrete Fourier Transform

Dr. Tahir Zaidi

Lecture 11: Discrete Fourier Transform
Sampling Discrete-time systems (2 lectures): Sampling
theorem, discrete Fourier transform

Specific objectives for today:

• Discrete Fourier transform
• Examples
• Convergence & properties
• Convolution

2/13
 Lecture 11: Resources
Core reading
SaS, O&W, 5.1-5.4

Background reading
MIT Lectures 9 and 10

3/13
 Reminder: CT Fourier Transform
CT Fourier transform maps a time domain frequency
signal to the frequency domain via

x(t )  1
2 
X ( j )e jt d

X ( j )   x(t )e  jt dt


The Fourier transform is used to

• Analyse the frequency content of a signal
• Design a system/filter with particular properties
• Solve differential equations in the frequency domain
using algebraic operators
Note that the transform/integral is not defined for some
signals (infinite energy)

4/13
 Derivation of the DT Fourier Transform
By analogy with the CT Fourier transform, we might “guess”

X (e j )   x[ n
n  
]e  jn

This is because tn, & the integral operator represents the

limit of a sum as the sum’s width tends to zero.
X(ej) is periodic of period 2, so is ejn. Try substituting
into the inverse Fourier transform with integral over 2:

k 


 jk jn
x[n]  1
2 x[ k ]e e d
2

 


j ( n  k )
 2
1
k  
x[ k ] e d
2

 x[n]
which is the original DT signal.

5/13
 Discrete Time Fourier Transform
The DT Fourier transform analysis and synthesis
equations are therefore:

X (e j )   x[ n
n  
]e  jn

x[n]  1
2 
2
X (e j )e jn d

The function X(ej) is referred to as the discrete-time

Fourier transform and the pair of equations are referred
to as the Fourier transform pair
X(ej) is sometimes referred to as the spectrum of x[n]
because it provides us with information on how x[n] is
composed of complex exponentials at different
frequencies
It converges when the signal is absolutely summable


n  
| x[n] | 
6/13
Example 1: 1st Order System, Decay Power
Calculate the DT Fourier transform of the signal:
x[n]  a nu[n], | a | 1 stable system
Therefore: 
X (e )   a nu[n]e  jn
j

n  

1
  (ae  j n
) 
n 0 1  ae  j

a=0.8

7/13
 Example 2: Rectangular Pulse
Consider the rectangular pulse
N1=2
1 | n | N1
x[n]  
0 | n | N1
and the Fourier transform is
N1
X ( e j )  e
n   N1
 j n

2 N1
 e jN1  e  jm
m 0

e j ( N1 1/ 2 ) 1  e  j ( 2 N1 1)
 j (1/ 2 )
e 1  e  j
e j ( N1 1/ 2 )  e  j ( N1 1/ 2 )

e j / 2  e  j  / 2
sin( ( N1  1 / 2))

sin( / 2)
8/13
 Example 3: Impulse Signal

Fourier transform of the DT impulse signal is


F{ [n]}    [
n  
n ]e  jn
1

9/13
Properties: Periodicity, Linearity & Time
The DT Fourier transform is always periodic with
period 2, because
X(ej(+2)) = X(ej)
It is relatively straightforward to prove that the DT
Fourier transform is linear, i.e.
F F
x1[n]  X 1 (e ), x2 [n]  X 2 (e j )
j

F
ax1[n]  bx2 [n]  aX 1 (e j )  bX 2 (e j )

Similarly, if a DT signal is shifted by n0 units of time

F
x[n]  X (e j )
F
x[n  n0 ]  e  jn0 X (e j )
10/13
 Convolution in the Frequency Domain
Like continuous time signals and systems, the time-domain
convolution of two discrete time signals can be
represented as the multiplication of the Fourier
transforms
If x[n], h[n] and y[n] are the input, impulse response and
output of a discrete-time LTI system so, by convolution,
y[n] = x[n]*h[n]
Then
Y(ej) = X(ej)H(ej)
The proof is analogous to proof used for the convolution of
continuous time Fourier transforms
Convolution in the discrete time domain is replaced by
multiplication in the frequency domain.

11/13
 Example: 1st Order System
Consider an LTI system with impulse response
h[n]=anu[n], |a|<1
and the system input is
x[n]=bnu[n], |b|<1
The DT Fourier transforms are:
1 1
H (e j )  , X ( e j
) 
1  ae  j 1  be  j
So
j 1
Y (e ) 
(1  ae  j )(1  be  j )
Expressing as partial fractions, assuming ab:
a 1 b 1
Y (e j )  
a  b (1  ae  j ) a  b (1  be  j )
and spotting the inverse Fourier transform
a n1u[n] b n1u[n]
y[n]  
a b a b

12/13
 Lecture 11: Summary
Apart from a slightly difference, the Fourier transform of a
discrete time signal is equivalent to the continuous time
formulae 
X (e j )   x[ n
n  
]e  jn

x[n]  1
2 
2
X (e j )e jn d
They have similar properties to the continuous time Fourier
transform for linearity, time shifts, differencing and
accumulation
The main result is that like continuous time signals and
systems, convolution in the time domain is replaced by
multiplication in the frequency domain.
Y(ej) = X(ej)H(ej)

13/13
 Lecture 11: Exercises
Theory
SaS, O&W, 5.1-5.3, 5.19

14/13