Efficient implementation of an exact multiple-output boolean function minimization algorithm

Abstract

The performance of the Svoboda-Nadler-Vora algorithm for exact multiple-output boolean function minimization is studied and compared with a heuristic minimization method.

For this purpose, the algorithm has been implemented in optimized ANSI C code. This implementation introduces a new set of procedures to reduce the cost of prime implicant generation. The concept of weight as the number of 1 and don't care neighbors of a state is used to take advantage of the special cases when a state has only one neighbor or no neighbors at all. The cost of prime implicant generation is further reduced by using the fact that the input dependency of any given state is limited by which of its neighbors exist within an output that are 1 's or don't cares. A detailed example illustrates how the heuristic method can fail to find the absolute minimum of a boolean function.