Information Technology Reference
In-Depth Information
As shown in Section
2.2.2
, every Boolean function
f
:
B
n
→B
can be realized as the
OR
of its minterms. As shown in Section
2.5.4
, the minterms on
n
variables are produced by the
decoder function
f
(
n
)
2
n
, which has a circuit with 2
n
+(
2
n
decode
:
B
n
→B
−
2
)
2
n/
2
gates and
+
1. Consequently, we can realize
f
from a circuit for
f
(
n
)
depth
log
2
n
decode
and an
OR
tree
on at most 2
n
inputs (which has at most 2
n
−
1two-input
OR
's and depth at most
n
). We
n
have that every function
f
:
B
→B
has circuit size and depth satisfying:
C
Ω
f
(
n
)
decode
+
2
n
2
n
+
1
+(
2
n
2
)
2
n/
2
C
Ω
(
f
)
≤
−
≤
−
−
1
1
D
Ω
f
(
n
)
decode
+
n
D
Ω
(
f
)
≤
≤
n
+
log
2
n
+
1
+
1
n
Thus every Boolean function
f
:
B
→B
can be realized with an exponential number of
gates and depth
n
+
O
(log log
n
)
applies to
almost all Boolean functions on
n
variables (see Section
2.12
), this is a very good upper bound
on depth. We improve upon the circuit size bound after summarizing the depth bound.
log
2
n
+
1. Since the depth lower bound of
n
−
THEOREM
2.13.1
The depth complexity of every Boolean function
f
:
B
n
→B
satisfies the
following bound:
D
Ω
0
(
f
)
≤
n
+
log
2
n
+
1
We now describe a procedure to construct circuits of small size for arbitrary Boolean func-
tions on
n
variables. By the results of the preceding section, this size will be exponential in
n
.
The method of approach is to view an arbitrary Boolean function
f
:
n
on
n
input vari-
ables
x
as a function of two sets of variables,
a
,thefirst
k
variables of
x
,and
b
, the remaining
n
B
→B
k
variables of
x
.Thatis,
x
=
ab
where
a
=(
x
1
,
...
,
x
k
)
and
b
=(
x
k
+
1
,
...
,
x
n
)
.
As suggested by Fig.
2.22
, we rearrange the entries in the defining table for
f
into a rectan-
gular table with 2
k
rows indexed by
a
and 2
n−k
columns indexed by
b
. The lower right-hand
quadrant of the table contains the values of the function
f
. The value of
f
on
x
is the entry
at the intersection of the row indexed by the value of
a
and the column indexed by the value
of
b
.Wefix
s
and divide the lower right-hand quadrant of the table into
p
−
−
1groupsof
s
consecutive rows and one group of
s
≤
2
k
/s
s
consecutive rows where
p
=
. (Note that
1
)
s
+
s
=
2
k
.) Call the
i
th collections of rows
A
i
. This table serves as the basis for the
(
k
,
s
)
-Lupanov representation of
f
, from which a smaller circuit for
f
can be constructed.
Let
f
i
:
(
p
−
n
B
→B
be
f
restricted to
A
i
;thatis,
f
i
(
x
)=
f
(
x
)
if
a
∈
A
i
0
otherwise.
It follows that
f
can be expanded as the
OR
of the
f
i
:
p
f
(
x
)=
f
i
(
x
)
i
=
1
We now expand
f
i
.When
b
is fixed, the values for
f
i
(
ab
)
when
a
∈
A
i
constitute an
s
-tuple (
s
-tuple)
v
for 1
≤
i
≤
p
−
1(for
i
=
p
). Let
B
i
,
v
be those
(
n
−
k
)
-tuples
b
for
Search WWH ::
Custom Search