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 (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.

Descriptors :   *STRUCTURED PROGRAMMING, ALGORITHMS, COMPUTER LOGIC, SYSTEMS ANALYSIS.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE