BDD-based engineering-change logic synthesis

The logic design for today's VLSI systems is getting increasingly complicated due to sharp increase in the number and speed of circuit components packed in a single IC-chip. As the MOS technology continues to be dominant, CAD methods that support designing of MOS networks with minimum design-layout cycles has become a necessity. The technology-dependent approach for logic design can contribute to such CAD methods. Among others, it enables engineering changes, which arise due to changes of design specifications and/or errors discovered later, to be made in one part of a laid-out circuit while keeping other parts intact. In this thesis, we present efficient algorithms based on binary decision diagrams (BDDs) to support technology-dependent synthesis of MOS networks.; We first study the efficient detection of unateness of functions represented by BDDs. The focus is on negative functions and their BDDs because a MOS gate realizes a negative function. Several efficient filters and algorithms that use them to detect negative functions are presented. Further, an efficient algorithm for classifying each variable of a BDD as positive, negative or binate is presented. Experimental results show that our algorithms are very efficient compared to the simple methods.; Next, the problem of covering an incompletely-specified negative function by a completely-specified negative function efficiently is investigated. This problem arises during the synthesis of MOS networks. A necessary step towards solving this is to obtain irredundant disjunctive and conjunctive forms, both of which are negative. We use BDDs for efficient computation of these expressions. Our algorithm is based on computing the maximum and minimum vectors of a BDD. Previous algorithms for this problem were based on inefficient enumeration of input vectors. The number of vectors to be enumerated is reduced to a small number in our method. Experimental results show our new covering method is quite fast and produces reasonably good results.