CHAPTER 5:

CHAPTER 5:
D
D
ISCRETE
ISCRETE
F
F
OURIER
OURIER
T
T
RANSFORM (DFT)
RANSFORM (DFT)
Lesson #19: DTFT of DT periodic signals
Lesson #20: DFT and Inverse DFT
Lesson #21: DFT properties
Lesson #22: Fast Fourier Transform (FFT)
Lesson #23: Applications of DFT/FFT
Lesson #24: Using of DFT/FFT
Lecture #19
Lecture #19
DTFT of periodic signals
DTFT of periodic signals
1. Review of Fourier Transforms (FT)
2. Fourier Series expansions
3. DTFT of periodic signals
FT of CT periodic signals
FT of CT periodic signals
T
dt e t x
T
a e a t x
t jk
T
k
t jk
k
k

2
; ) (
1
; ) (
0
0 0
= = =

Discrete and aperiodic in

frequency domain
Continuous and periodic
in time domain
FT of CT aperiodic signals
FT of CT aperiodic signals
Continuous and aperiodic
in time domain
1
Continuous and aperiodic in
frequency domain
FT of DT aperiodic signals
FT of DT aperiodic signals
Discrete and aperiodic
in time domain
Continuous and periodic in
frequency with period 2
Recapitulation
Recapitulation
Can guess?
Can guess?
Lecture #19
Lecture #19
DTFT of periodic signals
DTFT of periodic signals
1. Review of Fourier Transforms (FT)
2. Fourier Series expansions
3. DTFT of periodic signals

> <

> <
= =
n
n jk
k
n jk
k
k
e n x

a e a n x
0 0
] [
1
; ] [
N
2
0

=
dt e t x
T
a e a t x
t jk
T
k
t jk
k
k
0 0
) (
1
; ) (

= =
CT periodic signals with period T:
DT periodic signals with period N:
Note: finite sums over an interval length of one periodic N
n ) N k ( j
n
N
2
) N k ( j n
N
2
jk
n jk
0 0
e e e e
+

= = =
T
2
0

=
Fourier Series expansion
Fourier Series expansion
Given a DT periodic signals with period N:
Example of Fourier Series expansion
Example of Fourier Series expansion
[ ] [ ]
k
p n n k

=
= .

N
1
e ] n [ p
N
1
a
1 N
0 n
N / n 2 jk
k
= =

=

. . . -2N -N 0 N 2N . . . . .

=
=
1
0
2
] [

k
n

jk
k
e a n p

Lecture #19
Lecture #19
DTFT of periodic signals
DTFT of periodic signals
1. Review of Fourier Transforms (FT)
2. Fourier Series expansions
3. DTFT of periodic signals
CT periodic signals with period T:
DT periodic signals with period N:
DTFT of periodic signals
DTFT of periodic signals
) k ( a 2 ) ( X e a ) t ( x
0
k
k
F
t jk
k
k
0
= =


=

=
) k ( a 2 ) ( X ] n [ x
0
k
k
F
=

=
. . . -2N -N 0 N 2N . . . . . . . . n
Example of calculating DTFT of
Example of calculating DTFT of
periodic signals
periodic signals
( )


=

=
|

\
|

= =
k k
0 k
N
2
k
N
2
k a 2 ) ( P
2/N 2/N 2/N 2/N 2/N
. . . -4/N -2/N 0 2/N 4/N . . . .
Height = 1
Spacing = N
Height = 2/N
Spacing = 2/N
Another approach to get DTFT of
Another approach to get DTFT of
periodic signals
periodic signals
0
[ ] 0 1
[ ]
0 otherwise
x n n
x n
,

=

, .

0 N-1
x(n) is periodic signal; x
0
(n) is a part of x(n) that is repeated
Another approach (cont)
Another approach (cont)
0
[ ] 0 1
[ ]
0 otherwise
x n n
x n
,

=

, .

0 0 0
[ ] [ ] [ ] [ ] [ ] [ ]
k k k
x n x n k x n n k x n n k

= = =
= = =

p(n) in previous
example
0 0
[ ] [ ] [ ] ( ) ( ) ( )
F
x n x n p n X P X = =
Another approach (cont)
Another approach (cont)
0 0
[ ] [ ] [ ] ( ) ( ) ( )
F
x n x n p n X P X = =

=
|

\
|
=
k
k

k X

X X
)
2
( )
2
(
2
)
2
(
2
) ( ) (
0
0

It has N distinct values at k = 0, 1, , N-1

Inverse DTFT
Inverse DTFT
{ }

=

= =

=
= =
1
0
2
0
2
0
0
2
0
0
2
0
1
)
2
(
1
)
2
( )
2
(
1
)
2
( )
2
(
2
2
1
) (
2
1
] [ ) (

n k
j
k
n j
n j
k
n j
e

k X

d e

k X

d e

k X

d e X n x X DFT

This is obtained from this property of the impulse:

<
=

elsewhere
b t a t f
dt t t t f
b
a
0
) (
) ( ) (
0 0
0

Summary
Summary
Procedure to calculate DTFT of
Procedure to calculate DTFT of
periodic signals
periodic signals
Step 1:
Start with x
0
(n) one period of x(n), with zero everywhere else
Step 2:
Find the DTFT X
0
() of the signal x
0
[n] above
Step 3:
Find X
0
() at N equally spacing frequency points X
0
(k2/N)
Step 4:
Obtain the DTFT of x(n):

=
k

k

k X

X )
2
( )
2
(
2
) (
0

Example of calculating DTFT of
Example of calculating DTFT of
periodic signals
periodic signals

=

+ + = =

3
3
0
0 0
2 1 ) ( ) (
j j
n
n j
e e e n x X
k = 0 X
0
(0) = 4; k = 1 X
0
(1) = 1+j
k = 2 X
0
(2) = -2; k = 3 X
0
(3) = 1-j
0 1 2 3
Example (cont)
Example (cont)
Example (cont)
Example (cont)
a) Draw the magnitude plot of the FT of a CT sinusoid x(t), that
has a frequency of 24 Hz
b) Sample this signal x(t) at 40 Hz. Draw the magnitude plot of
the FT of the sampled signal
c) Reconstruct a CT signal from the samples above with a LPF, it
will look like a CT sinusoid of what frequency?
d) Consider DT signal that is obtained by the sampling x(t) at a
sampling frequency of 40 Hz is x(n). Is x(n) a periodic signal?
If yes, what is its period?
e) Specify the DTFT of the DT signal x(n).
DTFT and DFS example
DTFT and DFS example
a) Draw the magnitude plot of the FT of a CT sinusoid x(t), that has
a frequency of 24 Hz
The FT of a sinusoidal has nonzero values only at certain points
DTFT and DFS examples
DTFT and DFS examples
-24 24 f [Hz]
-48 48 [rad/s]
b) Sample this signal x(t) at 40 Hz. Draw the magnitude plot of the
FT of the sampled signal
Sampled signal FT magnitude = copies of unsampled signal FT
magnitude; each copy is centered at k40(Hz) or k80(rad/s)
DTFT and DFS examples
DTFT and DFS examples
-64 -56 -24 -16 0 16 24 40 56 64 f[Hz]
-128 -48 -32 32 48 80 112 [rad/s]
f
s
= 40Hz f
s
= 40Hz
8Hz
c) Reconstruct a CT signal from the samples above with a LPF, it will
look like a CT sinusoid of what frequency?
The unit circle represents the scale of frequency range for a
signal sampled at 40Hz the reconstructed signal looks like
16Hz.
DTFT and DFS examples
DTFT and DFS examples
20
24
16
0 16 24 40 56 64 f[Hz]
32 48 80 112 [rad/s]
8Hz
d) Consider DT signal that is obtained by the sampling x(t) at
a sampling frequency of 40 Hz is x(n). Is x(n) a periodic
signal? If yes, what is its period?
The unsampled signal: x(t) = cos(2.24t)
The sampled signal:
x[n] = cos(2.24.(1/40)t) = cos(6/5)n = cos (4/5)n
The sampled signal is periodic with N = 5 N = 5 N = 5 N = 5
DTFT and DFS examples
DTFT and DFS examples
e) Specify the DTFT of the DT signal x(n).
DTFT and DFS examples
DTFT and DFS examples
Lecture #20
Lecture #20
DFT and inverse DFT
DFT and inverse DFT
1. DFT and inverse DFT formulas
2. DFT and inverse DFT examples
3. Frequency resolution of the DFT
DFT to the rescue!
DFT to the rescue!
Both CTFT and DTFT produce continuous function of
frequency cant calculate an infinite continuum of frequencies
using a computer
Most real-world data is not in the form like a
n
u(n)
DFT can be used as a FT approximation that can calculate a finite
set of discrete-frequency spectrum values from a finite set of
discrete-time samples of an analog signal
Could we calculate the frequency spectrum of a signal
using a digital computer with CTFT/DTFT?
Building the DFT formula
Building the DFT formula
Window x(n) is like multiplying
the signal by the finite length
rectangular window
Discrete time
signal x(n)
Continuous time
signal x(t)
Discrete time
signal x
0
(n)
Finite length
sample
window
Building the DFT formula (cont)
Building the DFT formula (cont)
Discrete time
signal x(n)
Continuous time
signal x(t)
Discrete time
signal x
0
(n)
Finite length
sample
window
DTFT


