Information Technology Reference
In-Depth Information
functions are non-monotone (
x
, for example), some function
g
in a complete basis
Ω
is non-
monotone. This means there exist tuples
x
and
y
for
g
,
x
y
,suchthat
g
(
x
)=
1
>g
(
y
)=
0. Let
u
and
v
be the largest and smallest tuples, respectively, satisfying
x
≤
y
and
g
(
u
)=
1and
g
(
v
)=
0. Then
u
and
v
differ in at most one position. Without loss
of generality, let that position be the first and let the values in the remaining positions in
both tuples be
(
c
2
,
.
..
,
c
n
)
. It follows that
g
(
1,
c
2
,
...
,
c
n
)=
0and
g
(
0,
c
2
,
...
,
c
n
)=
1or
g
(
x
,
c
2
,
...
,
c
n
)=
x
.If
l
(Ω)
is the number of gates from
Ω
needed to realize the identity
function, then
l
(Ω) =
1or2.
≤
u
≤
v
≤
THEOREM
9.2.1
Let
Ω
be a complete basis of
n
m
. The following
fan-in
r
and let
f
:
B
→B
inequalities hold on
C
s
,
Ω
(
f
)
:
C
Ω
(
f
)
≤
C
s
+
1,
Ω
(
f
)
≤
C
s
,
Ω
(
f
)
≤
C
1,
Ω
(
f
)
Furthermore,
C
s
,
Ω
(
f
)
has the following relationship to
C
Ω
(
f
)
for
s
≥
2
:
C
Ω
(
f
)
1
+
l
(Ω)(
r
−
1
)
C
s
,
Ω
(
f
)
≤
s
−
1
Proof
The first set of inequalities holds because a smallest circuit with fan-out
s
is no smaller
than a smallest circuit with fan-out
s
+
1, a less restrictive type of circuit.
The last inequality follows by constructing a tree of identity functions at each gate whose
fan-out exceeds
s
.(SeeFig.
9.2
.) If a gate has fan-out
φ>s
,reducethefan-outto
s
and
then attach an identity gate to one of these
s
outputs. This increases the fan-out from
s
to
s
+
s
1. If
φ
is larger than this number, repeat the process of adding an identity gate
k
times, where
k
is the smallest integer such that
s
+
k
(
s
−
−
1
)
≥
φ
or is the largest integer
such that
s
+(
k
1
)
.
Let
φ
i
denote the fan-out of the
i
th gate in a circuit for
f
of potentially unbounded
fan-out and let
k
i
be the largest integer satisfying the following bound:
−
1
)(
s
−
1
)
<φ
.Thus,
k<
(
φ
−
1
)
/
(
s
−
k
i
<
φ
i
−
1
s
−
1
Then at most
i
(
k
i
l
(Ω) +
1
)
gates are needed in the circuit of fan-out
s
to realize
f
,
one for the
i
th gate in the original circuit and
k
i
l
(Ω)
gates for the
k
i
copies of the identity
(a)
Figure 9.2
Conversion of a vertex with fan-out more than
s
to a subtree with fan-out
s
,
illustrated for
s
=
2.
(b)
Search WWH ::
Custom Search