趙曙光，羅 霄，崔 平

(東華大學 信息科學與技術學院，上海 201620)

基于M-GEP的可逆邏輯綜合方法研究

趙曙光，羅 霄，崔 平

(東華大學 信息科學與技術學院，上海 201620)

可逆邏輯綜合是設計和實現(xiàn)可逆邏輯電路的基礎和難點。將改進的基于多層染色體基因表達式編程算法應用到可逆邏輯電路的綜合與優(yōu)化中，利用多層染色體構建的調用模型對個體進行表達，可根據(jù)預期的邏輯功能，自動求取便于構造可逆邏輯網(wǎng)絡的最簡"積之異或和"表達式。經(jīng)初步驗證，在解決可逆邏輯電路的多輸入單輸出的問題上，比現(xiàn)有的綜合方法更有效。

多層染色體基因表達式編程；可逆邏輯綜合；積之異或和；C語言編程實現(xiàn)

可逆邏輯電路(Reversible Logic Circuits)是一種可避免信息損失和有效降低能量損耗甚至達到零損耗的新型電路，是未來降低集成電路功耗的必由之路[1]。可逆邏輯電路是由可逆邏輯門依次級聯(lián)構成，利用給定的邏輯門，按照可逆邏輯網(wǎng)絡無扇入扇出、無反饋等約束條件和限制[2-3]，實現(xiàn)預期邏輯功能且盡可能優(yōu)化的電路?？赡孢壿嬤\算以“異或”運算為基礎，運算表達式稱為“積之異或和”表達式。本文研究的基于多層染色體基因表達式編程算法(Multilevel Chromosome Gene Expression Programming Algorithm，M-GEP)[4]的可逆邏輯綜合方法，將改進的M-GEP應用到可逆邏輯綜合電路的綜合與優(yōu)化中，利用多層染色體構建的調用模型對個體進行表達，可根據(jù)預期的邏輯功能，自動求取便于構造可逆邏輯網(wǎng)絡的最簡“積之異或和”表達式，并得到可逆邏輯電路。經(jīng)驗證，在解決可逆邏輯電路的多輸入單輸出問題上，比現(xiàn)有的綜合方法更有效。

1 相關背景及概念

1.1 常用可逆邏輯門

在可逆邏輯中，常用的可逆邏輯門有CNOT門、Toffoli門和PNC門[5-8]等，它們都是屬于多控制位單目標位門(Multi Control single Terminal，MCT)[9]，如圖1所示。

圖1 常用MCT門

圖1(a)CNOT門：單控門，控制位為“1”時，目標位取反，否則目標位保持變；圖1(b)Toffoli門：雙控門，兩個控制位都為“1”時，目標位取反，否則目標位保持不變；圖1(c)PNC門：正反控制門，正控制位為“1”，反控制位為“0”時，目標位取反，否則目標位保持不變。

1.2 可逆邏輯網(wǎng)絡

由可逆邏輯門級聯(lián)組成的電路稱為可逆邏輯網(wǎng)絡[10-11]。構造可逆邏輯網(wǎng)絡的具體步驟為：首先添加一位輔助位作為目標位，其次根據(jù)將輸入變量作為控制位的集合，并將目標位初始化為0，再根據(jù)每個乘積項添加一個MCT門，乘積項所有輸入變量的組合就是該MCT門的控制端的輸入，輔助位的輸出為最后的輸出結果。

1.3 M-GEP算法

(1)基因編碼。M-GEP的編碼是多層的染色體以及每層染色體中有多個基因[4]?；蚴怯苫蝾^部 和尾部 組成，包含了函數(shù)運算符和終端字符集(編碼字符)，基因頭部可以是兩者中的任何元素，基因尾部只能是終端字符集中的元素?；蝾^部和尾部的關系如式(1)所示，其中 為運算符結合的目數(shù)

t=h(n-1)+1

(1)

運算符集為F={&,⊕,!}，終端字符集為T={A,B,C,D,…}，{F,T}組成了編碼的來源信息，函數(shù)集中運算符的最大結合目數(shù)為2，所以根據(jù)基因字符串編碼轉換得到的表現(xiàn)型樹是二叉樹。

(2)染色體結構和調用。

1)染色體結構。多層染色體的結構模式是M-GEP的特有的形式，針對多層染色體結構，先對普通的基因加以改進以適應于多層染色體的新形式，其次也為后續(xù)的調用做準備。

