2020/05/04 by Mathias Soeken, Soeken, Mathias
Computer Science · Engineering · #B.6.3 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Low-power high-performance VLSI design #Quantum Physics (quant-ph) #VLSI and Analog Circuit Testing
paper · pdf · doi:10.48550/arxiv.2005.01778
openalex publication_date 2020/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a constructive SAT-based algorithm to determine the multiplicative complexity of a Boolean function, i.e., the smallest number of AND gates in any logic network that consists of 2-input AND gates, 2-input XOR gates, and inverters. In order to speed-up solving time, we make use of several symmetry breaking constraints; these exploit properties of XAGs that may be useful beyond the proposed SAT-based algorithm. We further propose a heuristic post-optimization algorithm to reduce the number of XOR gates once the optimum number of AND gates has been obtained, which also makes use of SAT solvers. Our algorithm is capable to find all optimum XAGs for representatives of all 5-input affine-equivalent classes, and for a set of frequently occurring 6-input functions.