Back to Search
Start Over
Advanced Functional Decomposition Using Majority and Its Applications.
- Source :
-
IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems . Aug2020, Vol. 39 Issue 8, p1621-1634. 14p. - Publication Year :
- 2020
-
Abstract
- Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and the 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such a decomposition can extend the capabilities of current logic decompositions, but only found limited attention in the previous work. Our algorithm make 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: 1) exact-synthesis-aware rewriting; 2) preoptimization for 6-input look-up table (6-LUT) mapping; and 3) synthesis of quantum circuits. An experimental evaluation shows that our algorithm leads to better XMGs compared to state-of-the-art algorithms based on XMGs, which positively affects all of these three applications. As one example, our experiments show that the proposed method achieves an average of 10% and 26% reduction on the LUTs size/depth product applied to the EPFL arithmetic and random control benchmarks after technology mapping, respectively. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*BOOLEAN functions
*DATA structures
*LOGIC design
*LOGIC
Subjects
Details
- Language :
- English
- ISSN :
- 02780070
- Volume :
- 39
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems
- Publication Type :
- Academic Journal
- Accession number :
- 144714981
- Full Text :
- https://doi.org/10.1109/TCAD.2019.2925392