Information Technology Reference
In-Depth Information
the
i
th input vertex from the left is obtained by writing the integer
i
as a binary number,
reversing the bits, and converting the resulting binary number to an integer. This is called the
bit-reverse permutation
of the binary representation of the integer. For example, the third
input from the left has index 3, which is (011) in binary. Reversed, the binary number is (110),
which represents 12.) Inputs are associated with the open vertices at the bottom of the graph.
Each vertex except for input vertices is associated with an addition and a multiplication. For
example, the white vertex at the top of the graph computes
f
8
=
p
e
((
ω
8
)
2
)+
ω
8
p
o
((
ω
8
)
2
)
,
where
(
ω
8
)
2
=
ω
16
=
ω
.
Let
C
(
F
(
d
)
)
and
D
(
F
(
d
)
)
be the size and depth of circuits for the 2
d
-point FFT algorithm
for integer
d
≥
1. The construction given above leads to the following recurrences for these
two measures:
C
F
(
d
)
2
C
F
(
d−
1
)
+
2
d
+
1
≤
D
F
(
d−
1
)
+
2
Also, examination of the base case of
n
=
2demonstratesthat
C
F
(
1
)
=
3and
D
F
(
1
)
=
2, from which we have the following theorem.
D
F
(
d
)
≤
THEOREM
6.7.1
Let
n
=
2
d
.Thecircuitforthe
n
-point FFT algorithm over a commutative
ring
R
has the following circuit size and depth bounds:
C
F
(
d
)
≤
2
n
log
n
D
F
(
d
)
≤
2
log
n
The FFT graph is used in later chapters to illustrate tradeoffs between space and time, space
and the number of I/O operations, and area and time for computation with VLSI machines.
For each of these applications we decompose the FFT graph into sub-FFT graphs. One such
decomposition is shown in Fig.
6.7
. A more general decomposition is shown in Fig.
6.8
and
described below.
LEMMA
6.7.4
The
2
d
-point FFT graph
F
(
d
)
can be decomposed into
2
e
2
d−e
-point
bottom
F
(
d−e
)
b
,
j
F
(
e
)
t
,
j
2
e
,and
2
d−e
2
e
-point
top
FFT graphs,
FFT graphs,
{
|
1
≤
j
≤
}
{
|
1
≤
j
≤
.The
i
th input of
F
(
e
)
t
,
j
is the
j
th output of
F
(
d−e
)
b
,
i
2
d−e
}
.
In Fig.
6.8
the vertices and edges have been grouped together as recognizable FFT graphs
and surrounded by shaded boxes. The edges between boxes are not edges of the FFT graph but
instead are used to identify vertices that are simultaneously outputs of bottom FFT subgraphs
and inputs to top FFT subgraphs.
COROLLARY
6.7.1
F
(
d
)
stages each containing
2
d−e
can be decomposed into
d/e
copies of
F
(
e
)
and one stage containing
2
d−k
copies of
F
(
k
)
,
k
=
d
−
d/e
e
.(
F
(
0
)
is a single vertex.)
The output vertices of one stage are the input vertices to the next.
Proof
From Lemma
6.7.4
,eachofthe2
e
bottom FFT subgraphs
F
(
d−e
)
can be further
decomposed into 2
d−
2
e
top FFT subgraphs
F
(
e
)
and 2
e
bottom FFT subgraphs
F
(
d−
2
e
)
.
By repeating this process
t
times,
t
d/e
,
F
(
d
)
≤
can be decomposed into
t
stages each
Search WWH ::
Custom Search