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

趙曙光，羅 霄，崔 平

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

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

趙曙光，羅 霄，崔 平

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

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

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

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

1 相關(guān)背景及概念

1.1 常用可逆邏輯門

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

圖1 常用MCT門

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

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

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

1.3 M-GEP算法

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

t=h(n-1)+1

(1)

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

(2)染色體結(jié)構(gòu)和調(diào)用。

1)染色體結(jié)構(gòu)。多層染色體的結(jié)構(gòu)模式是M-GEP的特有的形式，針對多層染色體結(jié)構(gòu)，先對普通的基因加以改進(jìn)以適應(yīng)于多層染色體的新形式，其次也為后續(xù)的調(diào)用做準(zhǔn)備。

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟5重復(fù)步驟3和步驟4，直到種群內(nèi)所有的個體的適應(yīng)度值都求完，即結(jié)束適應(yīng)度的計算；

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

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

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

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

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

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

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

圖3 基因隨機(jī)重組算子操作示意圖

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

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

2 M-GEP算法設(shè)計

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

輸入訓(xùn)練集和M-GEP配置。

輸出最佳的適應(yīng)度個體。

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

Init(StepConfig);

//調(diào)用評價函數(shù)

DefaultJudge(self,Population);

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

While(FCurrentGenaration < FMaxGenaration) do begin

//將適應(yīng)度排名第一的繼承下來

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

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

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

//調(diào)用評價函數(shù)

DefaultJudge(self,tmpPopulation);

//將結(jié)果排序并復(fù)制到下一代

Sort(tmpPopulation,Population);

//進(jìn)化輩數(shù)加1

Inc(FCurrentGenaration);

//如果最佳進(jìn)化結(jié)果滿足指定條件則退出

if tmpPopulation[0].Score

end;

//返回最佳適應(yīng)度個體

Result=tmpPopulation[0];

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

圖4 M-GEP算法流程圖

3 實驗結(jié)果分析

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

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

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

圖5 6輸入變量結(jié)果

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

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

圖7 10輸入變量結(jié)果

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

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

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

[2] 管致錦.可逆邏輯綜合[M].北京:科學(xué)出版社,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:基于多層染色體基因表達(dá)式編程的遺傳進(jìn)化算法[J].計算機(jī)學(xué)報,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] 張明明.面向量子可逆邏輯自動綜合的多目標(biāo)進(jìn)化算法研究[D].上海:東華大學(xué),2010.

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

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

[15] 夏凱祥,趙曙光,方聰,等.面向可逆邏輯綜合的GEP算法設(shè)計與實現(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

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

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

10.16180/j.cnki.issn1007-7820.2017.11.002