2-LEVEL MINIMIZATION OF MULTIVALUED FUNCTIONS WITH LARGE OFFSETS

Many problems that arise in the area of logic synthesis have been solv ed using two-level minimization of multivalued functions. A multivalue d function is used to abstract the problem such that its minimal two-l evel representation provides a solution to the problem. Therefore, an efficient two-level minimization method is very valuable. The approach es to two-level logic minimization can be classified into two groups: those that use tautology for expansion of cubes (product terms) and th ose that use the offset. Tautology-based schemes are generally slower and often give somewhat inferior results because of a limited global p icture 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 w ay 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 unreason ably large. It was recently shown that for the minimization of such bi nary-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 m ultivalued reduced offsets provides the same flexibility that is avail able with the use of the offset. Offset-based minimization of multival ued functions with large offsets often takes long computation time and requires very large memory and sometimes is not possible within reaso nable time and memory. Such functions can be minimized effectively usi ng reduced offsets.