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

CHAPTER
Logic Circuits
Many important functions are naturally computed with straight-line programs ,programs
without loops or branches. Such computations are conveniently described with circuits ,di-
rected acyclic graphs of straight-line programs. Circuit vertices are associated with program
steps, whereas edges identify dependencies between steps. Circuits are characterized by their
size , the number of vertices, and their depth , the length (in edges) of their longest path.
Circuits in which the operations are Boolean are called logic circuits , those using algebraic
operations are called algebraic circuits , and those using comparison operators are called com-
parator circuits . In this chapter we examine logic circuits. Algebraic and comparator circuits
are examined in Chapter 6 .
Logic circuits are the basic building blocks of real-world computers. As shown in Chap-
ter 3 , all machines with bounded memory can be constructed of logic circuits and binary
memory units. Furthermore, machines whose computations terminate can be completely sim-
ulated by circuits.
In this chapter circuits are designed for a large number of important functions. We begin
with a discussion of circuits, straight-line programs, and the functions computed by them.
Normal forms, a structured type of circuit, are examined next. They are a starting point for
the design of circuits that compute functions. We then develop simple circuits that combine
and select data. They include logical circuits, encoders, decoders, multiplexers, and demulti-
plexers. This is followed by an introduction to prefix circuits that efficiently perform running
sums. Circuits are then designed for the arithmetic operations of addition (in which prefix
computations are used), subtraction, multiplication, and division. We also construct efficient
circuits for symmetric functions. We close with proofs that every Boolean function can be
realized with size and depth exponential and linear, respectively, in its number of inputs, and
that most Boolean functions require such circuits.
The concept of a reduction from one problem to a previously solved one is introduced in
this chapter and applied to many simple functions. This important idea is used later to show
that two problems, such as different NP -complete problems, have the same computational
complexity. (See Chapters 3 and 8 .)
35