Mapping Monotone Boolean Functions into Majority
- 14 November 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 68 (5) , 791-797
Abstract
We consider the problem of decomposing monotone Boolean functions into majority-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) for monotone functions into majority-inverter graphs (MIGs), using a simple one-to-one mapping. This process highlights desirable properties for further majority graph optimization, e.g., symmetries between the inputs of primitive operations, which are not apparent from BDDs. Although our construction yields a quadratic upper bound on the number of majority-3 operations required to realize majority-n, for small n the concrete values are much smaller compared to those obtained from previous constructions which have linear and quasi-linear asymptotic upper bounds. Further, we demonstrate that minimum size MIGs, for the monotone functions majority-5 and majority-7, can be obtained applying a small number of algebraic transformations to the BDD.Keywords
Funding Information
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (200021-169084 MAJesty, ERC-2014-ADG 669354 CyberCare)
- ENEAC (EP/N002539/1)
This publication has 26 references indexed in Scilit:
- BDS-MAJ2013
- Non-volatile magnonic logic circuits engineeringJournal of Applied Physics, 2011
- Uniform constant-depth threshold circuits for division and iterated multiplicationJournal of Computer and System Sciences, 2002
- On TC0, AC0, and Arithmetic CircuitsJournal of Computer and System Sciences, 2000
- Selecting the MedianSIAM Journal on Computing, 1999
- Logical devices implemented using quantum cellular automataJournal of Applied Physics, 1994
- Quantum cellular automataNanotechnology, 1993
- On Threshold Circuits and Polynomial ComputationSIAM Journal on Computing, 1992
- Medians and betweennessProceedings of the American Mathematical Society, 1954
- A ternary operation in distributive latticesBulletin of the American Mathematical Society, 1947