The synthesis of cyclic combinational circuits

Marc D. Riedel, Jehoshua Bruck

Research output: Contribution to journalConference articlepeer-review

42 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)163-168
Number of pages6
JournalProceedings - Design Automation Conference
DOIs
StatePublished - 2003
EventProceedings of the 40th Design Automation Conference - Anaheim, CA, United States
Duration: Jun 2 2003Jun 6 2003

Keywords

  • Combinational Logic
  • Cycles
  • Feedback
  • Logic Synthesis

Fingerprint

Dive into the research topics of 'The synthesis of cyclic combinational circuits'. Together they form a unique fingerprint.

Cite this