Accession Number : ADA294746

Title :   Tools for Binary Decision Diagram Analysis.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Ang, Kwee H.

PDF Url : ADA294746

Report Date : MAR 1995

Pagination or Media Count : 91

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)

Descriptors :   *LOGIC CIRCUITS, *COMPUTER PROGRAM VERIFICATION, *CIRCUIT ANALYSIS, COMPUTER PROGRAM DOCUMENTATION, MATHEMATICAL MODELS, ALGORITHMS, OPTIMIZATION, COMPUTER AIDED DESIGN, THESES, NODES, VARIABLES, DECISION THEORY, SWITCHING, SPECIAL FUNCTIONS(MATHEMATICS), BREAKDOWN(ELECTRONIC THRESHOLD).

Subject Categories : Electricity and Magnetism
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE