Multilevel logic synthesis for arithmetic functions

TitleMultilevel logic synthesis for arithmetic functions
Publication TypeConference Paper
Year of Publication1996
AuthorsTsai, C-C, Marek-Sadowska, M
Conference NameDesign Automation Conference Proceedings 1996, 33rd
Date Publishedjun,
Keywordsadders, algebraic factorization, AND/XOR representations, area improvement, arithmetic functions, Boolean functions, circuit CAD, digital arithmetic, integrated circuit design, logic CAD, multilevel logic synthesis, multilevel logic synthesis method, multilevel networks, multiplying circuits, multivalued logic circuits, n-bit adder, natural representations, power consumption, redundancy removal process, testability
AbstractThe arithmetic functions, as a subclass of Boolean functions, have very compact descriptions in the AND and XOR operators. Any n-bit adder is a prime example. This paper presents a multilevel logic synthesis method which is particularly suited for arithmetic functions and utilizes their natural representations in the field GF(2). Algebraic factorization is performed to reduce the literal count. A direct translation of the AND/XOR representations of arithmetic functions into multilevel networks often results in excessive area, mainly due to the large area cost of XOR gates. We present a process of redundancy removal which reduces many XOR gates to single AND or OR gates without altering the functional behavior of the network. The redundancy removal process requires only to simulate a small and decidable set of primary input patterns. Preliminary results show that our method produces circuits, before and after technology mapping, with area improvement averaging 17% when compared to Berkeley SIS 1.2. The run time is reduced by at least 50%. The resulting circuits also have good testability and power consumption properties