Digital circuits are called
combinational if they are memoryless: they have outputs that depend only
on the current values of the inputs. Combinational circuits are generally
thought of as acyclic (i.e., feed-forward) structures. And yet, cyclic
circuits can be combinational. Cycles sometimes occur in designs
synthesized from high-level descriptions. Feedback in such cases is
carefully contrived, typically occurring when functional units are
connected in a cyclic topology. Although the premise of cycles in
combinational circuits has been accepted, and analysis techniques have
been proposed, no one has attempted the synthesis of circuits with
feedback at the logic level.
We propose a general methodology for the
synthesis of multilevel combinational circuits with cyclic topologies. Our
approach is to introduce feedback in the substitution/minimization
phase, optimizing a multilevel network description for area. In trials
with benchmark circuits, many were optimized significantly, with
improvements of up to 30% in the area.
We argue the case for radically rethinking the concept
of "combinational'' in circuit design: we should no longer think of
combinational logic as acyclic in theory or in practice, since nearly all
combinational circuits are best designed with cycles.