Biomedical Engineering Reference
In-Depth Information
1
X
m
(
p
)
X
m
+1
(
p
)
r
W
N
1
X
m
(
q
)
X
m
+1
(
q
)
W
N
r+N/
2
FIGURE 13.3
:
FFT “Butterfly” signal flow diagram
13.5 THE FF T “BUTTERFLY ” SIGNAL FLOW DIAGRAM
To predict the next value in the stage (decimation), the previous stage values are used as
inputs, where
p
may indicate the odd sequence and
q
the even sequence. The flow graph
(Fig. 13.3) is called the “butterfly computation” because of its appearance.
The output of the stage is calculated with (13.15) and (13.16).
W
r
N
X
m
(
q
)
=
+
(13.15)
X
m
+1
(
p
)
X
m
(
p
)
N
2
W
r
+
X
m
+1
(
q
)
=
X
m
(
p
)
+
X
m
(
q
)
(13.16)
N
However, from symmetry and periodicity properties:
N
2
N
e
−
j
(
2
N
)(
2
)
e
−
j
π
=−
W
=
=
1
the reduced Butterfly flow diagram becomes Fig. 13.4 and the equations are rewritten as
1
X
m
+1
(
p
)
X
m
(
p
)
1
1
X
m
(
q
)
X
m
+1
(
q
)
−
1
FIGURE 13.4
:
Reduced Butterfly flow diagram
Search WWH ::
Custom Search