REPRESENTING BOOLEAN FUNCTIONS WITH IF-THEN-ELSE DAGs
Kevin J. Karplus · 1988
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.