Differential BDDs.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 09, 1994
Accession Number
ADA324002

Entities

People

  • Anuchit Anuchitanukul
  • Zohar Manna

Organizations

  • Stanford University

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Automation
  • California
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Guarantees
  • Hash Tables
  • Polynomials
  • Scientific Research
  • Sequences
  • Standards
  • Switching
  • United States

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Electrochemical Surface Science
  • Graph Algorithms and Convex Optimization.