Improved Linear Decomposition of Majority and Threshold Boolean Functions

Abstract

To support efficient design automation for emerging computing fabrics, novel data structures for logic synthesis and technology mapping are being intensively studied. It has been shown that for several promising computing technologies intermediate forms, such as Majority-inverter graph (MIG) and XOR-Majority graph (XMG) can be particularly beneficial. This has propelled the Boolean Majority operator at the forefront of research. Though these structures primarily utilize 3-input Majority nodes, the efficacy of n-input Majority operators has been demonstrated as well. A long-standing research problem, in that context and also for theoretical circuit complexity, is to determine efficient decomposition of an n-input Majority (Maj(n)) function in terms of 3-input Majority (Maj(3)) operator. In this manuscript, we make two significant advances in this topic. First, a practically realizable linear decomposition is provided, thus improving the previously reported quadratic bounds. Second, the theoretical upper bound of decomposing Maj(n), in terms of Maj(3), is reduced from 5.884n to 3n. The erstwhile theoretical upper bound of 5.884n also lacked a practical construction for Maj(n) decomposition, presumably due to the presence of sequential elements in the algorithm. The proof of the linearity, detailed construction procedure along with experimental studies using state-of-the-art synthesis flows to validate the aforementioned claims are presented in this work. The results are applicable to threshold Boolean functions, too.