- Author:
- Kevin Karplus
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.
Cited By
- Amarú L, Gaillardon P and De Micheli G BDS-MAJ Proceedings of the 50th Annual Design Automation Conference, (1-6)
- Martinelli A, Krenz R and Dubrova E Disjoint-support Boolean decomposition combining functional and structural methods Proceedings of the 2004 Asia and South Pacific Design Automation Conference, (597-599)
- Bengtsson T, Martinelli A and Dubrova E A BDD-based fast heuristic algorithm for disjoint decomposition Proceedings of the 2003 Asia and South Pacific Design Automation Conference, (191-196)
- Yang C, Ciesielski M and Singhal V BDS Proceedings of the 37th Annual Design Automation Conference, (92-97)
- Bertacco V and Damiani M The disjunctive decomposition of logic functions Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, (78-82)
Recommendations
Two-level logic minimization for low power
In this paper we present a complete Boolean method for reducing the power consumption in two-level combinational circuits. The two-level logic optimizer performs the logic minimization for low power targeting static PLA, general logic gates, and dynamic ...
Multi-level logic minimization using implicit don't cares
An approach is described for the minimization of multilevel logic circuits. A multilevel representation of a block of combinational logic is defined, called a Boolean network. A procedure is then proposed, called ESPRESSOMLD, to transform a given ...