Logic synthesis and optimization algorithms

As VLSI integration size and chip complexity keep increasing, logic design is becoming more complex and it must be automated. The increasing demand for ASIC (Application Specific Integrated Circuits) also needs design efficiency and cost effectiveness which can only be achieved by effective automatic logic synthesis tools. In this thesis, two important network realization means, PLA's and multi-level networks (i.e., random logic networks), are studied, and effective algorithms are developed for the use as automatic logic synthesis tools.For the design based on PLA's, an absolute PLA minimization algorithm, PMIN, is presented. PMIN can handle a much larger range of functions than previous absolute minimization algorithms because it incorporated new algorithms for prime implicant generation and the extraction of a minimal subset of prime implicants. Also, a heuristic input variable assignment algorithm for the design of decoded-PLA's using multi-input decoders is incorporated in PMIN, and experimental results show that significant saving in area can be achieved for many functions.For the design of multi-level networks, a synthesis and optimization algorithm, SYLON-DREAM, is presented, which includes algorithms for network design, area optimization and timing optimization. Extensive experimental results are shown to demonstrate the capabilities of these algorithms.U of I OnlyETDs are only available to UIUC Users without author permissio