A Caltech Library Service

Cyclic Boolean circuits

Riedel, Marc D. and Bruck, Jehoshua (2012) Cyclic Boolean circuits. Discrete Applied Mathematics, 160 (13-14). pp. 1877-1900. ISSN 0166-218X. doi:10.1016/j.dam.2012.03.039.

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

Use this Persistent URL to link to this item:


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 of gates that are required by equivalent acyclic circuits. We also show a quadratic upper bound: given a cyclic Boolean circuit with m gates, there exists an equivalent acyclic Boolean circuit with m^2 gates.

Item Type:Article
Related URLs:
Riedel, Marc D.0000-0002-3318-346X
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2012 Elsevier B.V. Received 15 January 2010; Received in revised form 26 August 2011; Accepted 31 March 2012; Available online 14 May 2012. 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.
Funding AgencyGrant Number
NSF Expeditions in Computing ProgramCCF-0832824
MARCO Focus Center Research Program on Functional Engineered Nano-Architectonics (FENA)UNSPECIFIED
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:Boolean circuits; Boolean functions; Combinational circuits; Cyclic circuits; DAG; Cycles; Loops; Feedback
Issue or Number:13-14
Record Number:CaltechAUTHORS:20121109-103154708
Persistent URL:
Official Citation:Marc D. Riedel, Jehoshua Bruck, Cyclic Boolean circuits, Discrete Applied Mathematics, Volume 160, Issues 13–14, September 2012, Pages 1877-1900, ISSN 0166-218X, 10.1016/j.dam.2012.03.039.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:35385
Deposited By: Tony Diaz
Deposited On:14 Nov 2012 22:05
Last Modified:09 Nov 2021 23:14

Repository Staff Only: item control page