Minimization of binary decision diagrams based on exchanges of variables
- 10 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The authors present a novel exact algorithm and gradual improvement methods for minimizing binary decision diagrams (BDDs). In the exact minimization algorithm, the optimum order is searched by the exchanges of variables of BDDs based on the framework of the algorithm of S.J. Friedman and K.J. Supowit (1990). The use of the BDD representation of a given function and intermediate functions makes it possible to produce pruning into the method, which drastically reduces the computation cost. The authors succeeded in minimizing a 17-variable function by the use of the BDD representation of intermediate functions and the introduction of pruning. They also propose a greedy method and a simulated annealing method based on exchanges of two arbitrary variables, and a greedy method based on exchanges of adjacent m variables for m=3 and 4.Keywords
This publication has 8 references indexed in Scilit:
- Logic verification using binary decision diagrams in a logic synthesis environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Evaluation and improvement of Boolean comparison method based on binary decision diagramsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- 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
- Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagramsPublished by Association for Computing Machinery (ACM) ,1991
- Finding the optimal variable ordering for binary decision diagramsIEEE Transactions on Computers, 1990
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986