Tools for binary decision diagram analysis
Loading...
Authors
Ang, Kwee Hua
Subjects
Advisors
Butler, Jon T.
Date of Issue
1995-03
Date
March 1995
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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.
Type
Thesis
Description
Series/Report No
Department
Electrical Engineering
Organization
Identifiers
NPS Report Number
Sponsors
Funder
NA
Format
81 p.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.