Cyclic Boolean circuits

Marc D. Riedel, Jehoshua Bruck

Research output: Research - peer-reviewArticle

  • 5 Citations

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 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 m2 gates.

LanguageEnglish (US)
Pages1877-1900
Number of pages24
JournalDiscrete Applied Mathematics
Volume160
Issue number13-14
DOIs
StatePublished - Sep 1 2012

Fingerprint

Boolean Circuits
Topology
Networks (circuits)
Boolean Functions
Boolean functions
Digital Circuits
Directed Acyclic Graph
Feedforward
Upper bound
Cycle
Path
Output
Model
Digital circuits
Wire
Feedback

Keywords

  • Boolean circuits
  • Boolean functions
  • Combinational circuits
  • Cycles
  • Cyclic circuits
  • DAG
  • Feedback
  • Loops

Cite this

Cyclic Boolean circuits. / Riedel, Marc D.; Bruck, Jehoshua.

In: Discrete Applied Mathematics, Vol. 160, No. 13-14, 01.09.2012, p. 1877-1900.

Research output: Research - peer-reviewArticle

Riedel, MD & Bruck, J 2012, 'Cyclic Boolean circuits' Discrete Applied Mathematics, vol 160, no. 13-14, pp. 1877-1900. DOI: 10.1016/j.dam.2012.03.039
Riedel MD, Bruck J. Cyclic Boolean circuits. Discrete Applied Mathematics. 2012 Sep 1;160(13-14):1877-1900. Available from, DOI: 10.1016/j.dam.2012.03.039
Riedel, Marc D. ; Bruck, Jehoshua. / Cyclic Boolean circuits. In: Discrete Applied Mathematics. 2012 ; Vol. 160, No. 13-14. pp. 1877-1900
@article{8fca47a24a2b4deb90fac0223df4d410,
title = "Cyclic Boolean circuits",
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 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 m2 gates.",
keywords = "Boolean circuits, Boolean functions, Combinational circuits, Cycles, Cyclic circuits, DAG, Feedback, Loops",
author = "Riedel, {Marc D.} and Jehoshua Bruck",
year = "2012",
month = "9",
doi = "10.1016/j.dam.2012.03.039",
volume = "160",
pages = "1877--1900",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "13-14",

}

TY - JOUR

T1 - Cyclic Boolean circuits

AU - Riedel,Marc D.

AU - Bruck,Jehoshua

PY - 2012/9/1

Y1 - 2012/9/1

N2 - 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 m2 gates.

AB - 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 m2 gates.

KW - Boolean circuits

KW - Boolean functions

KW - Combinational circuits

KW - Cycles

KW - Cyclic circuits

KW - DAG

KW - Feedback

KW - Loops

UR - http://www.scopus.com/inward/record.url?scp=84862189627&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862189627&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2012.03.039

DO - 10.1016/j.dam.2012.03.039

M3 - Article

VL - 160

SP - 1877

EP - 1900

JO - Discrete Applied Mathematics

T2 - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 13-14

ER -