Factoring logic functions using graph partitioning
Martin Charles Golumbic, Aviad Mintz · 1999
Algorithmic logic synthesis is usually carried out in two stages, the independent stage where logic minimization is performed on the Boolean equations with no regard to physical properties and the dependent stage where mapping to a physical cell library is done. The independent stage includes logic operations like Decomposition, Extraction, Factoring, Substitution and Elimi-nation. These operations are done with some kind of division (boolean, algebraic), with the goal being to obtain a logically equivalent factored form which minimizes the number of liter-als. In this paper, we present an algorithm for factoring that uses graph partitioning rather than division. Central to our approach is to combine this with the use of special classes of boolean func-tions, such as read-once functions, to devise new combinatorial algorithms for logic minimization. Our method has been im-plemented in the SIS environment, and an empirical evaluation indicates that we usually get significantly better results than al-gebraic factoring and are quite competitive with boolean factor-ing but with lower computation costs. 1