跳到主要內容

臺灣博碩士論文加值系統

(44.211.239.1) 您好!臺灣時間:2023/01/31 06:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:許文誌
研究生(外文):Hsu, Wen-Chih
論文名稱:針對臨界值函數識別之降低計算量方法的研究
論文名稱(外文):On Reduction of Computation for Threshold Function Identification
指導教授:王俊堯王俊堯引用關係
指導教授(外文):Wang, Chun-Yao
口試委員:江介宏劉建男
口試委員(外文):Jiang, Jie-HongLiu, Chien-Nan
口試日期:2020-07-29
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2020
畢業學年度:108
語文別:英文
論文頁數:25
中文關鍵詞:臨界值函數臨界值函數辨識演算法權重分配法總和相等理論
外文關鍵詞:ThresholdFunctionTFIdentificationAlgorithmWeightAssignmentProcedureSummableCheckingProcessInputVector
相關次數:
  • 被引用被引用:0
  • 點閱點閱:115
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在臨界值函數辨識的演算法中,擁有一個充分條件和必要條件是非常關鍵的。但是目前還不存在一個合適的充分條件和必要條件來讓我們利用。在目前最好的研究中,使用了一個必要條件和權重及臨界值分配的方法來辨識臨界值函數。幾十年前,有一個稱作「總和相等理論」的充分條件和必要條件被提出來了。然而在實作層面上,這個理論以及對應的檢測演算法,因為較高的複雜度,所以效率的觀點上來看是不切實際的。在這篇論文中,我們提出了幾個新的理論,可以有效的減少臨界值辨識演算法的複雜度。此外,根據實驗結果來看,我們在計算量上平均減少了75到96個百分比,實際上的數字取決於輸入函數的輸入變數數量。
Having a sufficient and necessary condition for being a threshold function (TF) is quite crucial for TF identification algorithm. However, there does not exist an appropriate sufficient and necessary condition that we can take advantage of. The state-of-the-art to this identification problem exploits a necessary condition and weight and threshold value assignment to identify TF. Many decades ago, a sufficient and necessary condition for being a TF had been proposed, which is called the Summable Theorem. However, this theorem and the corresponding checking algorithm are not practical from the viewpoint of efficiency due to the high complexity in realization. In this thesis, we propose several new theorems such that the complexity of the TF identification algorithm can be significantly reduced. Furthermore, according to the experimental results, the ratios of reduced computation are 75\%$\sim$96\% on average, depending on input bits of the input function.
中文摘要 i
abstract ii
誌謝辭 iii
contents iv
List of Tables vi
List of Figures vii
1 Introduction 1
2 Preliminaries 4
3 Semi-critical Summable Theorem 8
4 2-Summable Theorem 16
5 Experimental Results 19
6 Conclusion 22
[1] V. Beiu, J. M. Quintana, and M. J. Avedillo, “VLSI implementations ofthreshold logic: A comprehensive survey,” IEEE Trans. Neural Netw.,vol. 14, no. 5, pp. 1217–1243, Sep. 2003.
[2] K. Berezowski and S. Vrudhula, “Automatic design of binary multiple-valued logic gates on the rtd series,”in Eight Euromicro Conf. on DigitalSystem Design, 2005.
[3] Y. Crama, and P. L. Hammer, “Boolean Functions: Theory, Algorithms,and Applications,” Cambridge University Press, 2011.
[4] M. J. Ghazala, “Irredundant disjunctive and conjunctive forms of aBoolean function,” I.B.M. Journal of Research and Development, vol.1, pp. 171-176, April 1957.
[5] P.-Y. Kuo, C.-Y. Wang, and C.-Y. Huang, “On Rewiring and Simplifica-tion for Canonicity in Threshold Logic Circuits,” inProc. ICCAD, pp.396-403, 2011.
[6] S.-Y. Lee, N.-Z. Lee, and J.-H. R. Jiang, “Canonicalization of thresholdlogic representation and its applications,” inProc. ICCAD, pp. 1-8, 2018.
[7] C.-C. Lin, C.-Y. Wang, Y.-C. Chen, and C.-Y. Huang, “Rewiring forThreshold Logic Circuit Minimization,” inProc. DATE, pp. 1-6, 2014.
[8] C.-C. Lin, C.-W. Huang, C.-Y. Wang and Y.-C. Chen, “In&Out: Restruc-turing for Threshold Logic Network Optimization,” inProc. ISQED, pp.413-418, 2017.
[9] C.-C. Lin, C.-H. Liu, Y.-C. Chen, C.-Y. Wang, and S. Yamashita, “ANew Necessary Condition for Threshold Function Identification,”IEEETrans. on Computer-Aided Design, Early access, 2020.
[10] C.-H. Liu, C.-C. Lin, Y.-C. Chen, C.-C. Wu, C.-Y. Wang, and S.Yamashita, “Threshold Function Identification by Redundancy Removaland Comprehensive Weight Assignments,”IEEE Trans. on Computer-Aided Design, vol. 38, no. 12, pp. 2284 - 2297, 2019.
[11] V. A. Mardiris, G. C. Sirakoulis, and I. G. Karafyllidis, “Automateddesign architecture for 1-D cellular automata using quantum cellularautomata,”IEEE Trans. Computers, vol. 64, no. 9, pp. 2476–2489, Sep.2015.
[12] S. Minato, “Fast generation of prime-irredundant covers from binarydecision diagrams,” IEICE Trans. Fundamentals, vol. E76-A, no. 6, pp.976- 973, 1993.
[13] S. Muroga,“Threshold Logic and its Applications,” New York, NY: JohnWiley, 1971.
[14] A. Neutzling, J. M. Matos, A. I. Reis, R. P. Ribas, and A. Mishchenko,“Threshold logic synthesis based on cut pruning,” inProc. ICCAD, pp.494-499, 2015.
[15] A. Neutzling, J. M. Matos, A. Mishchenko, A. I. Reis, and R. P. Ribas,“Effective Logic Synthesis for Threshold Logic Circuit Design,”IEEETrans. on Computer-Aided Design, vol. 38, no. 5, pp. 926-937, 2019.
[16] A. Neutzling, M. G. A. Martins, V. Callegaro, A. I. Reis, and R.P. Ribas, “A Simple and Effective Heuristic Method for Threshold LogicIdentification,”IEEE Trans. on Computer-Aided Design, vol. 37, no. 5,pp. 1023-1036, 2018.
[17] G. Papandroulidakis, A. Serb, A. khiat, G. Merreet, and T. Prodromakis,“Practical Implementation of Memristor-Based Threshold Logic Gates,”IEEE Trans. on Circuits and Systems, vol. 66, no. 8, pp. 3041-3051,2019.
[18] S. R. Petrick, “A direct determination of the irredundant forms of aBoolean function from a set of prime implicants,” A.F. Cambridge Res.Center, Bedford, Mass., Report AFCRC-TR-56-110, 1956.
[19] W. V. Quine, “The problem of simplifying truth functions,” Am. Math.Monthly, vol. 59, pp. 521-531, 1952.
[20] V. Saripalli, L. Liu, S. Datta, and V. Narayanan, “Energy-delay Per-formance of Nanoscale Transistors Exhibiting Single Electron Behaviorand Associated Logic Circuits,”Journal of Low Power Electronics, vol.6, pp. 415-428, 2010.
[21] P. Wang, M. Y. Niamat, S. R. Vemuru, M. Alam, and T. Killian,“A Synthesis of Majority/Minority Logic Networks,”IEEE Trans. onNanotechnology, vol. 14, no. 3, pp. 473-483, 2015.
[22] R. O. Winder, “Enumeration of Seven-Argument Threshold Functions,”IEEE Trans. on Electronic Computers, pp. 315-325, 1965.
[23] R. Zhang, P. Gupta, L. Zhong, and N. K. Jha, “Threshold NetworkSynthesis and Optimization and Its Application to Nanotechnologies,”IEEE Trans. Computer-Aided Design, vol. 24, no. 1, pp.107-118, 2005.
[24] Y. Zheng, M. S. Hsiao, and C. Huang, “SAT-based Equivalence Check-ing of Threshold Logic Designs for Nanotechnologies,”in Proc. GreatLake Symp. VLSI, May 2008, pp. 225-230.
[25] http://minisat.se/
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top