Digital Signal Processing Reference
In-Depth Information
Fig. 12.11. Flow graphs of
(
K
/2)-point DFTs using
(
K
/4)-point DFTs. (a)
G
[
r
];
(b)
H
[
r
].
G
′[0]
H
′ [0]
H
′ [1]
H
′′ [0]
H
′′ [1]
x
[0]
x
[4]
x
[2]
x
[6]
G
[0]
G
[1]
G
[2]
G
[3]
x
[5]
[1]
H
[0]
H
[1]
H
[2]
H
[3]
K
/4 point
DFT
K
/4 point
DFT
0
W
W
0
K
/2
G
′[1]
/
2
x
[3]
W
1
W
1
K
/2
G
′′[0]
G
′′[1]
/
2
x
x
[7]
K
/4 point
DFT
K
/4 point
DFT
2
2
K
/2
W
W
/
2
3
3
K
/2
W
W
/
2
(a)
(b)
G
′[0]
x
0
]
Equation (12.35) expresses the (
K
/
2)-point DFT
G
[
r
] in terms of two (
K
/4)-
point DFTs of the even- and odd-numbered samples of
g
[
k
]. Figure 12.11(a)
illustrates the flow graph for obtaining
G
[
r
] using Eq. (12.35). Similarly, Eq.
(12.36) expresses the (
K
/
2)-point DFT
H
[
r
] in terms of two (
K
/
4)-point DFTs
of the even- and odd-numbered samples of
h
[
k
], which can be implemented
using the flow graph shown in Fig. 12.11(b). If
K
is a power of 2, then the
above process can be continued until we are left with a 2-point DFT. For the
aforementioned example with
K
=
8, the (
K
/
4)-point DFTs in Fig. 12.11 can
be implemented directly using 2-point DFTs. Using the definition of the DFT,
the top left 2-point DFTs
G
′
[0] and
G
′
[1], for example, in Fig. 12.11(a) are
expressed as follows:
W
2
= 1
G
′[1]
x
4
]
W
1
= −1
2
(a)
G
G
′′[0]
x
2
W
2
= 1
G
′′[1]
x
6
W
1
= −1
2
(b)
H
′[0]
x
G
′
[0]
=
x
[0] e
−
j2
πℓ
r
/
2
ℓ=
0
,
r
=
0
+
x
[4] e
−
j2
πℓ
r
/
2
=
x
[0]
+
x
[4]
(12.37)
W
2
= 1
ℓ=
1
,
r
=
0
H
′[1]
x
5
and
W
1
= −1
2
G
′
[1]
=
x
[0] e
−
j2
πℓ
r
/
2
ℓ=
0
,
r
=
1
+
x
[4] e
−
j2
πℓ
r
/
2
=
x
[0]
−
x
[4]
.
(12.38)
(c)
ℓ=
1
,
r
=
1
H
′′[0]
x
3
W
2
= 1
The flow graphs for Eqs. (12.37) and (12.38) are shown in Fig. 12.12(a). By
following this procedure, the flow diagrams for the remaining 2-point DFTs
required in Fig. 12.11 are derived and are shown in Figs. 12.12(b)-(d). Because
of their shape, the elementary flow graphs shown in Fig. 12.12 are generally
referred to as the
butterfly
structures.
Combining the individual flow graphs shown in Figs. 12.10, 12.11, and 12.12,
it is straightforward to derive the overall flow graph for the 8-point DFT, which
is shown in Fig. 12.13; in this flow diagram, we have further reduced the number
of operations for an 8-point DFT by noting that
H
′′[1]
x
7
]
W
1
= −1
2
(d)
Fig. 12.12. Flow graphs of
2-point DFTs required for
Fig. 12.11. (a) Top 2-point DFT
G
′
[0] and
G
′
[1] for Fig. 12.11(a).
(b) Bottom 2-point DFT
G
′′
[0]
and
G
′′
[1] for Fig 12.11(a).
(c) Top 2-point DFT
H
′
[0] and
H
′
[1] for Fig 12.11(b).
(d) Bottom 2-point DFT
H
′′
[0]
and
H
′′
[1] for Fig. 12.11(b).
W
K
/
2
=
e
−
j2
π
r
/
(
K
/
2)
=
e
−
j4
π
r
/
K
=
W
2
K
,
and by placing the common terms between the twiddle multipliers of the two
branches, which are originating from the same node, before the source node.
12.6.1 Computational complexity
To derive the computational complexity of the decimation-in-time algorithm,
we generalize the results obtained in Fig. 12.13, where
K
is set to 8. We
observe that Fig. 12.13 consists of log
2
K
=
3 stages and that each stage
Search WWH ::
Custom Search