Construct Binary Decision Diagram by Cofactor on Circuit Structure by Cofactor on Circuit Structure
Date Issued
2007
Date
2007
Author(s)
Lin, Tsung-Mao
DOI
en-US
Abstract
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.
Subjects
二元決策圖
餘因式分解
正規驗證
BDD
cofactor
verification
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-R93921106-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):e5c20eca640fc96a50efa19d9572c1c5