陳少傑臺灣大學：電子工程學研究所王崇安Wang, Chong-AnChong-AnWang2007-11-272018-07-102007-11-272018-07-102007http://ntur.lib.ntu.edu.tw//handle/246246/57351在這篇論文裡，我們設計了一個邏輯最佳化工具，用來化簡多輸出之布林函數(Multi-output Boolean function)的積之互斥和表示式(Exclusive-OR Sum of Product)，積之互斥和表示式已經被證明在許多種類的函式中，所需要的積的數量比一般使用或邏輯閘(OR gate)的積之和表示式(Sum of Product)還要來的更少。在本文中，我們提出了一個特別的資料結構Sierpinski Gasket用來儲存積之互斥和表示式所需要的資訊。另外，我們也提出了一個兩階段的模擬退火演算法(simulated annealing)，用來處理積之互斥和表示式的最小化。 使用Sierpinski Gasket這個特殊資料結構的好處在於它非常適合於用來表示積之互斥和表示式，而且在我們的測試函式中，它所需要花費的記憶體也相當的少。而使用退火演算法的優點在於它可以幫助我們跳脫出一個解的區域極小值，使我們更容易找到整體的最小值。實驗顯示本文提出之演算法有不錯的處理效能，並可藉由調整模擬退火演算法之參數來增加此演算法之適應性。A logic optimization tool for minimizing the Exclusive-OR Sum of Product (ESOP) forms in a Multi-output Boolean function is designed. ESOP forms have been proven to require fewer products for many classes of functions than the more common Sum of Product (SOP) forms using inclusive-OR operator. In this Thesis, we propose a particular data structure called Sierpinski Gasket to store the information of ESOP expression. Besides, we also propose a two-stage simulated annealing algorithm to perform the ESOP minimization. The benefits of applying the particular data structure are that it is very suitable for the ESOP expression and it has lower memory usage in most test cases. The advantage of using the two-stage simulated annealing algorithm is that it can help a solution to escape from a local minimum thus to find an optimum solution more globally. Experimental results show that we achieve better performance and flexibility by adjusting the parameters of the two-stage simulated annealing algorithm.ABSTRACT i LIST OF FIGURES v LIST OF TABLES vii CHAPTER 1 INTRODUCTION 1 1.1 SOP versus ESOP 2 1.2 Methods of Minimization 4 1.2.1 SOP Minimization Methods 4 1.2.2 ESOP Minimization Methods 5 1.3 Motivation 6 1.4 Contribution 7 1.5 Thesis Organization 7 CHAPTER 2 DATA STRUCTURE 9 2.1 Background 9 2.1.1 Three Basic Expansions 9 2.1.2 ESOP Expression Forms 10 2.2 Sierpinski Gasket 12 2.3 Modified Sierpinski Gasket 13 2.4 Coordinate Convention 15 2.4.1 The First Coordinate Convention 15 2.4.2 The Second Coordinate Convention 16 2.5 ESOP 17 2.6 Manipulation Rules 18 2.7 A Manipulation Example 20 CHAPTER 3 MINIMIZATION ALGORITHM 23 3.1 Distance-k Operation 23 3.1.1 Distance-1 Operation 24 3.1.2 Distance-2 Operation 25 3.1.3 Distance-3 Operation 26 3.2 Initial Solution Generating 28 3.2.1 Disjoint Sum-of-Product Form 28 3.2.2 DSOP Transformation 29 3.3 Minimization Algorithm 34 3.3.1 Simulated Annealing 35 3.3.2 Two-stage Simulated Annealing 38 CHAPTER 4 EXPERIMENTAL RESULTS 41 4.1 The Sierpinski Gasket Structure 41 4.2 Two-stage Simulated Annealing 44 4.3 ESOP Minimization Algorithm 45 CHAPTER 5 CONCLUSION 49 REFERENCE 51847543 bytesapplication/pdfen-US積之互斥和互斥閘邏輯最佳化Exclusive-or Sum-of-ProductsXOR gateLogic Optimizationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/57351/1/ntu-96-R94943074-1.pdf