McBOOLE: A New Procedure for Exact Logic Minimization

Abstract

A new logic minimization algorithm is presented. It finds a minimal cover for a multiple-output boolean function expressed as a list of cubes. A directed graph is used to speed up the selection of a minimal cover. Covering cycles are partitioned and branched independently to reduce greatly the branching depth. The resulting minimized list of cubes is guaranteed to be minimal in the sense that no cover with less cubes can exist. The don't care at output is handled properly. This algorithm was implemented in C language under UNIX BSD4.2. An extensive comparison with ESPRESSO IIC shows that the new algorithm is particularly attractive for functions with less than 20 input and 20 output variables.