跳到主要內容

臺灣博碩士論文加值系統

(34.226.244.254) 您好!臺灣時間:2021/08/01 04:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳佳鴻
研究生(外文):Jia-Hung Chen
論文名稱:偵測布林函數對稱性之新方法
論文名稱(外文):A New Approach to Symmetry Detection of Boolean Functions
指導教授:王國華王國華引用關係
指導教授(外文):Kuo-Hua Wang
學位類別:碩士
校院名稱:輔仁大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:56
中文關鍵詞:同等對稱性非同等對稱性弱對稱性強對稱性
外文關鍵詞:Equivalence SymmetryNon-Equivalence SymmetryWeak SymmetryStrong Symmetry
相關次數:
  • 被引用被引用:0
  • 點閱點閱:117
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
對稱性偵測是去檢查布林函數中輸入的對稱情況。這對於許多應用在邏輯合成、實體設計和測試方面,都是一個非常有用的特性。這篇論文針對不完全布林函數提出兩個偵測對稱性的演算法。我們的演算法不需計算餘因子和做同等性驗證。此外,我們的演算法不但可以適用於不完全布林函數,也可以用於完全布林函數。我們也針對不完全布林函數提出尋找較大和最大對稱性的演算法。透過結果,我們的方法的確可以有效偵測布林函數的對稱性。
Symmetry detection is to check input symmetries of Boolean functions. It is a useful property for many applications in logic synthesis, physical design and testing. This thesis proposes two symmetry detection algorithms for incompletely specified functions. Our algorithms detect symmetries without using cofactor computation and equivalence checking. Moreover, our algorithms can not only handle incompletely specified functions but also completely specified functions. We also provide algorithms to find maximal and maximum symmetries for incompletely specified functions. By the experimental results, our methods are indeed very efficient to detect symmetries of Boolean functions.
1 Introduction
1.1 Motivation
1.2 Related Works
1.3 Organization of Thesis

2 Symmetry Detection for Incompletely Specied Functions
2.1 Background
2.2 Symmetry Detection with Don't Cares

3 Symmetry Detection with Cube Notations
3.1 Symmetry Detection Using Cube Pairs
3.2 The Symmetry Detection Algorithm
3.2.1 Removing Non-Symmetric Sets by Cube Pairs Implementation Issues
3.3 Extension to Single Variable, Skew and Strong Symmetry

4 Symmetry Detection with OBDD's
4.1 K-Disjointness Paradigm
4.1.1 K-Disjointness between Boolean Functions
4.1.2 Correlating K-Disjointness Paradigm with Symmetry Detection
4.2 Symmetry Detection Algorithm
4.3 Extension to Skew and Strong Symmetry

5 Maximal and Maximum Symmetries of Incompletely Specied Func-
tions
5.1 A Heuristic Method
5.2 A Greedy Method Based on Branch-and-Bound
5.3 An Exact Algorithm

6 Experimental Results
6.1 Experimental Results with Cube Notations
6.2 Experimental Results with OBDD's

7 Conclusions
[1] B.G. Kim and D.L. Dietmeyer, "Multilevel logic synthesis of symmetric switching functions",IEEE Trans. on Computer-Aided Design, vol. 10, pp. 436-446, April 1991.

[2] Feng Wang and D.L. Dietmeyer, "Exploiting near symmetry in multilevel logic synthesis", IEEE Trans. on Computer-Aided Design, vol. 17, pp. 772-781, Sept. 1998.

[3] V.N. Kravet and K.A. Sakallah, "Constructive library-aware synthesis using symmetries", in Proc. European Design Test Conf., 2000, pp. 208-213.

[4] C. Tsai and M. Marek-Sadowska, "Boolean matching using generalized Reed-Muller forms", in Proc. Design Automation Conf., pp. 339-344, June, 1994.

[5] F.A. Aloul, A. Ramani, I.L. Markov, and K.A. Sakallah, "Solving difficult SAT instances in the presence of symmetry", in Proc. Design Automation Conf., pp. 731-736, 2002.

[6] C. Scholl, D. Moller, P. Molitor, and R. Drechsler, "BDD minimization using symmetries", IEEE Trans. Computer-Aided-Design, vol. 18, pp. 81-100, Feb. 1999.
[7] C.W. Chang, Bo Hu and M. Marek-Sadowska, "In-place delay constrained power optimization using functional symmetries", in Proc. European Design Test Conf., pp. 377-382, 2001.

[8] S. Chakrabarti, S. Das, D.K. Das, and B.B. Bhattacharya, "Synthesis of symmetric functions for path-delay fault testability", IEEE Trans. Computer-Aided Design, vol. 9,
pp. 1076-1081 Sept. 2000.

[9] A. Mukhopadhyay, "Detection of total or partial symmetry of a switching function with the use of decomposition charts", IEEE Trans. Electron. Comput., vol. EC-12,
pp. 535-557, Oct. 1963.

