CaltechAUTHORS
  A Caltech Library Service

Cyclic Boolean circuits

Riedel, Marc D. and Bruck, Jehoshua (2009) Cyclic Boolean circuits. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2009.ETR099

[img]
Preview
PDF
See Usage Policy.

730Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2009.ETR099

Abstract

A Boolean circuit is a collection of gates and wires that performs a mapping from Boolean inputs to Boolean outputs. The accepted wisdom is that such circuits must have acyclic (i.e., loop-free or feed-forward) topologies. In fact, the model is often defined this way – as a directed acyclic graph (DAG). And yet simple examples suggest that this is incorrect. We advocate that Boolean circuits should have cyclic topologies (i.e., loops or feedback paths). In other work, we demonstrated the practical implications of this view: digital circuits can be designed with fewer gates if they contain cycles. In this paper, we explore the theoretical underpinnings of the idea. We show that the complexity of implementing Boolean functions can be lower with cyclic topologies than with acyclic topologies. With examples, we show that certain Boolean functions can be implemented by cyclic circuits with as little as one-half the number gates that are required by equivalent acyclic circuits.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://resolver.caltech.edu/CaltechAUTHORS:20121109-103154708Related ItemUNSPECIFIED
ORCID:
AuthorORCID
Riedel, Marc D.0000-0002-3318-346X
Additional Information:This work is partially supported by an NSF CAREER Award (grant CCF0845650), by the NSF Expeditions in Computing Program (grant CCF-0832824), by a grant from the MARCO Focus Center Research Program on Functional Engineered Nano-Architectonics (FENA), and by the Caltech Lee Center for Advanced Networking. Preprint submitted to Discrete Mathematics.
Group:Parallel and Distributed Systems Group
Subject Keywords:Boolean circuits, Boolean functions, combinational circuits, cyclic circuits, DAG, cycles, loops, feedback
Record Number:CaltechPARADISE:2009.ETR099
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2009.ETR099
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26130
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:09 Dec 2009
Last Modified:25 Feb 2014 22:02

Repository Staff Only: item control page