Fast Fourier Transform
Satishkumar Chavan
Don Bosco Institute of Technology, Mumbai
Email: satishkumar.dbit@dbclmumbai.org
DFT
Forward DFT
N 1
X k xnW nk
N
n 0
Inverse DFT
N 1
x[n] X (k )W nk
N
k 0
2 DTSP by Satish Chavan
Decimation in Frequency (DIF)
x[n] DIF-FFT X(k)
Samples will be Divide into even
in sequence and odd samples
2-point FFT (N=2)
k=0, 1 and n= 0, 1
N 1
X k xnWNnk
n 0
X(0) = x[0]WN0 + x[1]WN0 (1) W N1 W N0
X(1) = x[0]WN0 + x[1]WN1 (2)
x[0]
X(0) = x[0] + x[1] X[0]
x[1]
X(1) = x[0] - x[1] -1
X[1]
34 DTSP by Satish Chavan
DIF FFT
35 DTSP by Satish Chavan
DIF FFT
36 DTSP by Satish Chavan
DIF FFT
37 DTSP by Satish Chavan
DIF FFT
38 DTSP by Satish Chavan
DIF FFT N=4
𝑁
- Point FFT
2
𝑁
- Point FFT
2
39 DTSP by Satish Chavan
DIF FFT N=4
40 DTSP by Satish Chavan
DIF FFT N=4
41 DTSP by Satish Chavan
DIF FFT (N=8) Stage 1
42 DTSP by Satish Chavan
DIF FFT (N=8) Stage 2
43 DTSP by Satish Chavan
DIF FFT N=8
44 DTSP by Satish Chavan
Performance of the DFT Algorithm
The DFT requires N2 (NxN) complex multiplications:
Each X(k) requires N complex multiplications.
Therefore to evaluate all the values of the DFT ( X(0) to X(N-
1) ) N2 multiplications are required.
The DFT also requires (N-1)*N complex additions:
Each X(k) requires N-1 additions.
Therefore to evaluate all the values of the DFT (N-1)*N
additions are required.
Computational Complexity
Complex Complex
Multiplication Addition
DFT 𝑁2 N (N-1)
𝑁
FFT log 2 𝑁 𝑁 log 2 𝑁
2
46 DTSP by Satish Chavan
Computational Complexity
47 DTSP by Satish Chavan
