A collection of logic gates forms a combinational circuit if the outputs can be described
as boolean functions of the current input values. Optimizing combinational circuitry, for
instance, by reducing the number of gates (the area) or by reducing the length of the signal
paths (the delay), is an overriding concern in the design of integrated circuits.
The accepted wisdom is that combinational circuits must have acyclic (i.e., loopfree or
feedforward) topologies. In fact, the idea that "combinational" and "acyclic" are
synonymous terms is so thoroughly ingrained that many textbooks provide the latter as a
definition of the former. And yet simple examples suggest that this is incorrect. In this
dissertation, we advocate the design of cyclic combinational circuits (i.e., circuits with
loops or feedback paths). We demonstrate that circuits can be optimized effectively for area and
for delay by introducing cycles.
On the theoretical front, we discuss lower bounds and we prove that certain
families of functions can be implemented by cyclic circuits with 50% fewer gates than is possible with acyclic circuits. On the practical front,
we describe an efficient approach for analyzing cyclic circuits, and we provide a general
framework for synthesizing such circuits. On trials with industryaccepted benchmark
circuits, cyclic optimizations led to significant improvements in area and delay in nearly all cases. Based on
these results, we suggest that it is time to rewrite the definition: in both theory and practice, combinational might well
mean cyclic.
