Boolean factorization using multiple-valued minimization
Stan Liao, Srinivas Devadas, Abhijit Ghosh · 1993
We show that the problem of factoring a sum-ofproducts representation of a logic function can be transformed into one of multiple-valued prime generation followed by branch-and-bound covering. We give a factorization method that generates potential Boolean factors by generating the primes of a multiple-valued function with an associated don't-care set. A covering problem is solved wherein a set of primes with minimal cost is selected to obtain a Boolean factorization. This method can exploit Boolean identities in factorization such as a 1 a = 0 and a 1 a = a. Common factors across a set of Boolean functions can be identified by using multiple-output prime generation and covering. We show how all the kernels of an expression can be generated by generating the primes of a multiple-valued function. A covering step can be used to arrive at an algebraic factorization. 1 Introduction Multilevel logic synthesis has been an active research area in the past two decades [4]. Several programs ...