Digital Signal Processing Reference
In-Depth Information
x
e
[0]
X
e
[0]
x
[0]
X
[0]
Four-point
DFT
x
e
[1]
X
e
[1]
x
[2]
X
[1]
x
e
[2]
X
e
[2]
(See Figure
12.10 for
details)
x
[4]
X
[2]
x
e
[3]
X
e
[3]
x
[6]
X
[3]
W
0
8
1
x
o
[0]
X
o
[0]
x
[1]
X
[4]
Four-point
DFT
W
1
8
1
x
o
[1]
X
o
[1]
x
[3]
X
[5]
W
2
8
1
x
o
[2]
X
o
[2]
(See Figure
12.10 for
details)
x
[5]
X
[6]
W
3
8
1
x
o
[3]
X
o
[3]
x
[7]
X
[7]
Figure 12.11
Decomposition-in-time fast
Fourier transform.
Recomposition
of four-point DFT's
1
X
e
[
k
]
X
[
k
]
1
W
k
N
2
X
o
[
k
]
X k
Figure 12.12
Butterfly diagram for an
W
k
N
-point FFT.
TABLE 12.4
DFT and FFT Comparison (Number of
Complex Multiplications Required)
N
Standard DFT
FFT
2
4
1
4
16
4
8
64
12
16
256
32
32
1,024
80
64
4,096
192
128
16,384
448
256
65,536
1,024
512
262,144
2,304
1,024
1,048,576
5,120
N
2
log
2
N[6]
N
2
N
(a power of 2)