基因：基因G包含5個元素[4]，記為G=(Q,T,F,δ,s),Q， 為基因型；T為基因終端字符集；F為函數(shù)運算符集；δ為對基因進行操作的遺傳算子集合，包含變異算子、交叉算子、插串算子等； 是基因的適應度值。

染色體：染色體C包含5個元素[4]，記為C=(∑,T,F,δ,s)，∑為基因的集合；T為基因終端字符集；F為染色體中的基因連接函數(shù)運算符；δ為對染色體進行操作的遺傳算子集合；s為染色體的適應度值。

C中δ是染色體算子和基因算子的并集[4]。因此有δ=δc∪(δg1∪δg2∪…∪δgn)，n=length(C(∑))。δc是染色體算子，如染色體重組算子和基因隨機重組算子等。δgi=(i=1,2,…,length(C(∑)))，表示每層染色體上的各個基因的遺傳操作算子，一般取δg1=δg2=…=δgn，(n=length(C(∑)))即針對所有的染色體內的基因，它們的操作算子是相同的。

個體與種群：個體是組成種群的基本單元，個體I有3個元素[4]，記為I=(∑,δ,s)，∑表示個體的所有染色體集合；δ是對每個個體的遺傳操作的集合；s表示的是個體的適應度值。種群P=(∑),∑是個體的集合。

染色體的遺傳算子集合I(δ)是δ=δi∪(δc1∪δc2∪…∪δcn)，n=length(I(∑))。其中，δi是對個體內的多個染色體進行操作的遺傳算子，如染色體重組算子和基因隨機重組算子。δci(i=1,2,3,…，n)，n=length(I(∑))是針對的每個染色體的操作；

2)染色體之間的調用。M-GEP算法中的個體是具有多個染色體的，染色體I(∑)之間的關系通過特定的調用規(guī)則來保證它們之間是聯(lián)系的，而不是單獨且割裂的。

M-GEP中將染色體之間的關系設計為從上到下的調用關系[4]，染色體分別記為C1,C2,…,Ck，k=length(I(∑))，K為染色體的個數(shù)，設C1(∑)=(G(1,1),G(1,2),…,G(1,n))，n=length(C1(∑))，n為第一個染色體的基因的總數(shù)；C1(∑)的結構說明了其包含的基因數(shù)。第二層染色體的終端字符集為C2(T)=(G(1,1),G(1,2),…,G(1,n))，n=length(C1(∑))，C2(T)的結構即說明了第2層染色體對第1層染色體的基因的調用關系，推廣到第K個染色體 ，Ck(T)=(G(i-1,1),G(i-1,2),…G(i-1,n)),i>1。上層的染色體的基因的終端字符集是來源于下層染色體的基因；

(3)適應度函數(shù)。適應度函數(shù)的選取和具體的問題有關，它決定了種群進化的方向，對生成的新種群的質量高低有著決定性的影響[12]，因此根據(jù)實際的問題分析找到適合該問題的適應度函數(shù)和評價準則是至關重要的。本文中利用M-GEP對可逆邏輯電路進行綜合與優(yōu)化，對基因編碼字符串進行遺傳操作，利用表達式樹與真值表的匹配度和所需可逆邏輯門的數(shù)量，判斷綜合的表達式的真值表和指定的真值表是否完全匹配，以及根據(jù)表達式的最簡形式判斷其生成的電路的門數(shù)是否是最少的。

在M-GEP中個體I(∑)的求適應度值I(s)的步驟[4]為：

步驟1分析每個個體的所有染色體所包含的基因，得到計算適應度值所需要的計算資源和操作方法。這些計算形式共同組成一個步驟數(shù)組，數(shù)組內包括計算操作符，運算操作符，參數(shù)在計算過程中需要偏移的量以及結果保存的存放地址等；

步驟2根據(jù)每個基因和染色體的計算步驟和需要的計算資源，分配固定長度的計算地址用于存放參數(shù)和運算的中間結果以及最終結果，在程序設計中對應的即通過棧的寫入和取出來執(zhí)行參數(shù)運算；

步驟3根據(jù)訓練集或測試用例存放在指定的空間內[4]；

步驟4根據(jù)步驟1計算出所需要的資源和步驟數(shù)組，針對給定的訓練集或測試用例對個體的適應度值進行計算，并將結果存放在棧中。棧的頂部位置一定是最新的中間計算結果或最終的適應度值；

