Digital Signal Processing Reference
In-Depth Information
x[0]
x[4]
x[2]
x[6]
x[1]
x[5]
x[3]
x[7]
X
E
[0]
X
O
[0]
X
E
[0]
X
O
[0]
X
E
[0]
X
O
[0]
X
E
[0]
X
O
[0]
0
W
0
2
W
0
2
W
0
2
W
0
2
k = 0
W
0
2
= 1
−
−
−
−
+
+
+
+
X
E
[0]
X
E
[1]
X
O
[0]
X
O
[1]
X
E
[0]
X
E
[1]
X
O
[0]
X
O
[1]
1
W
0
4
W
1
4
W
0
4
W
1
4
k = 0, 1
W
0
4
= 1
W
1
4
= −j
−
−
−
−
+
+
+
+
X
E
[0]
X
E
[1]
X
E
[2]
X
E
[3]
X
O
[0]
X
O
[1]
X
O
[2]
X
O
[3]
2
k = 0, 1, 2 , 3
W
0
W
0
8
W
1
8
W
2
8
W
3
8
8
= 1
W
1
8
= 0.707(1−j)
W
2
8
= −j
W
3
−
−
−
−
+
+
+
+
8
= −0.707(1+j)
X[0]
X[1]
X[2]
X[3]
X[4]
X[5]
X[6]
X[7]
3
Figure 3.20:
The Butterfly Diagram for a length-8 Decimation-in-Time FFT algorithm.
Example 3.22.
Compute the DFT of the sequence
[
1234
]
using the radix-2 DIT algorithm discussed
above.
The first step is to decimate in time, which results in the net sequence [1,3,2,4]. Then we obtain
the 2-pt DFTs of the sequences [1,3] and [2,4] which are, respectively, [4,-2] and [6,-2] by using the
2-pt butterflies (3.21). Using the 4-pt butterflies at (3.22), we combine the two 2-pt DFTs into one 4-pt
DFT:
X
[
0
]=
4
+
6
=
10
X
[
0
+
2
]=
4
−
6
=−
2
and
X
[
1
]=−
2
+
(
−
j)(
−
2
)
=−
2
+
j
[
+
]=−
−
−
−
=−
−
X
1
2
2
(
j)(
2
)
2
j
yielding a net DFT of
[
10
,(
−
2
+
j),
−
2
,(
−
2
−
j)
]
The MathScript call
