• 作者： 蔡?園; 蕭培墉
• 作者服務機構： 交通大學資訊科學研究所
• 中文摘要： 由於約減式排序二元決策圖的變數排序對其大小有極大的影響，所以對於約減式排序二元決策圖的變數排序研究已經有許多很有效率的方法被探討出來，例如最深搜尋法已經在線路式邏輯函數中得到非常不錯的結果，但由於可程式邏輯函數的輸入變數位置對最深搜尋法的結果有極大的影響，亦連帶的影響了約減式排序二元決策圖的大小，所以在此論文中針對此一問題來找尋一個有效率的解決方法。 此方法是依據對各個輸入變數先預知其在約減式排序二元決策圖中被設定後所餘下的變數個數來做決定，故此被稱為前視式加權設定法。另對於多輸出的可程式邏輯函數，對每個輸出函數中每個乘積項的平均變數個數亦成為新的加權依據。在對標準可程式邏輯函數的實驗中，我們的方法不僅不受輸入變數位置變化的影響，同時在約減式排序二元決策圖大小的比較上，可較以最深搜尋法所得的平均值有9％的約減，並比最大變數優先法有6.7％的節省，足見此法的效率。
• 英文摘要： The ROBDD (Reduced-Ordered Binary Decision Diagram) is a canonical and efficient expressionfor Boolean functions, but the size of the ROBDD is directly related to input variable ordering. For anetlist expression of Boolean functions, DFS (Depth-First-Search) achieves very efficient variable orderingresults. However, the ROBDD of PLA-based Boolean functions is directly influenced by the positionof the primary inputs if the DFS method is applied to determine the variable ordering In this paper,we propose a look-ahead weight assignment method to select a 'good’variable ordering that can beindependent of the locative exchange of inputs This heuristic method deals with the literals remainingin the Boolean function whenever a variable is assigned as true and false. For multi-output Booleanfunctions, each separated single output Boolean subfunction is considered. The results of our experimentshave been compared to the average size of the ROBDD, which, in turn,was created by using the DFSmethod with different input variable allocations Further comparison with the dynamic weight assignmentmethod is also given. For PLA circuits of the ISCAS benchmark, our method is not only independentof the location of the input variables,but also achieves 9% and 6 7% improvement with the above bothpopular methods
• 中文關鍵字： ROBDD; DFS; cynamic weight assignment; look-ahead weight assignment
• 英文關鍵字： --