臺灣博碩士論文加值系統

在臨界值函數辨識的演算法中，擁有一個充分條件和必要條件是非常關鍵的。但是目前還不存在一個合適的充分條件和必要條件來讓我們利用。在目前最好的研究中，使用了一個必要條件和權重及臨界值分配的方法來辨識臨界值函數。幾十年前，有一個稱作「總和相等理論」的充分條件和必要條件被提出來了。然而在實作層面上，這個理論以及對應的檢測演算法，因為較高的複雜度，所以效率的觀點上來看是不切實際的。在這篇論文中，我們提出了幾個新的理論，可以有效的減少臨界值辨識演算法的複雜度。此外，根據實驗結果來看，我們在計算量上平均減少了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/