Algorithms for the minimization of binary and multiple-valued logic functions
Gerhard W. Dueck · Mspace (University of Manitoba) · 1988
The objective of logic minimization is to find a representation which lends itself to cost effective implementation. In this thesis new algorithms for the minimization of multiple-valued logic functions are presented. Any binary multiple-output problem can be transformed into a multiple-valued function. Therefore, the binary multiple-output problem can be solved by the techniques described in this thesis. Similarly, any multiple-valued multiple-output can be transformed into a single multiple-valued logic function. The thesis thus covers the complete spectrum of logic minimization. In some technologies, the truncated SUM operator is easier to implement than the more commonly used MAX operator. Due to the increased complexity associated with the truncated SUM operator, exact minimization is not feasible. A new direct cover algorithm for minimization with the truncated SUM is presented. Two heuristics are used by the proposed algorithm. First, the most isolated minterm is selected to be initially covered. Second, for each implicant which contains the chosen minterm the break count reduction is calculated. The implicant with the best break count reduction is chosen to be part of the solution. Directed search minimization integrates the choice of the minimal cover into the prime implicant generation process. An extension of the directed search algorithm to accommodate multiple-valued logic function is described. A new binary recursive consensus algorithm which starts with a sum-of-products expression is presented. The order in which product terms are generated is different from the traditional iterated consensus. In addition, information on the intersection between product terms is kept. These two changes facilitate the early detection of essential and pseudo-essential prime implicants. Moreover, the algorithm is adapted to handle multiple-valued logic functions. The algorithm combines the advantage of starting from a list of terms and detection of essential prime implicants while generating prime implicants. Finally, it is shown how the algorithms can be adapted to minimization with window literals. Window literals appear more frequently in the literature and are often easier to implement.