自二元決策圖﹙Binary Decision Diagram﹚用來表示布林函數的概念和其相關運算的演算法被提出以來，就獲得許多研究者的採用。要找出表達函數的最佳變數順序，計算之時間複雜度相當高，於是在過去的十年間，BDD最小化的問題受到許多人的討論和研究。雖然如此，數十到數百個輸入的電路至今仍無實用的演算法能夠求出更為精確的解。本論文針對這樣的問題，以亂數演算法，將過去只能求出近似解的篩選﹙sifting﹚演算法的計算能力，提升到相當於求出精確最佳解演算法一樣；而且更容易平行化，以符合更大型電路求解的需求。在本論文中，benchmark LGSynth91中輸入數小於500的電路除了C6288.blif之外，都找到了相當好的解，形成最小BDD的變數順序在附錄中一一列出，數據顯示，這些BDD的大小都比以往所知的小，計算時間也並未因為使用亂數演算法而有不穩定的現象，說明我們所提出的新方法有極佳的效能。 Binary Decision Diagram (BDD) is a data structure for the representation and manipulation of Boolean functions, which is applied in many areas. However, finding the optimal variable ordering of BDD seems to be intractable. Though numerous algorithms for BDD minimization are proposed in the last decade, no feasible one is able to find a good variable ordering for Boolean functions with up to hundreds variables. In this thesis we present a randomized algorithm to minimize BDD. With the help of our new approach, Sifting algorithm works as well as an exact algorithm. The new approach can be parallelized easily to meet the need of complex function minimization. In the thesis, LGSynth91 circuits with less than 500 variables are all minimized with very good results, except only C6288.blif. The better variable orderings of these benchmark circuits are listed in Appendix. Experimental results show that the BDDs' sizes are smaller than previous known results, and it's computing time is very small and very stable. It turns out that this randomized algorithm is a robust method for BDD minimization.

Binary Decision Diagram (BDD) is a data structure for the representation and
manipulation of Boolean functions, which is applied in many areas. However,
finding the optimal variable ordering of BDD seems to be intractable.
Though numerous algorithms for BDD minimization are proposed in the last
decade, no feasible one is able to find a good variable ordering for Boolean
functions with up to hundreds variables. In this thesis we present a
randomized algorithm to minimize BDD. With the help of our new approach,
Sifting algorithm works as well as an exact algorithm. The new approach can be
parallelized easily to meet the need of complex function minimization.
In the thesis, LGSynth91 circuits with less than 500 variables are all
minimized with very good results, except only C6288.blif. The better variable
orderings of these benchmark circuits are listed in Appendix. Experimental
results show that the BDDs' sizes are smaller than previous known results, and
it's computing time is very small and very stable. It turns out that this
randomized algorithm is a robust method for BDD minimization.

1. R. E. Bryant, “Graph-based algorithms for Boolean function manipulation,”
IEEE Trans. Comput., vol. 35, pp. 677-691, Aug. 1986.
2. S. J. Friedman and K. J. Supowit, “Finding the optimal variable ordering
for binary decision diagrams,” IEEE Trans. Comput., pp. 710-713, May 1990.
3. N. Ishiura, H. Sawada, and S. Yajima, “Minimization of binary decision
diagrams based on exchange of variables,” in Proc. Int. Conf. Computer-Aided
Design, pp. 472-475, Nov. 1991.
4. R. Rudell, “Dynamic variable ordering for ordered binary decision diagrams,
” Int. Conf. Computer-Aided Design, pp. 42-47, 1993.
5. S.-W. Jeong, T.-S. Kim, and F. Somenzi, “An efficient method for optimal
BDD ordering computation,” in Proc. Int. Conf. VLSI and CAD, 1993.
6. S. Panda and F. Somenzi, “Who are the variables in your neighborhood,” in
Int. Conf. Computer-Aided Design, pp. 74-77, 1995.
7. B. Bolling, M. Löbbing, and I. Wegener, “On the effect of local
changes in the variable ordering of ordered decision diagrams,” Inform.
Processing Lett., vol. 59, pp. 233-239, Oct. 1996.
8. B. Bolling, I. Wegener, “Improving the variable ordering of OBDDs is NP-
complete,” IEEE Trans. Computer., vol. 45, pp 993-1002, Sep. 1996.
9. R. Drechsler, W. Günther, and F. Somenzi, “Using lower bounds during
dynamic BDD minimization,” IEEE Trans. Computer-Aided Designs, vol. 20, pp.
51-57, Jan. 2001.
10. R. Drechsler, N. Drechsler, and W. Günther, “Fast exact minimization
of BDDs,” IEEE Trans. Computer-Aided Designs, vol. 19, pp. 384-389, Mar. 2000.
11. C. Scholl, D. Möller, and P. Molitor, “BDD minimization Using
Symmetries,” IEEE Trans. Computer-Aided Designs of Integrated Circuits and
Systems, vol. 18, no 2. Feb. 1999.
12. R. K. Brayton, G. D. Hachtel, C. T. McMullen and A. L. Sangiovanni-
Vincentelli, "Logic Minimization Algorithms for VLSI Synthesis," Kluwer
Academic Publishers, Boston. 1984.
13. D. Möller and R. Drechsler, “Symmetry based variable ordering for
ROBDD’s,” in Proc. IFIP Workshop on Logic and Architecture Synthesis, pp. 47-
53, Dec. 1994.
14. R. Drechsler and B. Becker, “Binary Decision Diagrams – Theory and
Implementation.” Kluwer Acadmic Publishers, 1998.
15. R. E. Brant, “On the complexity of VLSI implementations and graph
representations of Boolean functions with application to integer multiplication
,” IEEE Trans. on Comp., vol. 40, pp. 205-213, 1991.
16. W. Günther and R. Drechsler, “Minimization of Free BDDs,” IEEE
Trans. on Comp., vol. , pp. 323-326, 1999.
17. F. M. Brown, "Boolean Reasoning," Kluwer Academic Publishers, Boston. 1990.
18. R. E. Brant, “Symbolic Boolean Manipulation with Ordered Binary-Decision
Diagrams,” ACM, Comp. Surveys, vol. 24, 293-318, 1992.
19. J. C. Muzio, T. C. Wesselkamper, “Multiple-Valued Switching Theory,”
Adam Hilger Ltd Bristol and Boston, 1986.
20. C. E. Shannon, “A symbolic analysis of relay and switching circuits,”
Trans, AIEE, vol. 57, pp. 713-723, 1938.
21. U. Kebschull, E. Schubert and W. Rosenstiel, “Multilevel logic synthesis
based on functional decision diagrams,” Proc. European Design Automation
Conf. pp 43-47, 1992.
22. F. Somenzi, CUDD: CU Decision Diagram Package – Release 2.3.1 Technical
report, Dept. of Electrical and Computer Engineering, University of Colorado,
Boulder, Colorado, Feb. 2001.
23. 網站 http://vlsi.colorado.edu/~fabio