Lexicographical expressions of Boolean functions with application to multilevel synthesis

This paper proposes a new type of expression for Boolean functions called lexicographical expressions. The basic idea is to impose an input ordering for factoring logical expressions. Several algebraic properties are presented and relations with classical algebraic theory are established. The main result is that all elementary factorizations defined by (Cokernel, Kernel) pairs “compatible” with an input order are all “algebraically compatible,” i.e., are all parts of a single factorization of the function. Thus for a given input order a unique factorization is defined. This leads to fast division procedures. Basic techniques for obtaining lexicographical factorizations are presented. First, a precedence matrix and an updating procedure are defined and used later to select an input order and a corresponding compatible factorization. Second, a factorization technique respecting a fixed order is detailed. This method is then applied to multilevel synthesis using standard cells which was the original motivation of this work. The goal is to reduce wiring complexity. A lexicographical factorization leads to a wiring area reduction due to the structuring of the logic into layers in which the inputs enter the layout in the order given by the factorization. Experimental results comparing this approach to classical ones are given. These results include routing ratio measurements, routing structure observation, global area measurement and critical path estimation. All these results are analyzed after place and route, using an industrial tool (COMPASS Design Automation tool)