Kevin Karplus
11/30/1988 09:00 AM
Computer Science
This article describes the use of if-then-else DAGs for multi-level logic minimization. A new canonical form for if-then-else DAGs, analogous to Bryant's canonical form for binary decision diagrams (BDDs), is introduced. Two-cuts are defined for binary decision diagrams, and a relationship is exhibited between general if-then-else expressions and the two-cuts of a BDD for the same function. The canonical form is based on representing the lowest non-trivial two-cut in the corresponding BDD, instead of the highest two-cut, as in Bryant's canonical form. The definitions of prime and irredundant expressions are extended to if-then-else DAGs. Expressions in Bryant's canonical form or in the new canonical form can be shown to be prime and irredundant. Objective functions for minimization are discussed, and estimators for predicting the area and delay of the circuit produces after technology mapping are proposed. A brief discussion of methods for applying don't-care information and for factoring expressions is included.
