Tools for Binary Decision Diagram Analysis.

Abstract

The Binary Decision Diagram (BDD) is a very useful representation in the design and verification of switching functions. This is due to to its compactness, where size is measured by the number of nodes. In the implementation of logic circuits, connection of sub-functions is by means of pass transistors. The delay time for the interconnections is often larger than the delay of the decision logic. For that reason, crossings are often more expensive than logic. Planar Binary Decision Diagrams are therefore desirable in implementing logic circuits. This paper presents a method for finding a planar Ordered Binary Decision Diagram (OBDD) for threshold functions. The program that implements the algorithm is written in Borland C++. A special case of Fibonacci threshold function having up to 9 variables is analyzed. It is shown that Fibonacci functions having up to 9 variables have planar OBDD. With this program, the characteristics of other threshold functions are developed. (AN)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1995
Accession Number
ADA294746

Entities

People

  • Kwee H. Ang

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Circuits
  • Computer Programs
  • Computer Science
  • Computers
  • Crossings
  • Electrical Engineering
  • Engineering
  • Logic
  • Logic Gates
  • Mathematics
  • Networks
  • Numbers
  • Permutations
  • Switching
  • Trees (Data Structures)

Readers

  • Computer Programming and Software Development.
  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.