Functional Decomposition Using Majority

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and a 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such decomposition can extend the capabilities of current logic decomposition, but only found limited attention in previous work. Our algorithm makes use of a decomposition rule based on MAJ. Combined with disjoint-support decomposition, the algorithm can factorize XOR-Majority Graphs (XMGs), a recently proposed data structure which has XOR, MAJ, and inverters as only logic primitives. XMGs have been applied in various applications, including (i) exact synthesis aware rewriting, (ii) pre-optimization for 6-LUT mapping, and (iii) synthesis of quantum networks. An experimental evaluation shows that our algorithm leads to better XMGs compared to state-of-the-art algorithms, which positively affect all these three applications. As one example, our experiments show that the proposed method achieves up to 37.1% with an average of 9.6% reduction on the look-up tables (LUT) size/depth product applied to the EPFL arithmetic benchmarks after technology mapping.

Published in:
Proceedings of the 23rd Asia and South Pacific Design Automation Conference (ASP-DAC)
Presented at:
23rd Asia and South Pacific Design Automation Conference (ASP-DAC)23rd Asia and South Pacific Design Automation Conference (ASP-DAC), Jeju Island, KoreaJeju Island, Korea, January 22-25, 2018January 22-25, 2018
Jan 25 2018
ERC Cybercare 669354 / SNF MAJesty 200021-169084 / NSF China 61501268 / Zhejiang Provincial NSF LQ15F040001 / Ningbo City NSF 2015A610112

 Record created 2018-01-09, last modified 2019-02-05

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)