Digital Signal Processing Reference
In-Depth Information
FIGURE 6.2.
Decomposition of an
N
-point DFT into two (
N
/2)-point DFTs for
N
=
8.
FIGURE 6.3.
Decomposition of two (
N
/2)-point DFTs into four (
N
/4)-point DFTs for
N
=
8.
(
)
-
Â
N
21
(
)
=
()
Xk
21
+
bnWW
N
n
nk
(6.18)
N
2
n
=
0
Figure 6.2 shows the decomposition of an
N
-point DFT into two (
N
/2)-point DFTs
for
N
8. As a result of the decomposition process, the
X
's in Figure 6.2 are even
in the upper half and odd in the lower half. The decomposition process can now be
repeated such that each of the (
N
/2)-point DFTs is further decomposed into two
(
N
/4)-point DFTs, as shown in Figure 6.3, again using
N
=
8 to illustrate.
The upper section of the output sequence in Figure 6.2 yields the sequence
X
(0)
and
X
(4) in Figure 6.3, ordered as even.
X
(2) and
X
(6) from Figure 6.3 represent
=
Search WWH ::
Custom Search