Reduced Offsets for Minimization of Binary-Valued Functions

Abstract

The approaches to two-level logic minimization can be classified into two groups: Those that use tautology for expansion of cubes and others that use the offset. Tautology-based schemes are generally slow and do not obtain good expansion of cubes because they provide only a limited global picture of the way in which cubes can be expanded. If the offset is used, usually the expansion can be done quickly and in a more global way because it is easy to see directions of expansion that do not intersect the offset. The problem with this approach is that there are many functions that have a reasonable size representation for the onset and the don't care set, but the offset is unreasonably large. The offset usually has to be obtained by complementing the union of the onset and the don't care set. A modified approach is described in this paper which obviates the need to compute the offset; yet provides the same global picture available with the offset. This approach is based on a new concept called the reduced offset. It is shown that reduced offsets can be computed without using the offset. This scheme has been implemented in ESPRESSO with an interface to the multilevel minimization environment MIS where it is used to minimize individual nodes (representing two-level functions with single outputs) in multilevel networks. Such functions usually have very large offsets because of a large number of variables in their don't care sets. The modified approach is up to 8.5 times faster than ESPRESSO on a set of benchmark examples. © 1991 IEEE