.png){kind=icon}
.png){kind=icon}
Return
Mapping Monotone Boolean Functions into Majority
.png){kind=icon}
OA
AI
DOI：10.1109/TC.2018.2881245.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Weconsider the problemof decomposingmonotone Boolean functions intomajority-of-three operations, with a particular focus on decomposing the majority-n function. When targeting monotone Boolean functions, Shannon's expansion can be expressed by a single majority-of-three operation. We exploit this property to transform binary decision diagrams (BDDs) formonotone functions intomajority-inverter graphs (MIGs), using a simple one-to-onemapping. This process highlights desirable properties for furthermajority graph optimization, e.g., symmetries between the inputs of primitive operations, which are not apparent fromBDDs. Although our construction yields a quadratic upper bound on the number ofmajority-3 operations required to realizemajority-n, forsmall n the concrete values are much smaller compared to those obtained fromprevious constructions which have linear and quasi-linear asymptotic upper bounds. Further, we demonstrate that minimumsize MIGs, for the monotone functionsmajority-5 and majority-7, can be obtained applying a small number of algebraic transformations to the BDD.
Keywords:
Binary decision diagrams
majority logic
majority-inverter graphs
function decomposition
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K