EXPLOITING ALL SIMPLE DISJUNCTIVE DECOMPOSITIONS OF BOOLEAN FUNCTIONS BASED ON ALGEBRAIC FACTORIZATION


Abstract

Finding disjunctive decomposition is an important technique to realize optimal logic circuits. This talk presents a method to exploit all simple disjunctive decompositions, by generating irredundant sum-of-products forms and applying algebraic factorization. We proved that all existing simple disjunctive decompositions can be found and carried out in the result of our method. BDD and ZBDD-based symbolic manipulation techniques support fast execution of this method for large-scale functions. Our result is not only practically but also theoretically important since it clarifies a relationship between algebraic factorization and functional decomposition.


Contact 
©2002-2018 U.C. Regents