Reduced offsets for two-level multi-valued logic minimization

Abstract

The approaches to two-level logic minimization can be classified into two groups: those that use tautology for expansion of cubes 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 reasonably sized onset and don't care set, but the offset is unreasonably large. It was recently shown that for the minimization of such Boolean functions, a new approach using reduced offsets provides the same global picture and can be computed much faster. The authors extend reduced offsets to logic functions with multivalued inputs.