Information Technology Reference
In-Depth Information
The basis for induction is that
D
Ω
f
(
1
)
mux
+
2
≤
d
(Ω) log
r
L
Ω
(
f
)
for
L
Ω
(
f
)=
2,
which we now show.
d
(Ω) log
r
L
Ω
(
f
)=
D
Ω
f
(
1
)
mux
+
1
(log
r
2
)
/
log
r
r
+
1
r
mux
+
1
/
log
2
r
+
1
=
D
Ω
f
(
1
)
r
1
.
7
D
Ω
f
(
1
)
mux
+
1
D
Ω
(
f
(
1
)
≥
≥
mux
)+
2
1
.
5and
D
Ω
f
(
1
)
mux
since
(
r
+
1
)
/r
1.
The inductive hypothesis is that any function
f
with a formula size
L
Ω
(
f
)
≤
≥
≤
L
0
−
1
can be realized by a circuit with depth
d
(Ω) log
r
L
Ω
(
f
)
.
Let
T
be the tree associated with a formula for
f
of size
L
0
. The value computed by
T
can be computed from the function
f
(
1
)
mux
using the values produced by three trees, as
suggested in Fig.
9.3
.Thetree
T
v
of Corollary
9.2.1
and two copies of
T
from which
T
v
has been removed and replaced by 0 in one case (the tree
T
0
) and 1 in the other (the tree
T
1
) are formed and the value of
T
v
is used to determine which of
T
0
and
T
1
is the value
T
.
Since
T
v
has at least
L
0
/
(
r
+
1
)
rL
0
/
(
r
+
1
)
≤
L
0
−
1 leaves, each of
T
0
and at most
and
T
1
has at most
L
0
−
L
0
/
(
r
+
1
)
=
rL
0
/
(
r
+
1
)
leaves. (See Problem
9.1
.) Thus,
rL
0
/
(
r
+
1
)
≤
L
0
−
all trees have at most
1 leaves and the inductive hypothesis applies.
Since the depth of the new circuit is the depth of
f
(
1
)
mux
plus the maximum of the depths of
the three trees,
f
has the following depth bound:
D
Ω
f
(
1
)
mux
+
d
(Ω) log
r
rL
Ω
(
f
)
(
r
+
1
)
D
Ω
(
f
)
≤
The desired result follows from the definition of
d
(Ω)
.
a
f
(
1
)
mux
y
0
y
1
T
v
T
T
0
T
1
0
1
T
v
(a)
(b)
Figure 9.3
Decomposition of a tree circuit
T
for the purpose of reducing its depth. A large
subtree
T
v
is removed and its value used to select the value computed by two trees formed from
theoriginaltreebyreplacingthevalueof
T
v
alternately by 0 and 1.
Search WWH ::
Custom Search