步驟5重復步驟3和步驟4，直到種群內所有的個體的適應度值都求完，即結束適應度的計算；

(4)遺傳操作。M-GEP的遺傳操作包含選擇算子、交叉算子、變異算子、插串算子和染色體算子，染色體算子是M-GEP其獨有的算子，是對多基因染色體和多層染色體進行遺傳操作的算子。

選擇算子的作用對適應度值高的個體進行復制遺傳。個體被選中直接復制到下一代是利用輪盤賭的方法進行判斷的，適應度值高的個體被選中的概率大，適應度值低的個體被選中的概率小。

交叉算子包含單點交叉算子和多點交叉算子。交叉運算指相互配對的染色體根據(jù)交叉概率按照指定的交叉規(guī)則交換部分基因的過程。

突變算子是指將基因中的信息進行突變處理。變異算子和交叉算子兩者互相配合可以達到對空間的全局搜索和局部搜索。變異算子的作用過程即將原本位置上的基因字符改變成其他的基因字符。

插串算子包含了普通插串算子和根插串算子，插串算子在基因的任意位置開始選擇一段字符串，隨機的插入到基因頭部除第一個位置外的任意位置。根插串的子串選擇上不同于普通插串，它從基因的頭部任意位置開始查找，遇到第一個函數(shù)運算符后，以該位置處為起點隨機的選擇一段長度的子串作為插串子串，將它插入到基因頭部的第一個位置。由于插串算子將子串插入的位置在頭部，因此會導致超過頭部長度的基因字符被舍棄。

染色體算子包含染色體重組算子Pc和基因隨機重組算子Pr[4]。

圖2 染色體重組算子操作示意圖

圖3 基因隨機重組算子操作示意圖

如圖2所示，對與兩個需要進行染色體重組的個體，染色體重組算子Pc操作的基本單位是染色體，因此隨機的選擇個體中的某個或某一層染色體，在染色體上隨機的找到一個位置，這個位置即作為染色體重組的起點位置。

如圖3所示，基因隨機重組算子Pr操作的對象是每個個體中的基因，即它操作的最小單位是基因。在基因隨機重組算子作用下，隨機的選擇個體中的染色體上的基因，同時需要確認選擇的基因是在哪一層染色體上。

2 M-GEP算法設計

M-GEP算法[4]執(zhí)行的具體過程如下：

輸入訓練集和M-GEP配置。

輸出最佳的適應度個體。

//加載配置和種群初始化

Init(StepConfig);

//調用評價函數(shù)

DefaultJudge(self,Population);

//循環(huán)遺傳進化，直到達到最大輩數(shù)或找到符合適應度值的個體

While(FCurrentGenaration < FMaxGenaration) do begin

//將適應度排名第一的繼承下來

SetLength(tmpPopulation,1); tmpPopulation[0]=Population[0];

//依次進行各項遺傳算子操作，如交叉變異，染色體重組等

forx= 0 to FOperationCount - 1 do FOperationList[x](self,x,Population,temPopulation);

//調用評價函數(shù)

DefaultJudge(self,tmpPopulation);

//將結果排序并復制到下一代

Sort(tmpPopulation,Population);

//進化輩數(shù)加1

Inc(FCurrentGenaration);

//如果最佳進化結果滿足指定條件則退出

if tmpPopulation[0].Score

end;

//返回最佳適應度個體

Result=tmpPopulation[0];

根據(jù)M-GEP算法的實現(xiàn)步驟繪制算法流程，如圖4所示。

圖4 M-GEP算法流程圖

3 實驗結果分析

將M-GEP運用到可逆邏輯電路的綜合與優(yōu)化時，需要注意在基因編碼時，函數(shù)運算符集合是{⊕,&,!}，而基因字符集采用大寫字母來表示，即為{A,B,C,D…}，根據(jù)基因字符串的長度來選擇需要的字符。本文采用C語言編程實現(xiàn)了初步的實驗，在程序編寫時，為方便程序的運行操作，將“ ”代替“ ”進行表示，其他函數(shù)運算符不變。主要試驗參數(shù)如表1所示。

表1 實驗參數(shù)設置

實驗1對于6輸入變量的邏輯函數(shù)，通過M-GEP算法進行自動搜索最優(yōu)表達式。隨機生成輸入的真值表和M-GEP算法計算出的表達式結果和相應的基因編碼如圖5所示。

