Efficient variable ordering and partial representation algorithm
Jawahar Jain, Dinos Moundanos, James R. Bitner et al. · International Conference on VLSI Design · 2002
In this paper we introduce some new methods for constructing Ordered Partial Decision Diagrams (OPDDs), The algorithms are effective in capturing a significant fraction of a given function's truth table using only a very small space. Using such data structures the importance of a variable in a Boolean function can be computed. Such methods can easily be used for computing effective variable orders to construct BDDs. The measures of a variable's importance are based on information-theoretic criteria, and require computation of the entropy of a variable for a given function. We have found that entropy measures can be quite efficient in distinguishing the importance of variables, and at times provide very effective variable order. The results show an encouraging approach towards the understanding and the solution of this well known problem.
Cited by 12 works. doi:10.1109/icvd.1995.512082
Authors
References
- Graph-Based Algorithms for Boolean Function Manipulation
- Personal Communication
- Logic verification using binary decision diagrams in a logic synthesis environment
- Decision Trees and Diagrams
- Evaluation and improvement of Boolean comparison method based on binary decision diagrams
- Dynamic variable ordering for ordered binary decision diagrams
- Dynamic variable ordering for ordered binary decision diagrams
- On variable ordering of binary decision diagrams for the application of multi-level logic synthesis
- On variable ordering of binary decision diagrams for the application of multi-level logic synthesis
- An Information Theoretic Approach to Digital Fault Testing