Partitioned ROBDDs - A Compact, Canonical and Efficiently Manipulable Representation for Boolean Functions

Abstract

We present a new representation for Boolean functions called Partitioned-ROBDDs. In this representation we divide the Boolean space into `k' partitions and represent a function over each partition as a separate ROBDD. We show that partitioned-ROBDDs are canonical and can be efficiently manipulated. Further, they can be exponentially more compact than monolithic ROBDDs and even Free BDDs. Moreover, at any given time, only one partition needs to be manipulated which further increases the space efficiency.

In addition to showing the utility of partitioned-ROBDDs on special classes of functions, we provide automatic techniques for their construction. We show that for large circuits our techniques are more efficient in space as well as time over monolithic ROBDDs. Using these techniques, some complex industrial circuits could be verified for the first time.

For comments contact anarayan@ic.eecs.berkeley.edu