Hybrid Decision Diagrams. Overcoming the Limitations of MTBDDs and BMDs,
Abstract
Functions that map boolean vectors into the integers are important for the design and verification of arithmetic circuits. MTBDDs and BMDs have been proposed for representing this class of functions. We discuss the relationship between these methods and describe a generalization called hybrid decision diagrams which is often much more concise. We show how to implement arithemetic operations efficiently for hybrid decision diagrams. In practice, this is one of the main limitations of BMDs since performing arithmetic operations on functions expressed in this notation can be very expensive. In order to extend symbolic model checking algorithms to handle arithmetic properties, it is essential to be able to compute the BDD for the set of variable assignments that satisfy an arithmetic relation. Bryant and Chen do not provide an algorithm for this. In our paper, we give an efficient algorithm for this purpose. Moreover, we prove that for the class of linear expressions, the time complexity of our algorithm is linear in the number of variables. Our techniques for handling arithmetic operations and relations are used intensively in the verification of an SRT division algorithm similar to the one that is used in the Pentium. (KAR) P. 3
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1995
- Accession Number
- ADA296684
Entities
People
- B. Clarke
- M. Fujita
- Xingchen Zhao
Organizations
- Carnegie Mellon University