New heuristics for the exact minimization of logic functions

For the exact two-level minimization of logic functions, the most efficient implementation currently uses the Quine-McCluskey procedure. The authors present a modified bounding operation which improves the efficiency of the branch-and-bound algorithm. The key to this operation is the development of heuristics which allow a branch to be bounded by smaller lower bound values as well as to generate the minimum cover without having to visit the leaves of the search tree. The search space of the branch-and-bound algorithm is greatly reduced by these heuristics. Results from minimizing functions from the Berkeley test set are also presented.<>