Information Technology Reference
In-Depth Information
DEFINITION
9.3.2
A Boolean function
f
:
B
belongs to the class
F
(
n
,
k
)
n
+
k
,
2
k
→B
≥
n
,if
s
for some set
S
⊆{
0, 1,
...
,
n
−
1
}
,
|
S
|
=
s
,
f
(
a
k−
1
,
...
,
a
1
,
a
0
,
x
n−
1
,
...
,
x
0
)=
x
|
a
|
for
|
a
|∈
S
.
Clearly,
f
(
n
,
k
)
SA
is a member of
F
(
n
,
k
)
. We now show that every function in
F
(
n
,
k
)
has circuit
n
s
size that is at least 2
s
2.
In the proof of Theorem
9.3.2
the gate-elimination method replaced variables with con-
stants. In the following proof this idea is extended to replacing variables by functions. Applying
thisresult,wehavethat
C
Ω
(
f
(
n
)
−
2
n
+
1
mux
)
≥
−
1.
THEOREM
9.3.3
Let
f
:
B
belong to
F
(
n
,
k
)
n
+
k
,
2
k
→B
≥
n
. Then over the basis
B
2
the
s
circuit size of
f
satisfies the following bound:
2
Proof
In the proof of Theorem
9.3.2
we used the fact that some input variable has fan-out
2 or more, as deduced from a property of functions in
Q
(
n
)
C
Ω
(
f
)
≥
2
s
−
2,3
. This fact does not hold for the
storage access function (multiplexer), as can be seen from the construction in Section
2.5.5
.
Thus, our lower-bound argument must explicitly take into account the fact that the fan-out
from some input can be 1.
The following proof uses the fact that the basis
B
2
contains functions of two kinds,
AND
-
type and parity-type functions. The former compute expressions of the form
(
x
a
y
b
)
c
for
Boolean constants
a
,
b
,
c
,wherethenotation
x
c
denotes
x
when
c
=
1and
x
when
c
=
0.
Parity-type functions compute expressions of the form
x
∧
⊕
y
⊕
c
for some Boolean constant
c
. (See Problem
9.19
.)
The proof is by induction on the value of
s
. In the base case
s
=
1 and the lower bound
is trivially 0. The inductive hypothesis assumes that for
s
=
s
−
2
(
s
−
1,
C
Ω
(
f
)
≥
1
)
−
2.
We l e t
s
=
s
and consider the following mutually exclusive cases:
a) For some
i
S
,
x
i
has fan-out 2. Replacing
x
i
by a constant allows elimination of
at least two gates, replaces
S
by
S
∈
, which has size
s
−
−{
i
}
1, and reduces
f
to
F
(
n
,
k
)
s
−
f
∗
∈
1
, from which we conclude that
2
+
C
Ω
(
f
∗
)
2
s
+
2
=
2
s
C
Ω
(
f
)
≥
≥
−
2
b) For some
i
S
,
x
i
hasfan-out1,itsuniquesuccessorisagate
G
of
AND
-type, and
G
computes
th
e expression
(
x
i
∧
∈
g
b
)
c
for some function
g
of the inputs. Setting
x
i
=
a
sets
x
i
=
a
a
=
0, thereby causing the expression to have value 0
c
,whichisaconstant.
Since
G
cannot be the output gate, this substitution allows the elimination of
G
and at
least one successor gate, reduces
f
to
f
∗
∈
F
(
n
,
k
)
s
−
1
,andreplaces
S
by
S
−{
i
}
,from
which the lower bound follows.
c) For some
i
S
,
x
i
hasfan-out1,itsuniquesuccessorisagate
G
of parity-type, and
G
computes the expression
x
i
⊕
∈
g
⊕
c
for some function
g
of the inputs. Replace
S
by
S
−{
i
}
. Since we ask that the output of the circuit be
x
|
a
|
for
a
∈
S
−{
i
}
,thisoutput
Search WWH ::
Custom Search