| 題名: | BDD最小化問題之改良演算法 |
| 作者: | 林順喜 魏君任 |
| 期刊名/會議名稱: | 2001 NCS會議 |
| 摘要: | 自二元決策圖﹙Binary Decision Diagram﹚[1]用來表示布林函數的概念和其相關運算的演算法被提出以來，就獲得許多研究者的採用。然而要找出表達函數的最佳變數順序，計算複雜度相當高[9]，於是在過去的十年間，BDD最小化的問題受到許多人的討論和研究。雖然如此，數十到數百個輸入的電路至今仍無實用的演算法能夠求出更為精確的解。本論文針對這樣的問題，以亂數演算法，將過去只能求出近似解的篩選﹙sifting﹚演算法[3]的計算能力，提升到相當於求出精確最佳解演算法一樣，效能上也有極佳的表現；benchmark LGSynth91中輸入數小於500以下的電路，除了C6288.blif以外，都已經找到了很好的解。而我們提出的新方法更容易平行化，以符合更大型電路求解的需求。 關鍵詞：Minimization, Binary Decision Diagram, Randomized Algorithm |
| 日期: | 2006-10-16T05:38:14Z |
| 分類: | 2001年 NCS 全國計算機會議 |
文件中的檔案：
| 檔案 | 描述 | 大小 | 格式 | |
|---|---|---|---|---|
| ce07ncs002001000018.pdf | 868.79 kB | Adobe PDF | 檢視/開啟 |
在 DSpace 系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。