Analytical approach to VLSI logic synthesis

First, an analytical method for the minimization of multiple-valued input Boolean functions is investigated. The method is based on the reduction of the logic minimization problem to graph coloring. Implicants of a special type, called Minimally Split Product Implicants (MSI), are generated from a set of input cubes, and a graph which represents incompatibility relations between implicants is constructed from this set. Grouping of the MSI implicants into a minimum cardinality cover is then obtained by coloring the incompatibility graph of implicants. It can be shown that optimum results can be obtained with this set of implicants, provided that an optimum graph coloring is found. Second, a new theoretical formulation of the input encoding problem is presented, based on the concept of compatibility of dichotomies. The input encoding problem is shown to be equivalent to two-level logic minimization. Three possible techniques to solve the encoding problem are discussed, based on: (1) techniques borrowed from classical logic minimization (generation of prime dichotomies and solving the covering problem), (2) graph coloring applied to the incompatibility graph of dichotomies, and (3) extraction of essential prime dichotomies followed by graph coloring. For near-optimum results a powerful heuristic, based on an iterative improvement technique, has been developed. The new method can be applied to the input encoding of combinational logic as well as the state assignment of Finite State Machines (FSM) in both two-level and multi-level implementations. Third, a method for four-level optimization by Programmable Logic Array (PLA) decomposition is presented. A single two-level Boolean function is decomposed into two stages of cascaded PLA\u27s, such that the total area of all PLA\u27s is smaller than that of the original PLA. Finally, the concluding chapter suggests a number of important directions for research in sequential logic synthesis. The integration of logical and physical design steps in VLSI is emphasized. (Abstract shortened with permission of author.