Part A | 9.3
214 Part A Fundamentals
x (0)
X (0)
x (4)
X (1)
2-point
DFT
2-point
DFT
2-point
DFT
2-point
DFT
Combine
4-point
DFTs
Combine
2-point
DFTs
Combine
2-point
DFTs
x (2)
X (2)
x (6)
X (3)
x (1)
X (4)
x (5)
X (5)
x (3)
X (6)
x (7)
X (7)
Fig. 9.23 Computation of eight-point
FFT in three stages using DIT
x (0)
X (0)
x (4)
X (1)
W 8
0
Stage 1
Bit reversed
inputs
Complex
multiplications
log 2 N
–1
x (2)
X (2)
x (6)
X (3)
W 8
0
W 8
2
W 8
0
–1
–1
–1
x (1)
X (4)
x (5)
X (5)
W 8
0
W 8
1
–1
–1
W 8
0
–1
x (3)
X (6)
x (7)
X (7)
W 8
0
W 8
2
W 8
0
W 8
3
W 8
2
–1
–1
–1
–1
–1
Stage 3
Stage 2
N
2
Fig. 9.24 Eight-point DITFFT algorithm
x (0)
X (0)
x (1)
X (4)
Two-point
DFT
Two-point
DFT
Two-point
DFT
Two-point
DFT
Reduce
to four-point
DFTs
Reduce
to two-point
DFTs
Reduce
to two-point
DFTs
x (2)
X (2)
x (3)
X (6)
x (4)
X (1)
x (5)
X (5)
x (3)
X (3)
x (7)
X (7)
Fig. 9.25 Computation of eight-point
FFT in three stages using DIF