Logic Circuits - Models of Computation: Exploring the Power of Computing - page 36

2.1 Designing Circuits
The logic circuit, as defined in Section 1.4.1 , is a directed acyclic graph (DAG) whose vertices
are labeled with the names of Boolean functions (logic gates) or variables (inputs). Each logic
circuit computes a binary function f :

n m

B →B that is a mapping from the values of its n

input variables to the values of its m outputs.
Computer architects often need to design circuits for functions, a task that we explore in
this chapter. The goal of the architect is to design efficient circuits, circuits whose size (the
number of gates) and/or depth (the length of the longest path from an input to an output
vertex) is small. The computer scientist is interested in circuit size and depth because these
measures provide lower bounds on the resources needed to complete a task. (See Section 1.5.1
and Chapter 3 .) For example, circuit size provides a lower bound on the product of the
space and time needed for a problem on both the random-access and Turing machines (see
Sections 3.6 and 3.9.2 ) and circuit depth is a measure of the parallel time needed to compute
afunction(seeSection 8.14.1 ).
The logic circuit also provides a framework for the classification of problems by their com-
putational complexity. For example, in Section 3.9.4 we use circuits to identify hard compu-
tational problems, in particular, the P -complete languages that are believed hard to parallelize
and the NP -complete languages that are believed hard to solve on serial computers. After more
than fifty years of research it is still unknown whether NP -complete problems have polynomial-
time algorithms.
In this chapter not only do we describe circuits for important functions, but we show that
most Boolean functions are complex. For example, we show that there are so many Boolean
functions on n variables and so few circuits containing C or fewer gates that unless C is large,
not all Boolean functions can be realized with C gates or fewer.
Circuit complexity is also explored in Chapter 9 . The present chapter develops methods
to derive lower bounds on the size and depth of circuits. A lower bound on the circuit size
(depth) of a function f is a value for the size (depth) below which there does not exist a circuit
for f . Thus, every circuit for f must have a size (depth) greater than or equal to the lower
bound. In Chapter 9 we also establish a connection between circuit depth and formula size,
the number of Boolean operations needed to realize a Boolean function by a formula. This
allows us to derive an upper bound on formula size from an upper bound on depth. Thus, the
depth bounds of this chapter are useful in deriving upper bounds on the size of the smallest
formulas for problems. Prefix circuits are used in the present chapter to design fast adders.
They are also used in Chapter 6 to design fast parallel algorithms.

2.2 Straight-Line Programs and Circuits
As suggested in Section 1.4.1 , the mapping between inputs and outputs of a logic circuit can
be described by a binary function. In this section we formalize this idea and, in addition,
demonstrate that every binary function can be realized by a circuit. Normal-form expansions
of Boolean functions play a central role in establishing the latter result. Circuits were defined
informally in Section 1.4.1 . We now give a formal definition of circuits.
To fix ideas, we start with an example. Figure 2.1 shows a circuit that contains two AND
gates, one OR gate, and two NOT gates. (Circles denote NOT gates, AND and OR gates are
labeled

∧ and ∨ , respectively.) Corresponding to this circuit is the following functional de-