Graph-Based Algorithms for Boolean Function Manipulation

CMU-CS-85-135

Randal E. Bryant

July 1985 oot This paper has been accepted for publication in IEEE Transactions on Computers . A preliminary version of this paper was presented under the title "Symbolic Manipulation of Boolean Functions Using a Graphical Representation" at the 22nd Design Automation Conference, Las Vegas, NV, June 1985.

In this paper we present a new data structure for representing Boolean functions and an associated set of manipulation algorithms. Functions are represented by directed, acyclic graphs in a manner similar to the representations introduced by Lee and Akers, but with further restrictions on the ordering of decision variables in the graph. Although a function requires, in the worst case, a graph of size exponential in the number of arguments, many of the functions encountered in typical applications have a more reasonable representation. Our algorithms have time complexity proportional to the sizes of the graphs being operated on, and hence are quite efficient as long as the graphs do no grow too large. We present experimental results form applying these algorithms to problems in logic design verification that demonstrate the practicality of our approach.

33 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]