Abstract
傳統上, 邏輯函數大都以AND/OR閘來實現. 近年來, 已經有很多邏輯最佳化針對積之和 ( Sum of Product) 的問題提出最佳的解. 最近, 有一些研究表示適當的運用一些XOR閘可 以使數學運算的函數變得很簡單. 再者, 在一些現場可程式閘陣列 (Field Programmable Gate Arrays) 的結構中, XOR閘不需要額外的代價, 因為在每一個巨集原件 (macrocell )中, 有一個已經現成的XOR閘. 因此, 吸引更多的研究人員去發展一些工具, 針對邏輯 合成時運用XOR閘在現場可程式閘陣列中. 此論文的目標就是去發展一套新的邏輯合成器去有效利用XOR閘. 我們發展一個新的邏輯合成方法針對AND-OR-XOR多層次線路.首先, 我們提出一個啟發式的(heuristic) 演算法針對適合用 Davio expansion 展開的函數, 運用OFDDs (Ordered Functional Decision Diagrams) 去得到其 FPRMs(Fixed Polarity Reed-Muller expressions). 因為對一些數學運算的函數用 FPRM 表示式可以變得很精簡. 再者, 我們針對那些不適合用 Davioexpansion 去展開的函數, 利用 off-set 方法去做化簡. off-set 方法是利用 XOR 閘的特性去增加一個函數的 on-set 部分. 論文中的程式是以 C 語言來實作, 我們以 MCNC 的例子來進行我們的實驗, 在字元(literal) 數比較上, 實驗結果證實我們的方法比 SIS 的結果平均好35.4%. 在未來, 我們將以立方因子來改進 FPRM 表示式, 另外我們會繼續研究更智慧化的方式來決定更適合某函數的 off-set.In this thesis, we present a new logic synthesis method for AND-OR-XOR multi-level networks. First, we propose a heuristicalgorithm which usesOFDDs (Ordered Functional Decision Diagrams)for FPRMs (Fixed PolarityReed-Muller expressions) minimization,which is used to expand the functionssuitable for Davioexpansion. Then, we use an off-set method to reduce theremainingsubfunctions which are not suited for Davio expansion.Experimentalresults show that our algorithm reduces the numberof literal count on theaverage of 35.4% compared to thatgenerated by SIS 1.2.