Kevin Karplus
11/30/1988 09:00 AM
Computer Science
This article describes the use of binary decision diagrams (BDDs) and if-then-else DAGs for representing and manipulating Boolean functions. Two-cuts are defined for binary decision diagrams, and the relationship is exhibited between general if-then- else expressions and the two-cuts of a BDD for the same function. An algorithm for computing all two-cuts of a BDD in O(n2) time is given. A new canonical form for if-then-else DAGs, analogous to Bryant\'s canonical form for BDDs, is introduced. The canonical form is based on representing the lowest non-trivial two-cut in the corresponding BDD, while Bryant\'s canonical form represents the highest two-cut. Expressions in Bryant\'s canonical form or in the new canonical form are shown to be prime and irredundant. Some applications of if-then-else DAGs to multi-level logic minimization are given, and the Printform transformations for reducing the complexity of if-then-else DAGs are presented.
