Interleaving based variable ordering methods for ordered binary decision diagrams
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Ordered binary decision diagrams (OBDDs) are efficient representations of Boolean functions and have been widely used in various computer-aided design tools. Since the size of an OBDD depends on variable ordering, it is important to find a good variable order for the efficient manipulation of OBDDs. In particular, it is important to find the same good variable order for multiple functions, since multiple functions are handled at the same time in most computer-aided design tools. The paper describes new variable ordering algorithms for multiple output circuits. The new algorithms use variable interleaving, while conventional algorithms use variable appending. For some benchmark circuits, OBDDs have been successfully generated by using the new algorithms, while they have not been generated by using conventional algorithms. Consequently, the new variable ordering algorithms are effective and allow us to apply OBDD-based CAD tools to wider classes of circuits.Keywords
This publication has 9 references indexed in Scilit:
- Combinational profiles of sequential benchmark circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Logic verification using binary decision diagrams in a logic synthesis environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Functional approaches to generating orderings for efficient symbolic representationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Minimization of binary decision diagrams based on exchanges of variablesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On variable ordering of binary decision diagrams for the application of multi-level logic synthesisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient implementation of a BDD packagePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Shared binary decision diagram with attributed edges for efficient Boolean function manipulationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Variable ordering algorithms for ordered binary decision diagrams and their evaluationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986