圖5 6輸入變量結果

圖6 6輸入可逆邏輯網(wǎng)絡

實驗2加大輸入變量的個數(shù)，對10輸入的變量進行綜合，隨機生成的真值表和根據(jù)M-GEP算法計算出的結果如圖7所示。

圖7 10輸入變量結果

圖8 10輸入可逆邏輯網(wǎng)絡

通過上述試驗結果的分析可知，M-GEP算法在進行邏輯表達式化簡是可行的，且在缺乏復雜的知識背景的情況下，可以綜合出理想的結果。相比較于遺傳算法[13]、遺傳編程[14]和基因表達式編程[15]，M-GEP的編碼可以簡單也可以根據(jù)實際問題改變的更為復雜，但由于有染色體之間的調用關系，使得可以通過不復雜的基因編碼在進化的過程中實現(xiàn)復雜的功能的作用，如實驗1中的基因長度只為21，但最終生成的基因的編碼字符串的長度是遠大于給定的基因的長度的，因此增加了解的空間，為解決更復雜的問題提供了思路。

[1] Bennett C H.Logical reversibility of computation[J]. IBM Journal of Research and Development,1973,17(6):525-532.

[2] 管致錦.可逆邏輯綜合[M].北京:科學出版社,2011.

[3] Mishchenko A,Perkowski M.Fast heuristic minimization of exclusive-sums-of-products[C].Portland: 5th International Reed-Muller Workshop,2001.

[4] 彭京,唐常杰,李川,等.M-GEP:基于多層染色體基因表達式編程的遺傳進化算法[J].計算機學報,2005,28(9):1459-1466.

[5] Divincenzo D P.Quantum gates and circuits[J].Proceedings of the Royal Society A Mathematical Physical & Engineering Sciences,1997,54(9):261-276.

[6] Fredkin E,Toffoli T.Conservative logic[J]. International Journal of Theoretical Physics,1982,21(3):219-253.

[7] Feynman R P,Hibbs A R,Styer D F. Quantum mechanics and path integrals[M].MA,USA:Courier Corporation,2005.

[8] Peres A.Reversible logic and quantum computers[J].Physical Review A,1985,32(32):3266-3276.

[9] Maslov D,Dueck G W,Miller D M.Toffoli network synthesis with templates[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2005,24(6):807-817.

[10] Maslov D,Miller D M.Comparison of the cost metrics through investigation of the relation between optimal NCV and optimal NCT three-qubit reversible circuits[J].IET Computers & Digital Techniques,2007,1(2):98-104.

[11] Shende V V,Prasad A K,Markov I L,et al. Synthesis of reversible logic circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2003,22(6):710-722.

[12] 張明明.面向量子可逆邏輯自動綜合的多目標進化算法研究[D].上海:東華大學,2010.

[13] 周明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業(yè)出版社,1999.

[14] 吉根林.遺傳算法研究綜述[J].計算機應用與軟件,2004,21(2):69-73.

[15] 夏凱祥,趙曙光,方聰,等.面向可逆邏輯綜合的GEP算法設計與實現(xiàn)[J].電子科技,2014,27(11):21-24,162.

Reversible Logic Synthesis Method Based on Gene Expression Programming of Multilayer Chromosomes

ZHAO Shuguang，LUO Xiao，CUI Ping

(School of Information Science and Technology,Donghua University,Shanghai 201620,China)

Reversible logic synthesis is the basis and difficulty of design and implementation of reversible logic circuits. An improved algorithm based on gene expression programming of multilayer chromosomes is applied to synthesis and optimization of reversible logic circuits. Individuals are expressed by multi-layer chromosome construction call model,it can automatically obtain the most simple "exclusive-OR sum" expression of the reversible logic network according to the anticipated logic function. After preliminary verification,in solving the problem of multiple-input single-output of the reversible logic circuit,of the integrated approach more effective.

multilayer chromosome gene expression programming;XOR;sum of reversible logic synthesis product;C language programming

TN79+1;TP301.6

A

1007-7820(2017)11-004-05

2016- 11- 16

國家自然科學基金(61272224);上海市教委科研創(chuàng)新重點項目(14ZZ068)

趙曙光(1965-)，男，博士，教授。研究方向：進化電路設計。羅霄(1990-)，男，碩士研究生。研究方向：可逆邏輯綜合等。

10.16180/j.cnki.issn1007-7820.2017.11.002