Report Number: CS-TR-94-1525
Institution: Stanford University, Department of Computer Science
Title: Differential BDDs
Author: Anuchitanukul, Anuchit
Author: Manna, Z ohar
Date: September 1994
Abstract: In this paper, we introduce a class of Binary Decision Diagrams (BDDs) which we call Differential BDDs (DBDDs), and two transformations over DBDDs, called Push-up and Delta transformations. In DBDDs and its derived classes such as Push-up DBDDs or Delta DBDDs, 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 DBDDs, is potentially exponential while boolean manipulations on DBDDs remain efficient.
http://i.stanford.edu/pub/cstr/reports/cs/tr/94/1525/CS-TR-94-1525.pdf