Digital Signal Processing Reference
In-Depth Information
are each split into two 2-sample sequences, forming a total of four 2-sample sequences. These are then
subdivided again to form eight 1-sample sequences. The result, however, is identical to the ordering of
the four 2-sample sequences. Since the last three rows are identical, there is obviously no separate step
needed to generate the final two rows.
The DFT of a single sample sequence is itself, so the row TD(8 X 1) in the matrix, is also a row
of eight 1-sample DFTs, labeled FD(8 X 1).
3.14.3 REASSEMBLY VIA BUTTERFLY
From there, the sequences are recombined to form four 2-pt DFTs, then two 4-pt DFTs, then one 8-pt
DFT. This is done according to the Butterfly formulas given above.
In practical terms, when the DIT routine arrives at 2
N
−
1
subsequences of length two, the butterfly
routine can be started. For the first set of butterflies, eight 1-point DFTs are converted to four two-point
DFTs using the butterfly formulas with
N
= 2 and
k
taking on only the single value of 0. These formulas
W
2
X
O
[
[
]=
X
E
[
]+
]
X
0
0
0
W
2
X
O
[
X
[
0
+
1
]=
X
E
[
0
]−
0
]
which simplify to
X
[
0
]=
X
E
[
0
]+
X
O
[
0
]
X
[
0
+
1
]=
X
E
[
0
]−
X
O
[
0
]
(3.21)
are applied in turn to the four pairs of single-point DFTs to produce the four 2-point DFTs.
At this stage we now have four 2-pt DFTs which must be assembled into two 4-pt DFTs. Using
the butterfly formulas, and letting
k
runfrom0to1,wehave
W
4
X
O
[
X
[
0
]=
X
E
[
0
]+
0
]
W
4
X
O
[
X
[
0
+
2
]=
X
E
[
0
]−
0
]
W
4
X
O
[
X
[
1
]=
X
E
[
1
]+
1
]
W
4
X
O
[
(3.22)
which thus produce a new four point DFT for every four bins formed by the two bins of each of
X
E
X
[
1
+
2
]=
X
E
[
1
]−
1
]
and
X
O
.
The final step is to assemble two 4-pt DFTs into one 8-pt DFT using the butterfly formulas. A
summary of the entire process in schematic form, known as a
Butterfly Diagram,
is shown in Fig. 3.20.
The input to this butterfly diagram or algorithm is the time-decimated signal
x
(shown above the topmost
row of boxes) from the final stage of time domain decimation. The values
x
[
0
]
,
x
[
4
]
, etc., are reinterpreted
as eight 1-pt DFTs which are labeled in pairs as
X
E
[
preparatory to combining to form
four 2-pt DFTs. The applicable values for
k
and twiddle factors
W
are shown to the right of each set of
butterflies.
0
]
and
X
O
[
0
]
