A Caltech Library Service

The synthesis of cyclic combinational circuits

Riedel, Marc D. and Bruck, Jehoshua (2003) The synthesis of cyclic combinational circuits. In: 40th Design Automation Conference. Association for Computing Machinery , New York, pp. 163-168. ISBN 1-58113-688-9.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 axe 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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Riedel, Marc D.0000-0002-3318-346X
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2003 ACM. Supported in part by the “Alpha Project” at the Center for Genomic Experimentation and Computation, a National Institutes of Health Center of Excellence in Genomic Sciences. The Alpha Project is supported by a grant from the National Human Genome Research Institute (grant no. P50 HG02370).
Funding AgencyGrant Number
Center for Genomic Experimentation and ComputationUNSPECIFIED
NIH Center of Excellence in Genomic SciencesUNSPECIFIED
National Human Genome Research InstituteP50 HG02370
Subject Keywords:Algorithms; Design; Logic Synthesis; Combinational Logic; Cycles; Feedback
Record Number:CaltechAUTHORS:20111012-143707754
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27201
Deposited By: Tony Diaz
Deposited On:13 Oct 2011 21:46
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page