CaltechTHESIS
A Caltech Library Service

# Cyclic Combinational Circuits

## Citation

Riedel, Marcus D. (2004) Cyclic Combinational Circuits. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/410B-XR25. https://resolver.caltech.edu/CaltechETD:etd-05032004-153842

## Abstract

A collection of logic gates forms a combinational circuit if the outputs can be described as Boolean functions of the current input values only. 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 digital integrated circuits.

The accepted wisdom is that combinational circuits must have acyclic (i.e., loop-free or feed-forward) 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 show that certain cyclic circuits are one-half the size of the best possible equivalent acyclic implementations. 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 industry-accepted benchmark circuits, we obtained significant improvements in area and delay in nearly all cases. Based on these results, we suggest that it is time to re-write the definition: combinational might well mean cyclic.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:combinational circuits; combinational logic; cycles; feedback; logic synthesis; loops
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Awards:Charles Wilts Prize, 2004.
Thesis Availability:Public (worldwide access)
• Bruck, Jehoshua
Thesis Committee:
• Bruck, Jehoshua (chair)
• Martin, Alain J.
• Hajimiri, Ali
• Viterbi, Andrew
• Winfree, Erik
• Abu-Mostafa, Yaser S.
Defense Date:17 November 2003
Non-Caltech Author Email:mriedel (AT) umn.edu
Funders:
Funding AgencyGrant Number
National Human Genome Research InstituteP50 HG02370
Lee Center for Advanced Networking at CaltechUNSPECIFIED
Record Number:CaltechETD:etd-05032004-153842
Persistent URL:https://resolver.caltech.edu/CaltechETD:etd-05032004-153842
DOI:10.7907/410B-XR25
ORCID:
AuthorORCID
Riedel, Marcus D.0000-0002-3318-346X
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1591
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:06 May 2004