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.