[10] D.L. Dietmeyer and P.R. Schneider, "Identification of symmetry, redundancy, and equivalence of Boolean functins", IEEE Trans. Electron. Comput. vol. 16, pp. 804-817, Dec. 1967.

[11] C.C. Tsai and M. Marek-Sadowska, "Generalized Reed-Muller forms as a tool to detect symmetries", IEEE Trans. Comput., vol. 45, pp. 33-40 , Jan. 1996.

[12] B.J. Falkowski and S. Kannurao, "Skew symmetry detection using the Walsh Spectral Coefficients", in Proc. International Symposium on Cirucuit and System , 2000, vol. 2, pp. 321-324.

[13] S. Rahardja and B.J. Falkowski, "Symmetry conditions of Boolean functions in complex Hadamard transform", Electronics Letters, vol. 34, pp. 1634-1635, Aug. 1998.

[14] C. Scholl, S. Melchior, G. Hotza, and P. Molitor, "Minimizing ROBDD sizes of incompletely specified functions by exploiting strong symmetries", in Proc. European Design Test Conf.,Mar. 1997, pp. 229-234.

[15] Alan Mishchenko, "Fast Computation of Symmetries in Boolean Functions", IEEE Trans. Computer-Aided-Design, vol. 18, pp. 1588-1593, Nov. 2003.
[16] C.L. Liu, "Introduction to Combinatiorial Mathematics", McGraw Hill College Div., 1968.

[17] E.M. Sentovich, K.J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P.R. Stephan, R.K. Brayton, A. Sangiovanni-Vincentelli, "SIS: A System for Sequential Circuit Synthesis", Electronics Research Laboratory, Memorandum No. UCB/ERL M92/41, 4 May 1992.

[18] F. Somenzi. CUDD Package, Release 2.3.1. [Online] Availabe: http://vlsi/Colorado.EDU/~fabio/CUDD/cuddIntro.html

[19] A. Mishchenko. EXTRA library of DD procedures. [Onlin]. Available: http://www.ee.pdx.edu/~alanmi/research/extra.htm

[20] C. -W. Chang, C. -K. Cheng, P. Suaris and M. Marek-Sadowska, "Fast Post-placement Rewiring Using Easily Detectable Functional Symmetries", pp. 286-289, Design Automation Conference, 2000.

[21] Y. -M. Jiang, A. Krstic, K. -T. Cheng, and M. Marek-Sadowska, "Post-Layout Logic Restructuring for Performance Optimization", in Proc. of DAC, pp. 662-665, 1997.

[22] S. Minato, "Zero-suppressed BDDs for set manipulation in combinatiorial problems", in Proc. Design Automation Conf., 1993, pp. 272-277.

[23] D. Moller, J. Mohnke, and M. Weber, "Detection of symmetry of Boolean functions represented by ROBDD's", in Proc. Int. Conf. Computer Aided Design, 1993, pp. 680-684.

[24] R.E. Bryant, "Graph-based algorithms for Boolean function manipulation", IEEE Trans. Comput., vol. C-35, pp.677-691, 1986.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 13.謝立功著,電子商務發展之挑戰-網路洗錢相關問題之探討(上),科技法律透析,民國八十九年十月。
2. 14.謝立功著,電子商務發展之挑戰-網路洗錢相關問題之探討(下),科技法律透析,民國八十九年十一月。
3. 16.謝立功著,我國防制洗錢法制之省思,律師雜誌,民國八十八年八月。
4. 19.劉連煜著,評議洗錢防制法草案中之「可疑申報制」,軍法專刊,民國八十四年十二月。
5. 20.謝易宏著,網路銀行法律問題之研究,月旦法學雜誌第七十一期,民國九十年四月。
6. 21.林昱仁著,電子支付系統,電腦與通訊第八十五期,民國八十八年五月。
7. 23.林育廷著,淺論我國網路金融法制相關問題之研究,科技法律透析,二○○一年二月。
8. 24.郭冠甫著,電子付款機制的興起與相關法律問題(上)(下),資訊法務透析,二○○一年一月。
9. 25.李榮謙、方耀著,電子支付系統與電子貨幣:發展、影響及適當的管理架構,中央銀行季刊第廿三卷第三期。
10. 26.方翊人著,現金儲值卡與消費者保護相關問題之研究,科技法律透析二○○二年三月。
11. 30.楊靜宜著,網路行為管轄權爭議問題之初探,資訊法務透析,一九九九年五月號。
12. 33.林合民著,對電腦資訊之搜索與扣押,律師雜誌第二三三期。
13. 34.盧文祥著,電腦犯罪之偵查實務,律師雜誌第二二八期。
14. 35.蔡美智著,美國重要之網路犯罪防治相關單位組織簡介,資訊法務透析,二○○○年三月。