Extends the theory of reduced offsets to logic functions with multivalued inputs. The authors 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.>

A scheme for programmable logic array (PLA) decomposition that consists of one level of PLAs followed by a second level of simple two-input logic gates is presented. The propagation delay is therefore the sum of the delay through one level of PLA and one level of two-input gates. Since the delay through a two-input gate is significantly less than that through a PLA, the timing performance of the new scheme is generally superior to those of earlier PLA decomposition schemes. The sizes of the PLAs used depend on the choice of the two-input gates. An algorithm is presented that chooses the functionality of the gates such that the areas of the first-level PLAs are minimized, further improving performance. The new decomposition scheme was developed for the automatic programming of a programmable logic device (PLD) which had basically a three level architecture. The functional unit for such a PLD is described and the application of the algorithm to the programming of these functional units is discussed. Experimental results show that the new scheme significantly reduces the area over the single PLA implementation.>

A modified approach to two-level logic minimization is described 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.>

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 reasonable size 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. In this paper we extend reduced offsets to logic functions with multi-valued inputs.

Two methods for two-level logic minimization tuned to a multilevel network environment are discussed. Each produces results superior to ESPRESSO. The tautology-based method is very simple and can be coded in less than 700 lines of C language using the existing data structures, and some routines in ESPRESSO. The reduced offset modification is somewhat more complicated but gives the best results. This algorithm has been incorporated into MISII. The authors have demonstrated that a simple filter applied to the don't care set in this application can be extremely effective.>

The minimization of Boolean functions is usually aimed at obtaining a minimum sum-of-products representation, measured in terms of the number of product terms produced. In multilevel logic, however, a better objective function is a minimized factored form. Traditionally, logic functions have been factored by using algebraic techniques on a minimized sum-of-products. Algebraic factorization techniques explore only part of the solution space. A technique for factoring based on Boolean operations is presented. This technique often leads to a better factored form for a logic function. The algorithm uses the Boolean operations which are the basis of the two-level minimizer ESPRESSO. The technique has been implemented in the multilevel logic minimization program MIS. Some results of Boolean factorization of individual nodes in multilevel networks are presented and then compared with other factoring methods in MIS.>

A methodology in which it is not necessary to compute the entire offset is presented, that still provides a global picture. This scheme has been implemented in ESPRESSO with an interface to the multilevel minimization environment MIS. Initial results show that for functions for which the ratio of the size of the cover to the size of the don't care set is small, the new approach is much faster. The initial interest was to use this mainly in a multilevel logic synthesis system where the desired don't care sets are typically large. Some results in this environment are given, and the new scheme is compared with ESPRESSO.>