The document discusses the Fast Fourier Transform algorithm. It explains that FFT computes the discrete Fourier transform using only NlogN complex multiplications and additions, compared to N^2 for the direct method. It then describes the decimation-in-time FFT algorithm and provides examples of computing 2-point and 8-point DFTs using the algorithm.
The document discusses the Fast Fourier Transform algorithm. It explains that FFT computes the discrete Fourier transform using only NlogN complex multiplications and additions, compared to N^2 for the direct method. It then describes the decimation-in-time FFT algorithm and provides examples of computing 2-point and 8-point DFTs using the algorithm.
The document discusses the Fast Fourier Transform algorithm. It explains that FFT computes the discrete Fourier transform using only NlogN complex multiplications and additions, compared to N^2 for the direct method. It then describes the decimation-in-time FFT algorithm and provides examples of computing 2-point and 8-point DFTs using the algorithm.
The document discusses the Fast Fourier Transform algorithm. It explains that FFT computes the discrete Fourier transform using only NlogN complex multiplications and additions, compared to N^2 for the direct method. It then describes the decimation-in-time FFT algorithm and provides examples of computing 2-point and 8-point DFTs using the algorithm.
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
