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

Language | English (US) |
---|---|

Pages | 1877-1900 |

Number of pages | 24 |

Journal | Discrete Applied Mathematics |

Volume | 160 |

Issue number | 13-14 |

DOIs | |

State | Published - Sep 1 2012 |

### Fingerprint

### Keywords

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

### Cite this

*Discrete Applied Mathematics*,

*160*(13-14), 1877-1900. DOI: 10.1016/j.dam.2012.03.039

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

Research output: Research - peer-review › Article

*Discrete Applied Mathematics*, vol 160, no. 13-14, pp. 1877-1900. DOI: 10.1016/j.dam.2012.03.039

}

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 -