Boolean factorization using multiple-valued minimization

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 a = 0 and a a = a. Common factors across a set of Boolean functions can be identi ed 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.