Two-Level Minimization of Multivalued Functions with Large Offsets

Abstract

Many problems that arise in the area of logic synthesis have been solved using two-level minimization of multivalued functions. A multivalued function is used to abstract the problem such that its minimal two-level representation provides a solution to the problem. Therefore, an efficient two-level minimization method is very valuable. The approaches to two-level logic minimization can be classified into two groups: those that use tautology for expansion of cubes (product terms) and those that use the offset. Tautology-based schemes are generally slower and often give somewhat inferior results because of a limited global picture of the way in which the cube can be expanded. If the offset is used, usually the expansion can be done quickly and in a more global way because it is easier to see effective directions of expansion. The problem with this approach is that there are many functions that have a reasonable size onset and don’t care set, but the offset is unreasonably large. It was recently shown that for the minimization of such binary-valued functions (a special case of multivalued functions), a new approach using reduced offsets, provides the same global picture and is much faster. In this paper, we extend the theory of reduced offsets to logic functions with multivalued inputs. We show that the use of multivalued reduced offsets provides the same flexibility that is available with the use of the offset. Offset-based minimization of multivalued functions with large offsets often takes long computation time and requires very large memory and sometimes is not possible within reasonable time and memory. Such functions can be minimized effectively using reduced offsets. © 1993 IEEE