Information Technology Reference
In-Depth Information
9.1
Circuit Models and Measures
In this section we characterize types of logic circuits by their bases and the fan-in and fan-
out of basis elements. We consider bases that are complete and incomplete and that have
bounded and unbounded fan-in. We also consider circuits in which the fan-out is restricted
and unrestricted. Each of these factors can affect the size and depth of a circuit.
9.1.1 Circuit Models
The (general)
logic circuit
is the graph of a straight-line program in which the variables have
value 0 or 1 and the operations are Boolean functions
g
:
p
B
→B
,
p
≥
1. (Boolean functions
have one binary value. Logic circuits are defined in Section
1.2
and discussed at length in
Chapter
2
.) The vertices in a logic circuit are labeled with Boolean operations and are called
gates
; the set of different gate types used in a circuit is called the
basis
(denoted
Ω
)forthe
circuit. The
fan-in of a basis
is the maximal fan-in of any function in the basis. A circuit
computes
the binary function
f
:
m
, which is the mapping from the
n
circuit inputs
to the
m
gate outputs designated as circuit outputs.
The
standard basis
, denoted
Ω
0
,istheset
n
B
→B
{
}
in which
AND
and
OR
have
fan-in 2. The
full two-input basis
, denoted
B
2
, consists of all two-input Boolean functions.
The
dyadic unate basis
, denoted
U
2
, consists of al
l
Boolean functions of the form
(
x
a
AND
,
OR
,
NOT
y
b
)
c
∧
.Here
x
1
=
x
and
x
0
=
x
.
A
basis
Ω
is
complete
if every binary function can be computed by a circuit over
Ω
.The
bases
Ω
0
,
B
2
,and
U
2
a
re com
plete, as is the basis consisting of the
NAND
gate computing the
function
x
NAND
y
=
x
for constants
a
,
b
,
c
in
B
y
. (See Problem
2.5
.)
The bounded fan-out circuit model specifies a bound on the fan-out of a circuit. As we
shall see, the
fan-out-1 circuit
plays a special role related to circuit depth. Each circuit of
fan-out 1 corresponds to a
formula
in which the operators are the functions associated with
vertices of the circuit. Figure
9.1
shows an example of a circuit of fan-out 1 over the standard
basis and its associated formula. (See also Problem
9.9
.) Although each input variable appears
once in this example, Boolean functions generally require multiple instances of variables (have
fan-out greater than 1). Formula size is studied at length in Section
9.4
.
To define the monotone circuits, we need an ordering of binary
n
-tuples. Two such tuples,
x
=(
x
1
,
x
2
,
...
,
x
n
)
and
y
=(
y
1
,
y
2
,
...
,
y
n
)
, are in the relation
x
≤
y
if for all 1
∧
≤
i
≤
n
,
x
i
≤
y
i
,where0
≤
≤
≤
≤
≤
0, 1
1, and 0
1, but 1
0. (Thus, 001011
101111, but
≤
011011
101111.)
A
monotone circuit
is a circuit over the monotone basis
Ω
mon
=
{
}
in which
the fan-in is 2. There is a direct correspondence between monotone circuits and monotone
functions. A
monotone function
is a function
f
:
AND
,
OR
n
m
B
→B
that is either
monotone
n
,if
x
increasing
,thatis,forall
x
,
y
∈B
≤
y
,then
f
(
x
)
≤
f
(
y
)
,oris
monotone
n
,if
x
decreasing
,thatis,forall
x
,
y
f
(
y
)
. Unless stated explicitly, a
monotone function will be understood to be a monotone increasing function.
A monotone Boolean function has the following expansion on the first variable, as the
reader can show. (See Problem
9.10
.) A similar expansion is possible on any variable.
∈B
≤
y
,then
f
(
x
)
≥
f
(
x
1
,
x
2
,
...
,
x
n
)=
f
(
0,
x
2
,
...
,
x
n
)
∨
(
x
1
∧
f
(
1,
x
2
,
...
,
x
n
))
By applying this expansion to every variable in succession, we see that each monotone function
can be realized by a circuit over the monotone basis. Furthermore, the
monotone basis
Ω
mon
Search WWH ::
Custom Search