This research is on converting a Boolean function circuit description into a circuit that implements the functions, meeting time and cost constraints. The approach is to use transformations of if-then-else DAG's in multi-level minimization. These are particularly attractive for representing Boolean functions because they can compactly express useful functions, such as arithmetic and parity functions, that require exponentially larger representations in the sum-of-products format. Preliminary studies indicate that even fairly crude transformations provide effective minimization. Research is on algorithms for: factoring, to reduce the complexity of expressions; sharing common sub- expressions to eliminate redundant circuitry; and using don't care information to handle partially specified functions. The proposed research is in an important area of automated design of IC chips, logic synthesis. The Principal Investigator is recognized as an expert researcher in this area, has a history of novel ideas, and the potential to continue producing good research. This research is important to our understanding of IC design theory and methods.
