Report Number: CSL-TR-93-584
Institution: Stanford University, Computer Systems Laboratory
Title: Optimization of Combinational Logic Circuits Based on Compatible Gates
Author: Damiani, Maurizio
Author: Yang, Jerry Chih-Yuan
Author: DeMicheli, Giovanni
Date: June 1993
Abstract: This paper presents a set of new techniques for the optimization of multiple-level combinational Boolean networks. We describe first a technique based upon the selection of appropriate "multiple-output" subnetworks (consisting of so-called "compatible gates" whose local functions can be optimized simultaneously. We then generalize the method to larger and more arbitrary subsets of gates. Because simultaneous optimization of local functions can take place, our methods are more powerful and general than Boolean optimization methods using "don't cares", where only single-gate optimization can be performed. In addition, our methods represent a more efficient alternative to optimization procedures based on Boolean relations because the problem can be modeled by a "unate" covering problem instead of the more difficult "binate" covering problem. The method is implemented in program ACHILLES and compares favorably to SIS .