Information Technology Reference
In-Depth Information
CHAPTER
Algebraic and Combinatorial
Circuits
Algebraic circuits combine operations drawn from an algebraic system. In this chapter we de-
velop algebraic and combinatorial circuits for a variety of generally non-Boolean problems, in-
cluding multiplication and inversion of matrices, convolution, the discrete Fourier transform,
and sorting networks. These problems are used primarily to illustrate concepts developed in
later chapters, so that this chapter may be used for reference when studying those chapters.
For each of the problems examined here the natural algorithms are straight-line and the
graphs are directed and acyclic; that is, they are circuits. Not only are straight-line algorithms
the ones typically used for these problems, but in some cases they are the best possible.
The quality of the circuits developed here is measured by circuit size, the number of circuit
operations, and circuit depth, the length of the longest path between input and output ver-
tices. Circuit size is a measure of the work necessary to execute the corresponding straight-line
program. Circuit depth is a measure of the minimal time needed for a problem on a parallel
machine.
For some problems, such as matrix inversion, we give serial (large-depth) as well as par-
allel (small-depth) circuits. The parallel circuits generally require considerably more circuit
elements than the corresponding serial circuits.
237
Search WWH ::
Custom Search