
Accession Number : ADA324002
Title : Differential BDDs.
Descriptive Note : Research paper,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Anuchitanukul, Anuchit ; Manna, Zohar
PDF Url : ADA324002
Report Date : 09 SEP 1994
Pagination or Media Count : 11
Abstract : In this paper, we introduce a class of Binary Decision Diagrams (BDDs) which we call Differential BDDs (deltaBDDs), and two transformations over deltaBDDs, called Pushup (up arrow) and Delta (delta) transformations. In deltaBDDs and its derived classes such as up arrow deltaBDDs or delta up arrow deltaBDDs, in addition to the ordinary nodesharing 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 deltaBDDs, is potentially exponential while boolean manipulations on deltaBDDs remain efficient.
Descriptors : *STRUCTURED PROGRAMMING, ALGORITHMS, COMPUTER LOGIC, SYSTEMS ANALYSIS.
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE