積之互斥和表示式之邏輯最佳化工具設計

Design of a Logic Optimization Tool for Exclusive-or Sum-of-Products Expressions

王崇安(Chong-An Wang)

指導教授 ： 陳少傑

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.01547

摘要

在這篇論文裡，我們設計了一個邏輯最佳化工具，用來化簡多輸出之布林函數(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.

並列關鍵字

Exclusive-or Sum-of-Products ； XOR gate ； Logic Optimization

參考文獻

[1] M. Karnaugh, “The Map Method for Synthesis of Combinational Logic Circuits,” Trans. on American Institute of Electrical Engineers, vol. 72, no. 9, pp. 593-599, Nov. 1953.

[2] E.J. McCluskey, “Minimization of Boolean Functions,” Bell System Technical Journal, vol. 35, no. 5, pp. 1417-1444, Apr. 1956.

[3] W. Quine, “A Way to Simplify Truth Functions,” American Mathematical Monthly, vol. 62, no. 9, pp. 627-631, Nov. 1955.

[4] E. W. Veitch, “A Chart Method for Simplifying Truth Functions,” Proc. Association for Computing Machinery, pp. 127-133, May. 1952.

[6] T. Sasao and P. Besslich, “On the Complexity of Mod-2 Sum PLAs,” IEEE Trans. on Computers, vol. 39, no. 2, pp. 262-266, Feb. 1990.