Amrita School of Engineering, Bangalore
ES 623/ PE 610
DIGITAL SIGNAL
PROCESSING
Lecture 16
Fast Fourier Transforms
Amrita School of Engineering, Bangalore
Last Session
Linear convolution using circular convolution
Computation of DFT
Tabular method
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
Amrita School of Engineering, Bangalore
Todays Session
Computation of DFT
Fast Fourier Transforms(FFT)
DIT FFT
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
Amrita School of Engineering, Bangalore
Example
Compute the DFT of 4-point sequence
x(n)=[0,1,2,3] using the tabular method
Ans: X(k)=[6, -2+2j, -2, -2-2j]
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
Amrita School of Engineering, Bangalore
Computation of DFT Cont..
DFT is given by the expression:
N 1
X (k ) = x(n)W ; k = 0,1,2,3......N 1
nk
N
n =0
Number of Complex multiplications?
Number of Complex additions?
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
Amrita School of Engineering, Bangalore
Computation of DFT
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
Amrita School of Engineering, Bangalore
Properties of phase factor
W
N
N
N /2
N
=1
= 1
2
N
W = WN / 2
11 October 2010
N1 + N 2
N
K ( N n )
N
N +K
N
K +N / 2
N
N1
N
=W W
N2
N
KN *
N
= W
= WNK
= WNK
Dr.Shikha Tripathi,ASE, Bangalore
Amrita School of Engineering, Bangalore
2 - Point DFT
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
Amrita School of Engineering, Bangalore
Fast Fourier Transform (FFT)
An Algorithm to compute DFT fast.
Reduces the number of computations
Number of efficient FFTs available
FFT Computes the DFT using only Nlog2N
complex multiplies & additions
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
Amrita School of Engineering, Bangalore
Types of FFT
Decimation In Time (D-I-T): Sequence
x(n) is decomposed into successively
smaller subsequences.
Decimation In Frequency (D-I-F):
Sequence of the DFT coefficients X(k) is
decomposed into smaller subsequences.
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
10
Amrita School of Engineering, Bangalore
If N = rp , r is called the radix of FFT
algorithm .
If N= 2p the algorithm is called radix 2 FFT
(the most widely used algorithm).
We consider the special case of N = 2p
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
11
Amrita School of Engineering, Bangalore
DIT FFT Algorithm
Since N is even, decompose N into two N/2 size
sequences such that one part contains even numbered
samples & the other contains odd numbered samples of
x(n).
i.e;
f1(n) = x(2n)
and f2(n) = x(2n +1) ;n=0,1,2,,N/2 -1
Thus f1(n) & f2(n) are obtained by decimating
x(n) by a factor of 2 hence DIT algorithm
We make use of the symmetry and periodicity
properties of the phase factor WN to decimate &
simplify the expression.
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
12
Amrita School of Engineering, Bangalore
DIT FFT Algorithm
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
13
Amrita School of Engineering, Bangalore
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
14
Amrita School of Engineering, Bangalore
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
15
Amrita School of Engineering, Bangalore
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
16
Amrita School of Engineering, Bangalore
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
17
Amrita School of Engineering, Bangalore
8-Point DIT FFT Algorithm
Further modification using properties of WN
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
18
Amrita School of Engineering, Bangalore
DIT FFT algorithm Signal Flow Graph
Next
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
19
Amrita School of Engineering, Bangalore
Next Session
Inverse FFT
Convolution using FFT
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
20
Amrita School of Engineering, Bangalore
Thank You
11 October 2010
Dr.Shikha Tripathi,ASE, Bangalore
21