=

=

= =
1
0
0 0 0
] [ ] [ ) (

n
n j
n
n j
e n x e n x X
Building the DFT formula (cont)
Building the DFT formula (cont)
Discrete time
signal x(n)
Continuous time
signal x(t)
Discrete time
signal x
0
(n)
Finite length
sample
window
DTFT
Sample
at N
values
around
the unit
circle
Discrete Fourier Transform DFT X(k)
Discrete + periodic with period N
X
0
()
Continuous + periodic
with period 2
D
F
T
Notation conventions
Notation conventions
Notation conventions (cont)
Notation conventions (cont)
DFT and inverse DFT formulas
DFT and inverse DFT formulas
Notation
You only have to store N points
N
2
j
N
e W

=
Lecture #20
Lecture #20
DFT and inverse DFT
DFT and inverse DFT
1. DFT and inverse DFT formulas
2. DFT and inverse DFT examples
3. Frequency resolution of the DFT
DFT and IDFT examples
DFT and IDFT examples
Ex.1. Find the DFT of x(n) = 1, n = 0, 1, 2, , (N-1)
k = 0 X(k) = X(0) = N
k 0 X(k) = 0
DFT and IDFT examples
DFT and IDFT examples
Ex.2. Given y(n) = (n-2) and N = 8, find Y(k)
DFT and IDFT examples
DFT and IDFT examples
Ex.3. Find the IDFT of X(k) = 1, k = 0, 1, , 7.
DFT and IDFT examples
DFT and IDFT examples
Ex.4. Given x(n) = (n) + 2(n-1) +3(n-2) + (n-3) and
N = 4. Find X(k).
DFT and IDFT examples
DFT and IDFT examples
Ex.5. Given X(k) = 2(k) + 2(k-2) and N = 4. Find x(n).
DFT in matrix forms
DFT in matrix forms
(
(
(
(
(

=
(
(
(
(

=
(
(
(
(

=
= =

) 1 )( 1 ( ) 1 ( 2 1
) 1 ( 2 1
1
0
1
1
1 1 1 1
] 1 [
] 1 [
] 0 [
] 1 [
] 1 [
] 0 [
: '
1 ,..., 1 , 0 ] [ ] [

n
kn

W W W
W W W
W
X
X
X
X
x
x
x
x
define s Let
k W n x k X
K
M
M M
The N-point DFT
may be expressed
in matrix form as:
X
N
= W
N
x
N
IDFT in matrix forms
IDFT in matrix forms
(
(
(
(
(

=
(
(
(
(

=
(
(
(
(

=
= =

) 1 )( 1 ( ) 1 ( 2 1
) 1 ( 2 1
1
0
1
1
1 1 1 1
] 1 [
] 1 [
] 0 [
] 1 [
] 1 [
] 0 [
: '
1 ,..., 1 , 0 ] [
1
] [

k
kn

W W W
W W W
W
X
X
X
X
x
x
x
x
define s Let
n W k X

n x
K
M
M M
The N-point DFT
may be expressed
in matrix form as:
matrix identity I
I W W
X W

X W x

:
1
*
* 1
=
= =

Example of calculation of DFT in matrix form
Example of calculation of DFT in matrix form
Find DFT of the signal
x[n] =
[n-1] + 2[n-2] + 3[n-3]
(
(
(
(

+
= =
(
(
(
(

=
(
(
(
(
(

=
(
(
(
(

=
j
j
x W X Then
j j
j j
W W W
W W W
W W W
W
x
define s Let
2 2
2
2 2
6
.
1 1
1 1 1 1
1 1
1 1 1 1
1
1
1
1 1 1 1
3
2
1
0
: '
4 4 4
9
4
6
4
3
4
6
4
4
4
2
4
3
4
2
4
1
4
4
4
Lecture #20
Lecture #20
DFT and inverse DFT
DFT and inverse DFT
1. DFT and inverse DFT formulas
2. DFT and inverse DFT examples
3. Frequency resolution of the DFT
Discrete frequency spectrum computed from DFT has the
spacing between frequency samples of:
Frequency resolution of the DFT
Frequency resolution of the DFT
N
f
f
s
=
N
2
=
The choice of N determines the resolution of the frequency
spectrum, or vice-versa
To obtain the adequate resolution:
1. Increasing of the duration of data input to the DFT
2. Zero padding, which adds no new information, but effects a better
interpolator
0 0.5 1 1.5 2 2.5 3 3.5 4
0
1
2
3
4
5
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
0 5 10 15 20 25 30
0
1
2
3
4
5
Examples of N = 5 and N = 15
Examples of N = 5 and N = 15
0 0. 5 1 1.5 2 2.5 3 3.5 4
0
2
4
6
0 5 10 15 20 25 30
0
2
4
6
0 10 20 30 40 50 60
0
2
4
6
Examples of N = 15 and N = 30
Examples of N = 15 and N = 30
Lecture #21
Lecture #21
DFT properties
DFT properties
1. Periodicity and Linearity
2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parsevals theorem
DFT properties
DFT properties
x(n)
Finite length
x
p
(n)
Periodic
N periodic extension
truncate
N periodic extension
truncate
X(k)
Finite length
X
p
(k)
Periodic
D
F
T
s
a
m
p
l
i
n
g
r
e
c
o
n
s
t
r
u
c
t
i
o
n
D
F
T
-
1
X
p
()
Periodic
DTFT
DTFT
-1
DFT properties
DFT properties
x(n)
Finite length
x
p
(n)
Periodic
N periodic extension
truncate
N periodic extension
truncate
X(k)
Finite length
X
p
(k)
Periodic
D
F
T
s
a
m
p
l
i
n
g
r
e
c
o
n
s
t
r
u
c
t
i
o
n
D
F
T
-
1
X
p
()
Periodic
DTFT
DTFT
-1
Periodicity
Periodicity
x[n+N] = x[n] for all n
X[k+N] = X[k] for all k
If x[n] and X[k] are an N-point DFT pair, then
Linearity
Linearity
Note: The length of x
1
[n] is same with the length of x
2
[n]
] [ ] [ ] [ ] [
2 2 1 1 2 2 1 1
k X a k X a n x a n x a
DFT
+ +
Proof:
Infer from the definition formula of DFT
Lecture #21
Lecture #21
DFT properties
DFT properties
1. Periodicity and Linearity
2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parsevals theorem
Circular time shift property
Circular time shift property
] k [ X W ] m n [ x
km
DFT

Proof:
Infer from the relation between DFT and DTFT
] [ ] [ ) (
:
2
) ( ] [
2
k X W k X e X e

k
X e m n x
km
m

jk
m j
m j
DTFT
=

Circular
Circular
time
time
shift
shift
Circular shift by m is the same as a shift by m modulo N
x(n)
x
p
(n)
x
p
(n+2)
x(n+2)
Lecture #21
Lecture #21
DFT properties
DFT properties
1. Periodicity and Linearity
2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parsevals theorem
Circular frequency shift property
Circular frequency shift property
] [ ] [
ln
l k X W n x
DFT

Proof:
Similar to the circular time shift property
Lecture #21
Lecture #21
DFT properties
DFT properties
1. Periodicity and Linearity
2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parsevals theorem
Circular convolution property
Circular convolution property
The non-zero length of x
1
(n) and x
2
(n) can be no longer
than N
The shift operation is circular shift
The flip operation is circular flip

=
=
1
0
2 1 2 1 2 1
] [ ] [ ] [ ] [ ] [ ]. [

p
DFT
p n x p x n x n x k X k X
The circular convolution is not the linear convolution in chapter 2
Direct method to calculate circular
Direct method to calculate circular
convolution
convolution
1. Draw a circle with N values of x(n) with N equally spaced angles
in a counterclockwise direction.
2. Draw a smaller radius circle with N values of h(n) with equally
spaced angles in a clockwise direction. Superimpose the centers of 2
circles, and have h(0) in front of x(0).
3. Calculate y(0) by multiplying the corresponding values on each
radial line, and then adding the products.
4. Find succeeding values of y(n) in the same way after rotating the
inner disk counterclockwise through the angle 2k/N
Example to calculate circular convolution
Example to calculate circular convolution
Evaluate the circular convolution, y(n) of 2 signals:
x
1
(n) = [ 1 2 3 4 ]; x
2
(n) = [ 0 1 2 3 ]
1
2
3
4
0
1
2
3
y(0) = 16
1
2
3
4
1
2
3
0
y(1) = 18
Example (cont)
Example (cont)
Evaluate the circular convolution, y(n) of 2 signals:
x
1
(n) = [ 1 2 3 4 ]; x
2
(n) = [ 0 1 2 3 ]
1
2
3
4
2
3
0
1
y(2) = 16
1
2
3
4
3
0
1
2
y(3) = 10
Another method to calculate circular convolution
Another method to calculate circular convolution
x
1
(n)
x
2
(n)
X
1
(k)
X
2
(k)
DFT
DFT
IDFT
y(n)
Ex. x
1
(n) = [ 1 2 3 4 ]; x
2
(n) = [ 0 1 2 3 ]
X
1
(k) = [ 10, -2+j2, -2, -2-j2 ];
X
2
(k) = [ 6, -2+j2, -2, -2-j2 ];
Y(k) = X
1
(k).X
2
(k) = [ 60, -j8, 4, j8 ]
y(n) = [ 16, 18, 16, 10 ]
Lecture #21
Lecture #21
DFT properties
DFT properties
1. Periodicity and Linearity
2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parsevals theorem
Multiplication
Multiplication
The non-zero length of X
1
(k) and X
2
(k) can be no longer
than N
The shift operation is circular shift
The flip operation is circular flip

=
=
1
0
2 1 2 1 2 1
] [ ] [
1
] [ ] [
1
] [ ]. [

l
DFT
l k X l X

k X k X

n x n x
Lecture #21
Lecture #21
DFT properties
DFT properties
1. Periodicity and Linearity
2. Circular time shift
3. Circular frequency shift
4. Circular convolution
5. Multiplication
6. Parsevals theorem
Parseval
Parseval

s
s
theorem
theorem
The general form:
Special case:


=

=
=
1
0
1
0
] [ * ] [
1
] [ * ] [

k

n
k Y k X

n y n x


=

=
=
1
0
2
1
0
2
| ] [ |
1
| ] [ |

k

n
k X

n x
Parseval
Parseval

s
s
theorem example
theorem example
Given x(n) = (n) + 2(n-1) +3(n-2) + (n-3) and N = 4.

=
= = + + + + + =
= + + + =
1
0
2 2 2 2 2 2 2
2 2 2 2
1
0
2
15
4
60
) 1 2 1 1 2 7 (
4
1
| ] [ |
1
15 1 3 2 1 | ] [ |

n
k X

n x
Multiple choice questions
Multiple choice questions
Ex1:
It is desired to build a sampling system which takes a
recorded orchestra music signal s(t) and converts it to a
discretely-sampled form. In order to experimentally determine
the bandwidth (in frequency) of this signal the best transform
would be
a. The Fourier transform of a continuous function or a discrete
sequence
b. The Z-transform
c. The Fourier series
d. The discrete Fourier transform
Multiple choice questions
Multiple choice questions
Ex2:
A mathematical model of human speech puts out a perfectly
periodic signal for steady vowel sounds. In order to accurately
determine the harmonics of the fundamental frequency for
this mathematical model, the best transform should be
a. The Fourier transform of a continuous function or a discrete
sequence
b. The Z-transform
c. The Fourier series
d. The discrete Fourier transform
Multiple choice questions
Multiple choice questions
Ex3:
A student wishes to convolve the continuous-time mathematical
functions g(t) and h(t). She/he uniformly samples these
functions, and uses a computer to get, at best, an approximate
result. Another student claims to be able to get an exact result
via a transform. She/he must be thinking of which transform
a. The Fourier transform of a continuous function or a discrete
sequence
b. The Z-transform
c. The Fourier series
d. The discrete Fourier transform
Multiple choice questions
Multiple choice questions
Ex4:
A student wishes to convolve the discrete-time mathematical
functions g(n) and h(n). She/he claims to be able to get an
exact result via one of the transforms below. She/he must be
thinking of which transforms
a. The Fourier transform of a continuous function or a discrete
sequence
b. The Z-transform
c. The Fourier series
d. The discrete Fourier transform
Lecture #22
Lecture #22
Fast Fourier Transform (FFT)
Fast Fourier Transform (FFT)
1. What is FFT?
2. The decomposition-in-time Fast Fourier
Transform algorithm (DIT-FFT)
3. The decomposition-in-frequency Fast
Fourier Transform algorithm (DIF-FFT)
Using some "tricks" and choosing the appropriate N value, the DFT
can be implemented in a very computationally efficient way this is
the Fast Fourier Transform (FFT) - which is the basis of lots of
contemporary DSP hardware
N
2
j
N
e W

=
1 N n 0 W ] k [ X
N
1
] n [ x
1 N k 0 W ] n [ x ] k [ X
1 N
0 n
nk
N
1 N
0 n
nk
N
=
=

=
Recall DFT and IDFT definition
Recall DFT and IDFT definition
N
th
complex
root of unity:
What does it take to compute DFT or IDFT?
N
2
complex multiplications for all N points of X(k) or x[n]
FFT: the algorithm to optimize the computational process by
breaking the N-point DFT into smaller DFTs
Ex.: N is a power of 2: split N-point DFT into two N/2-point
DFTs, then split each of these into two of length N/4, etc., until
we have N/2 subsequences of length 2
Cooley and Tukey (1965):
Fast Fourier Transform (FFT)
Fast Fourier Transform (FFT)
tions multiplica complex
2
log
2
2

0 10 20 30 40 50 60 70 80 90 100
-2000
0
2000
4000
6000
8000
10000
N C
o
m
p
l
e
x

m
u
l
t
i
p
l
i
c
a
t
i
o
n

n
u
m
b
e
r
s
D
F
T
FFT
Comparison of DFT and FFT efficiency
Comparison of DFT and FFT efficiency
Comparison of DFT and FFT efficiency
Comparison of DFT and FFT efficiency
Number of Complex multiplications Complex multiplications Speed improvement
points N in direct DFT in FFT factor
4
8
16
32
64
128
256
512
1024
16
64
256
1,024
4,096
16,384
65,536
262,144
1,048,576
4
12
32
80
192
448
1,024
2,304
5,120
4.0
5.3
8.0
12.8
21.3
36.6
64.0
113.8
204.8
Some properties of can be exploited in performing
FFT:
Other useful properties:
{ }
W
nk

( )
k and n in y periodicit ,
symmetry conjugate complex ,
) ( ) (
*
) (
W W W
W
W W
n k

n k

kn

kn

n k

kn

+ +

= =
= =
W W
W
W
e W W W W
kn

kn

kn

kn

jn kn

kn

2
2
2
)
2
(
odd n if ,
even n if ,
=

= = =

+
FFT (cont)
FFT (cont)
Lecture #22
Lecture #22
Fast Fourier Transform (FFT)
Fast Fourier Transform (FFT)
1. What is FFT?
2. The decomposition-in-time Fast
Fourier Transform algorithm (DIT-FFT)
3. The decomposition-in-frequency Fast
Fourier Transform algorithm (DIF-FFT)
G(k) is N/2 points DFT of the even numbered data: x(0),
x(2), x(4), ., x(N-2).
H(k) is the N/2 points DFT of the odd numbered data:
x(1), x(3), , x(N-1).
even odd
[ ] [ ] [ ]
kn kn
n n
X k x n W x n W = +

DIT
DIT
-
-
FFT with N as a 2
FFT with N as a 2
-
-
radix number
radix number
1 N ,..., 1 , 0 k ), k ( H ) k ( G ) k ( X
W
k
N
= + =
We divide X(k) into 2 parts:
2 2
1 1
2 (2 1)
0 0
[ ] [2 ] [2 1]

mk k m
m m
X k x m W x m W

+
= =
= + + =

2 2
1 1
2 2
0 0
[2 ]( ) [2 1]( )

mk k mk
m m
x m W W x m W

= =
+ + =

=
( )
2 / N
) 2 / N /( 2 j
2
N / 2 j 2
N
W e e W = = =

G(k) and H(k) are of length N/2; X(k) is of length N
G(k)=G(k+N/2) and H(k)=H(k+N/2)
) ( ) ( ] [ ] [ ) (
1
0
2 /
1
0
2 /
2 2
k H k G W m h W W m g k X
W
k

m
mk

m
mk

+ = + =


=

=
DIT
DIT
-
-
FFT (cont)
FFT (cont)
Note:
4
k
8 4 8
] k [ H W ] k [ G ] k [ X + =
] 3 [ H W ] 3 [ G ] 7 [ X ] 3 [ H W ] 3 [ G ] 3 [ X
] 2 [ H W ] 2 [ G ] 6 [ X ] 2 [ H W ] 2 [ G ] 2 [ X
] 1 [ H W ] 1 [ G ] 5 [ X ] 1 [ H W ] 1 [ G ] 1 [ X
] 0 [ H W ] 0 [ G ] 4 [ X ] 0 [ H W ] 0 [ G ] 0 [ X
7
8
3
8
6
8
2
8
5
8
1
8
4
8
0
8
+ = + =
+ = + =
+ = + =
+ = + =
DIT
DIT
-
-
FFT of length N = 8
FFT of length N = 8
DFT
N = 4
DFT
N = 4
# complex multiplications are reduced: 8
2
= 64 2x(4)
2
+ 8 = 40
Signal
Signal
flow
flow
graph
graph
for
for
8
8
-
-
point
point
FFT
FFT
2 4 2 4
] [ ] [ ] [ k H W k G k X
k
+ =
DIT
DIT
-
-
FFT of length N = 4
FFT of length N = 4
] 1 [ ] 1 [ ] 3 [
] 0 [ ] 0 [ ] 2 [
] 1 [ ] 1 [ ] 1 [
] 0 [ ] 0 [ ] 0 [
3
4
2
4
1
4
0
4
H W G X
H W G X
H W G X
H W G X
+ =
+ =
+ =
+ =
] 1 [ ] 1 [ ] 3 [
3
4
H W G X + =
] 1 [ ] 1 [ ] 1 [
1
4
H W G X + =
] 0 [ ] 0 [ ] 2 [
2
4
H W G X + =
] 0 [ ] 0 [ ] 0 [
0
4
H W G X + =
DFT
N = 2
DFT
N = 2
W
0
x[0]
x[2]
x[1]
x[3]
W
1
W
2
W
3
# multiplications are reduced: 4
2
= 16 2x(2)
2
+ 4 = 12
DIT
DIT
-
-
FFT of length N = 2
FFT of length N = 2
# multiplications are
reduced: 2
2
= 4 0;
just 2 additions!!!
x[1] - 1
x[0]
X[0]
X[1]
] 1 [ ] 0 [ ] 1 [ ] 0 [ ] 1 [
] 1 [ ] 0 [ ] 1 [ ] 0 [ ] 0 [
1 , 1 0 , ] [ ] [
1 . 1 1 . 0
0 . 1 0 . 0
2
2
1
0
x x W x W x X
x x W x W x X
e W k W n x k X
j
n
nk
= + =
+ = + =
= = =

=

Butterfly diagram
DFT
N = 4
DFT
N = 4
First step: split 8-point DFT into two 4-point DFTs
Example
Example
of
of
8
8
-
-
point
point
FFT
FFT
0
W
0
W
W
4
W
2
W
0
W
0
W
6
W
6
W
2
W
4
DFT N = 2
DFT N = 2
DFT N = 2
DFT N = 2
G[0]
G[1]
G[2]
G[3]
H[0]
H[1]
H[2]
H[3]
Example
Example
of
of
8
8
-
-
point
point
FFT
FFT
(cont)
(cont)
Second step: split each of 4-point DFT into two 2-point DFTs
Example
Example
of
of
8
8
-
-
point
point
FFT
FFT
(cont)
(cont)
0
W
0
W
W
4
W
2
W
0
W
0
W
6
W
6
W
2
W
4
Third step: combine all signal flow graphs of step 1 and step 2
W
0
W
1
W
2
W
3
W
4
W
5
W
6
W
7
There are 3 = log
2
8 stages; 4 butterfly diagrams in each stage
W
r+N/2
= -W
r
W
r
- 1
Butterfly diagram
Butterfly diagram
Now the overall computation is reduced to:
tions multiplica complex
2
log
2
2

The
The
overall
overall
signal
signal
flow
flow
graph
graph
for
for
8
8
-
-
point
point
DIT
DIT
-
-
FFT
FFT
W
r
- 1
In
In
-
-
place computation
place computation
a
b
A
B
Each butterfly takes (a,b) to produce (A,B) no need to save
(a,b) can store (A,B) in the same locations as (a,b)
We need 2N store registers to store the results at each stage and
these registers are also used throughout the computation of the
N-point DFT
The order of the input: bit-reversed order
The order of the output: natural order
Lecture #22
Lecture #22
Fast Fourier Transform (FFT)
Fast Fourier Transform (FFT)
1. What is FFT?
2. The decomposition-in-time Fast Fourier
Transform algorithm (DIT-FFT)
3. The decomposition-in-frequency Fast
Fourier Transform algorithm (DIF-FFT)
Rewrite the second half:
DIF
DIF
-
-
FFT with N as a 2
FFT with N as a 2
-
-
radix number
radix number
( )


=

=
+

=
|

\
|
+ =
|

\
|
+ =
1 ) 2 / (
0
1 ) 2 / (
0
1
) 2 / (
2 2
) (
2 2

n
kn

n
n k

n
kn

n x W W

n x W n x

1 ,..., 1 , 0 , ) ( ) ( ) (
1 ) 2 / (
0
1
) 2 / (
= + =

=
k W n x W n x k X

n

n
kn

kn

k j k j
k

e e W

) 1 (
) 2 / )( / 2 (
2
= = =

We divide X(k) in half first half and second half
Since:
then
| | 1 ,..., 1 , 0 , ) 2 / ( ) 1 ( ) ( ) (
1 ) 2 / (
0
= + + =

=
k W n x n x k X

n
kn

k
DIF
DIF
-
-
FFT (cont)
FFT (cont)
| |
| | { } 1
2
,..., 1 , 0 , ) 2 / ( ) ( ) 1 2 (
1
2
,..., 1 , 0 , ) 2 / ( ) ( ) 2 (
1 ) 2 / (
0
2 /
1 ) 2 / (
0
2 /
= + = +
= + + =

k W W n x n x k X

k W n x n x k X

n
kn

n
kn

2
2 /
2

W W =
Decompose X(k) into two frequency sequences, even and odd:
Since:
then,
| |
| | 1
2
,..., 1 , 0 , ) 2 / ( ) ( ) 1 2 (
1
2
,..., 1 , 0 , ) 2 / ( ) ( ) 2 (
1 ) 2 / (
0
) 1 2 (
1 ) 2 / (
0
2
= + = +
= + + =

=
+

k W n x n x k X

k W n x n x k X

n
n k

n
kn

DIF
DIF
-
-
FFT butterfly
FFT butterfly
x[n]
x[n+N/2]
x[n] + x[n+N/2]
(x[n] - x[n+N/2])W
N
n
-1
W
N
n
DIF
DIF
-
-
FFT of length N = 4
FFT of length N = 4
-1
-1
-1
-1
W
4
1
W
4
0
x[0] + x[2]
x[1] + x[3]
(x[0] - x[2])W
4
0
(x[1] - x[3])W
4
1
x[0]
x[1]
x[2]
x[3]
X[0]
X[2]
X[1]
X[3]
Lecture #23
Lecture #23
DFT applications
DFT applications
1. Approximation of the Fourier Transform
of analog signals
2. Linear convolution
Approximation of Fourier Transform
Approximation of Fourier Transform
Using DFT as a discrete-frequency approximation of the DTFT
and also an approximation of the CTFT
Step1. Determine the resolution = 2/N required for the DFT to
be useful for its intended purpose determine N (N often = 2
n
)
Step 2. Determine the sampling frequency required to sample the
analog signal so as to avoid aliasing
s
2
M
Step 3. Accumulate N samples of the analog signal over N.T
seconds (T = 2 / // /
s
)
Step 4. Calculate DFT directly or using FFT algorithm
0 0.5 1 1. 5 2 2.5 3
0
0.5
1
n
f
[
n
]
0 1 2 3 4 5
0
1
2
3
omega
m
a
g
n
i
t
u
d
e
Example
Example
f(t) = rect[(t-1)/2]
F() = 2sinc()e
-j
T
s
= 1s
%Error of sample 1 = 50%
Example
Example
0 5 10 15
0
0.5
1
n
f
[
n
]
0 5 10 15 20 25 30
0
1
2
3
omega
m
a
g
n
i
t
u
d
e
f(t) = rect[(t-1)/2]
F() = 2sinc()e
-j
T
s
= 0.2s
%Error of sample 1 = 10%
0 5 10 15 20 25 30 35
0
0.5
1
n
f
[
n
]
0 10 20 30 40 50 60 70
0
1
2
3
omega
m
a
g
n
i
t
u
d
e
Example
Example
f(t) = rect[(t-1)/2]
F() = 2sinc()e
-j
T
s
= 0.1s
%Error of sample 1 = 5%
Windowing
Windowing
Source of error: truncation or windowing of the periodic
extension of the DT sequence implied in the DFT development
Windowing = multiplying the periodic extension of x[n] by a
rectangular function with duration N.T DFT involves a convolution
DFT = sampled(DTFT*sinc)
This multiplication causes spectrum-leakage distortion
To reduce the affect of spectrum-leakage distortion:
- Increase the sampling frequency
- Increase the number of samples
- Choose an appropriate windowing function (Hamming, Hanning)
Lecture #23
Lecture #23
DFT applications
DFT applications
1. Approximation of the Fourier Transform of
analog signals
2. Linear convolution
Recall linear convolution
Recall linear convolution
N
1
: the non-zero length of x
1
(n); N
2
: the non-zero
length of x
2
(n); N
y
= N
1
+ N
2
-1
The shift operation is the regular shift
The flip operation is the regular flip

=
= =
p
p n x p x n x n x n y ] [ ] [ ] [ * ] [ ] [
2 1 2 1
Recall circular convolution
Recall circular convolution
The non-zero length of x
1
(n) and x
2
(n) can be no longer
than N
The shift operation is circular shift
The flip operation is circular flip

=
= =
1
0
2 1 2 1
] [ ] [ ] [ ] [ ] [

p
p n x p x n x n x n y
Calculation of the linear convolution
Calculation of the linear convolution
The circular convolution of 2 sequences of length N
1
and N
2
can be made equal to the linear convolution of 2 sequences
by zero padding both sequences so that they both consists
of N
1
+N
2
-1 samples.
x
1
(n)
N
1
samples
x
2
(n)
N
2
samples
x
1
(n)
x
2
(n)
Zero padding
(N
2
-1) zeros
IDFT
x
1
(n)*x
2
(n)
Zero padding
(N
1
-1) zeros
DFT
DFT
Example of calculation of the linear convolution
Example of calculation of the linear convolution
x
1
(n) = [ 1 2 3 4 ]; x
2
(n) = [ 0 1 2 3 ]
x
1
(n) = [ 1 2 3 4 0 0 0 ]; x
2
(n) = [ 0 1 2 3 0 0 0 ]
X
1
(k) = [ 10, -2.0245-j6.2240, 0.3460+j2.4791, 0.1784-
j2.4220, 0.1784+j2.4220, 0.3460-j2.4791, -2.0245-j6.2240 ];
X
2
(k) = [ 6, -2.5245-j4.0333, -0.1540+j2.2383, -0.3216-
j1.7950, -0.3216+j1.7950, -0.1540-j2.2383, -2.5245+j4.0333];
Y(k) = [ 60, -19.9928+j23.8775, -5.6024+j0.3927, -5.8342-
j0.8644, -4.4049+j0.4585, -5.6024-j0.3927, -19.9928
+j23.8775 ]
IDFT{Y(k)} = y(n) = [ 0 1 4 10 16 17 12 ]
Lecture #24
Lecture #24
Using DFT/FFT in filtering
Using DFT/FFT in filtering
The response, y(n) of a filter with the impulse response, h(n)
to an input, x(n) can be calculated by using the DFT
Limitations: All sample values of the signal must be
accumulated before the process begins
Great memory
Long time delay
Not suitable for long duration input
Solution: block filtering
Divide long input signal, x(n) into non-overlapped blocks,
x
b
(n) of appropriate length for FFT calculation.
Convolve each block x
b
(n) and h(n) to get the output,
y
b
(n)
Overlap-add outputs, y
b
(n) together to form the output
signal, y(n)
Overlap
Overlap
-
-
add technique in block filtering
add technique in block filtering
Example of overlap
Example of overlap
-
-
add technique
add technique
h(n)
x(n)
Example of overlap
Example of overlap
-
-
add technique
add technique
x
0
(n)
x
1
(n)
x
2
(n)
Example (cont)
Example (cont)
y
0
(n)
y
1
(n)
y
2
(n)
Prob.1 Prob. 5
12.10 12.18
Prob. 2 Prob. 6
12.11 12.22
Prob. 3 Prob. 7
12.12 12.24
Prob. 4 Prob. 8
12.15 12.30
HW
HW
Prob.9
Given signals below and their DFT-5
HW
HW
] n [ ] n [ s ) c (
] 1 n [ ] n [ x ) b (
] 4 n [ 4 ] 3 n [ 3 ] 2 n [ 2 ] 1 n [ ] n [ x ) a (
2
1
=
=
+ + + =
1. Find y[n] so that Y[k] = X
1
[k].X
2
[k]
2. Does x
3
[n] exist, if S[k] = X
1
[k].X
3
[k]?
Prob.10
Prove the Parsevals theorem
HW
HW


=

=
=
1
0
1
0
] [ * ] [
1
] [ * ] [

k

n
k Y k X

n y n x