Information Technology Reference
In-Depth Information
cannot depend on the value of
G
because a change in
x
i
would cause the value of
G
to
change. Thus,
G
is not the output gate and when
a
∈
S
−{
i
}
we can set its value to
any function without affecting the value computed by the circuit. In particular, setting
x
i
=
g
causes
G
to have value
c
, a constant. This substitution allows the elimination of
G
and at least one successor gate, and reduces
f
to
f
∗
∈
F
(
n
,
k
)
s
−
1
,fromwhichthelower
bound follows.
Thus, in all cases,
C
Ω
(
f
)
≥
2
s
−
2.
The lower bounds given above are derived for two functions over the basis
B
2
.Thebest
circuit-size lower bound that has been derived for this basis is 3
(
n
1
)
. When the basis
is restricted, larger lower bounds may result, as mentioned in the notes and illustrated by
Problems
9.22
and
9.23
.
−
9.4 Lower-Bound Methods for Formula Size
Since formulas correspond to circuits of fan-out 1, the formula size of a function may be much
larger than its circuit size. In this section we introduce two techniques for deriving lower
bounds on formula size that illustrate this point. Each leads to bounds that are quadratic or
nearly quadratic in the number of inputs. The first, due to Neciporuk [
230
], applies to any
complete basis. The second, due to Krapchenko [
174
], applies to the standard basis
Ω
0
.
To fix ideas about formula size, we construct a circuit of fan-out 1 for the
indirect storage
access function
f
(
k
,
l
)
ISA
k
+
lK
+
L
,where
K
=
2
k
and
L
=
2
l
:
:
B
→B
f
(
k
,
l
)
ISA
(
a
,
x
K−
1
,
...
,
x
0
,
y
)=
y
|
x
|
a
|
|
Here
a
is a
k
-tuple,
x
j
=(
x
j
,
l−
1
,
...
,
x
j
,0
)
is an
l
-tuple for 0
≤
j
≤
K
−
1, and
y
=(
y
L−
1
,
...
,
y
0
)
is an
L
-tuple. The value of
f
(
k
,
l
)
is computed by indirection; that is,
ISA
the value of
a
is treated as a binary number with value
|
a
|
that is used to select the
|
a
|
th
l
-tuple
x
|
a
|
; this, in turn, is treated as a binary number and its value is used to select the
|
x
|
a
|
|
th variable in
y
.
A circuit realizing
f
(
k
,
l
)
ISA
from multiple copies of the multiplexer (direct storage access
function)
f
(
n
)
2
n
+
n
mux
:
B
→B
is shown schematically in Fig.
9.5
. This circuit uses
l
copies
of
f
(
k
)
and one copy of
f
(
l
)
.Thecopiesof
f
(
k
)
2
k
+
k
2
l
+
l
mux
:
B
→B
mux
:
B
→B
mux
produce
th
l
-tuple, which is supplied to the copy of
f
(
l
)
the
|
a
|
mux
to select a variable from
y
.Since,as
shown in Lemma
2.5.5
,thefunction
f
(
k
)
mux
can be realized by a circuit of size linear in 2
k
,a
circuit for
f
(
k
,
l
)
ISA
can be constructed that is also linear in the size of its input.
A formula for
f
(
k
,
l
)
ISA
has fan-out of 1 from every gate. The circuit sketched in Fig.
9.5
has
fan-out 1 if and only if the fan-out within each multiplexer circuit is also 1. To construct a
formula from this circuit, we first construct one for
f
(
l
)
mux
. The total number of times that
address bits appear in a formula for
f
(
l
)
mux
determines the number of copies of the formula for
f
(
k
)
mux
that are used in the formula for
f
(
k
,
l
)
ISA
. A proof by induction can be developed to show
that a formula for
f
(
p
)
mux
can be constructed of size 32
p
2 in which address bits occur 2
(
2
p
−
−
1
)
times. (See Problem
9.24
.) Since each occurrence of an address bit in
f
(
l
)
mux
corresponds to a
copy of the formula for
f
(
k
)
mux
, by choosing
L
=
2
l
=
n
and
k
the smallest integer such that
Search WWH ::
Custom Search