在電路結構記錄餘因數分解的二元決策圖建構法

Abstract

長久以來，為電路建構二元決策圖最大的問題在於使用的時間與空間成指數成長，雖然透過許多巧妙的方法與善用原始電路的資訊可減少計算過程之中所需用到的最大空間及計算時間，但是就理論上仍擺脫不了指數成長的範疇。此篇論文先提供一種方法，使得運算過程之中所需要使用的時間或空間能夠得到一個局部的最佳解，再結合了數種程式技巧及方法以求取中間較佳的平衡點。將原始電路以餘因數分解的方法逐步轉換成最終所需的二元決策圖並以ite結構做為轉換之中的媒介，另外以深度優先搜尋來保證過程之中所需額外使用的空間可以是O(N^2)，更進一步，混合使用深度優先搜尋與廣度優先搜尋將可以在一給定的使用空間中獲得更快的運算時間，最後，巧妙的使用雙向鍊結及遮罩將大輻改善計算餘因式分解時的搜尋空間並達到較佳的運行速度。

For a long time, the biggest problem on building BDD (binary decision diagram) is the complexity in time and space are exponential. Through many heuristics and the information from the original circuit, the peak memory usage and total operating time may be improved. However, the worst case is still in the exponential scope. This thesis combines several measures and translates the initial circuit into the final BDD structure progressively by using cofactor method and ITE (If-Then-Else) structure as the medium. Using the dfs (depth first search) concept the space complexity will be bounded in square of data size. Furthermore, mixing dfs and bfs (breadth first search) will get faster operating speed under a given bounded space. Lastly, carefully applying the ideas of double-link and mask would greatly reduce the search space in performing cofactor operations and reach the ideal effect.