STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
In this paper, we introduce a class of Binary Decision Diagrams BDDs which we call Differential BDDs delta-BDDs, and two transformations over delta-BDDs, called Push-up up arrow and Delta delta transformations. In delta-BDDs and its derived classes such as up arrow delta-BDDs or delta up arrow delta-BDDs, in addition to the ordinary node-sharing in the normal Ordered Binary Decision Diagrams OBDDs, some isomorphic substructures are collapsed together forming an even more compact representation of boolean functions. The elimination of isomorphic substructures coincides with the repetitive occurrences of the same or similar small components in many applications of BDDs such as in the representation of hardware circuits. The reduction in the number of nodes, from OBDDs to delta-BDDs, is potentially exponential while boolean manipulations on delta-BDDs remain efficient.
- Computer Programming and Software