Digital Signal Processing Reference
In-Depth Information
(6.31) becomes
(
)
-
Â
N
41
[
]
k
k
k
()
=
()
+
()
(
)
+
()
(
)
+
()
(
)
nk
Xk
xn
j xn N
+
4
1
xn N
+
2
j xn
+
3
N
4
W
(6.32)
n
=
0
Let
W
N
=
W
N
/4
. Equation (6.32) can be written as
(
)
-
Â
N
41
()
=
[
()
++
(
)
++
(
)
++
(
)
]
W
N
nk
(6.33)
X
4
k
xn
xn N
4
xn N
2
xn
3
N
4
4
n
=
0
(
)
-
Â
N
41
(
)
=
[
()
-+
(
)
-+
(
)
++
(
)
]
X
41
k
+
x n
jx n
N
4
x n
N
2
jx n
34
N
W W
N
n
nk
(6.34)
N
4
n
=
0
(
)
-
Â
N
41
[
]
(
)
=
()
-+
(
)
++
(
)
-+
(
)
X
42
k
+
xn
xn N
4
xn N
2
xn
34
2
N
W W
N
n
nk
(6.35)
N
4
n
=
0
(
)
-
Â
N
41
(
)
=
[
()
++
(
)
-+
(
)
-+
(
)
]
X
43
k
+
xn
jxn N
4
xn N
2
jxn
34
3
N
W W
N
n
nk
(6.36)
N
4
n
=
0
for
k
1. Equations (6.33) through (6.36) represent a decomposi-
tion process yielding four four-point DFTs. The flow graph for a 16-point radix-4
DIF FFT is shown in Figure 6.11. Note the four-point butterfly in the flow graph.
The
=
0,1,...,(
N
/4)
-
1 are not shown in Figure 6.11. The results shown in the flow graph are
for the following exercise.
±
j
and
-
Exercise 6.4: Sixteen-Point FFT with Radix-4
Given the input sequence
x
(
n
) as in Exercise 6.2, representing a rectangular
sequence
x
(0)
0, we will find
the output sequence for a 16-point FFT with radix-4 using the flow graph in Figure
6.11. The twiddle constants are shown in Table 6.1.
=
x
(1)
=
...
=
x
(7)
=
1, and
x
(8)
=
x
(9)
=
...
=
x
(15)
=
TABLE 6.1
Twiddle Constants for 16-Point FFT with
Radix-4
m
W
N
W
N/4
0
1
1
1
0.9238
-
j
0.3826
-
j
2
0.707
-
j
0.707
-
1
3
0.3826
-
j
0.9238
+
j
4
0
-
j
1
5
-
0.3826
-
j
0.9238
-
j
6
-
0.707
-
j
0.707
-
1
7
-
0.9238
-
j
0.3826
+
j
Search WWH ::
Custom Search