請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/29732
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 黃鐘揚 | |
dc.contributor.author | Tsung-Mao Lin | en |
dc.contributor.author | 林宗茂 | zh_TW |
dc.date.accessioned | 2021-06-13T01:16:38Z | - |
dc.date.available | 2007-07-23 | |
dc.date.copyright | 2007-07-23 | |
dc.date.issued | 2007 | |
dc.date.submitted | 2007-07-19 | |
dc.identifier.citation | [1] Radomir S. Stankovic, Tsutomu Sasao: Decision Diagrams for Discrete Functions: Classification and Unified Interpretation. ASP-DAC 1998: 439-446
[2] K. S. Brace, R. L. Rudell, and R. E. Bryant. Efficient implementation of a BDD package. In Proceedings of the 27th Design Automation Conference, pages 40-45, Orlando, FL, June 1990. [3] Henrik Reif Anderson, “An Introduction to Binary Decision Diagrams” [4] MINCE: A Static Global Variable-Ordering Heuristic for SAT Search and BDD Manipulation F. Aloul, I. Markov, and K. Sakallah Journal of Universal Computer Science (JUCS), 10(12), pp. 1562-1596, December 2004 [5] O. Coudert, C. Berthet, and J. C. Madre. Verification of sequential machines using Boolean functional vectors. In L. Claesen, editor, Proceedings IFIP International Workshop on Applied Formal Methods for Correct VLSI Design, pages 111–128, Leuven, Belgium, November 1989. [6] In-Ho Moon, To Split or to Conjoin: The Question in Image Computation [7] Partial Binary Decision Diagrams Whitney J. Townsend and Mitchell A. Thornton 34th IEEE Southeastern Symposium on System Theory pp. 422-425, Huntsville, AL, March 18-19, 2002 [8] M. Fujita, P. McGeer, and J.-Y. Yang, “Multi-terminal Binary Decision Diagrams: An efficient data structure for matrix representation,” Formal Methods in System Design, vol. 10, no. 2/3, pp. 149–169, April/May 1997. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/29732 | - |
dc.description.abstract | 長久以來,為電路建構二元決策圖最大的問題在於使用的時間與空間成指數成長,雖然透過許多巧妙的方法與善用原始電路的資訊可減少計算過程之中所需用到的最大空間及計算時間,但是就理論上仍擺脫不了指數成長的範疇。此篇論文先提供一種方法,使得運算過程之中所需要使用的時間或空間能夠得到一個局部的最佳解,再結合了數種程式技巧及方法以求取中間較佳的平衡點。將原始電路以餘因數分解的方法逐步轉換成最終所需的二元決策圖並以ite結構做為轉換之中的媒介,另外以深度優先搜尋來保證過程之中所需額外使用的空間可以是O(N^2),更進一步,混合使用深度優先搜尋與廣度優先搜尋將可以在一給定的使用空間中獲得更快的運算時間,最後,巧妙的使用雙向鍊結及遮罩將大輻改善計算餘因式分解時的搜尋空間並達到較佳的運行速度。 | zh_TW |
dc.description.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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T01:16:38Z (GMT). No. of bitstreams: 1 ntu-96-R93921106-1.pdf: 1540240 bytes, checksum: 2a3c51109541f527b1e84b4488583bc1 (MD5) Previous issue date: 2007 | en |
dc.description.tableofcontents | 摘要..................................................i
Abstract..............................................ii Acknowledgements......................................iii List of Tables........................................vi List of Figures.......................................v Chapter 1 Introduction................................1 Chatter 2 Basic Ideas.................................2 Chatter 3 Algorithm...................................4 3.1 Overview of the Algorithm.......................4 3.2 Circuit in ITE Structure........................5 3.3 Data Structure..................................7 3.4 BDD Construction Main Flow......................9 3.5 BDD Construction by Cofactors...................11 Chatter 4 Experimental Result.........................19 Chatter 5 Future Work.................................25 Reference.............................................26 | |
dc.language.iso | en | |
dc.title | 在電路結構記錄餘因數分解的二元決策圖建構法 | zh_TW |
dc.title | Construct Binary Decision Diagram
by Cofactor on Circuit Structure by Cofactor on Circuit Structure | en |
dc.type | Thesis | |
dc.date.schoolyear | 95-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 王柏堯,江介宏 | |
dc.subject.keyword | 二元決策圖,餘因式分解,正規驗證, | zh_TW |
dc.subject.keyword | BDD,cofactor,verification, | en |
dc.relation.page | 26 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2007-07-19 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 1.5 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。