基于M-GEP的可逆逻辑综合方法研究

赵曙光，罗 霄，崔 平

(东华大学 信息科学与技术学院，上海 201620)

基于M-GEP的可逆逻辑综合方法研究

赵曙光，罗 霄，崔 平

(东华大学 信息科学与技术学院，上海 201620)

可逆逻辑综合是设计和实现可逆逻辑电路的基础和难点。将改进的基于多层染色体基因表达式编程算法应用到可逆逻辑电路的综合与优化中，利用多层染色体构建的调用模型对个体进行表达，可根据预期的逻辑功能，自动求取便于构造可逆逻辑网络的最简"积之异或和"表达式。经初步验证，在解决可逆逻辑电路的多输入单输出的问题上，比现有的综合方法更有效。

多层染色体基因表达式编程；可逆逻辑综合；积之异或和；C语言编程实现

可逆逻辑电路(Reversible Logic Circuits)是一种可避免信息损失和有效降低能量损耗甚至达到零损耗的新型电路，是未来降低集成电路功耗的必由之路[1]。可逆逻辑电路是由可逆逻辑门依次级联构成，利用给定的逻辑门，按照可逆逻辑网络无扇入扇出、无反馈等约束条件和限制[2-3]，实现预期逻辑功能且尽可能优化的电路。可逆逻辑运算以“异或”运算为基础，运算表达式称为“积之异或和”表达式。本文研究的基于多层染色体基因表达式编程算法(Multilevel Chromosome Gene Expression Programming Algorithm，M-GEP)[4]的可逆逻辑综合方法，将改进的M-GEP应用到可逆逻辑综合电路的综合与优化中，利用多层染色体构建的调用模型对个体进行表达，可根据预期的逻辑功能，自动求取便于构造可逆逻辑网络的最简“积之异或和”表达式，并得到可逆逻辑电路。经验证，在解决可逆逻辑电路的多输入单输出问题上，比现有的综合方法更有效。

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 可逆逻辑网络

由可逆逻辑门级联组成的电路称为可逆逻辑网络[10-11]。构造可逆逻辑网络的具体步骤为：首先添加一位辅助位作为目标位，其次根据将输入变量作为控制位的集合，并将目标位初始化为0，再根据每个乘积项添加一个MCT门，乘积项所有输入变量的组合就是该MCT门的控制端的输入，辅助位的输出为最后的输出结果。

1.3 M-GEP算法

(1)基因编码。M-GEP的编码是多层的染色体以及每层染色体中有多个基因[4]。基因是由基因头部 和尾部 组成，包含了函数运算符和终端字符集(编码字符)，基因头部可以是两者中的任何元素，基因尾部只能是终端字符集中的元素。基因头部和尾部的关系如式(1)所示，其中 为运算符结合的目数

t=h(n-1)+1

(1)

运算符集为F={&,⊕,!}，终端字符集为T={A,B,C,D,…}，{F,T}组成了编码的来源信息，函数集中运算符的最大结合目数为2，所以根据基因字符串编码转换得到的表现型树是二叉树。

(2)染色体结构和调用。

1)染色体结构。多层染色体的结构模式是M-GEP的特有的形式，针对多层染色体结构，先对普通的基因加以改进以适应于多层染色体的新形式，其次也为后续的调用做准备。

基因：基因G包含5个元素[4]，记为G=(Q,T,F,δ,s),Q， 为基因型；T为基因终端字符集；F为函数运算符集；δ为对基因进行操作的遗传算子集合，包含变异算子、交叉算子、插串算子等； 是基因的适应度值。

染色体：染色体C包含5个元素[4]，记为C=(∑,T,F,δ,s)，∑为基因的集合；T为基因终端字符集；F为染色体中的基因连接函数运算符；δ为对染色体进行操作的遗传算子集合；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(∑)之间的关系通过特定的调用规则来保证它们之间是联系的，而不是单独且割裂的。

M-GEP中将染色体之间的关系设计为从上到下的调用关系[4]，染色体分别记为C1,C2,…,Ck，k=length(I(∑))，K为染色体的个数，设C1(∑)=(G(1,1),G(1,2),…,G(1,n))，n=length(C1(∑))，n为第一个染色体的基因的总数；C1(∑)的结构说明了其包含的基因数。第二层染色体的终端字符集为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)适应度函数。适应度函数的选取和具体的问题有关，它决定了种群进化的方向，对生成的新种群的质量高低有着决定性的影响[12]，因此根据实际的问题分析找到适合该问题的适应度函数和评价准则是至关重要的。本文中利用M-GEP对可逆逻辑电路进行综合与优化，对基因编码字符串进行遗传操作，利用表达式树与真值表的匹配度和所需可逆逻辑门的数量，判断综合的表达式的真值表和指定的真值表是否完全匹配，以及根据表达式的最简形式判断其生成的电路的门数是否是最少的。

在M-GEP中个体I(∑)的求适应度值I(s)的步骤[4]为：

步骤1分析每个个体的所有染色体所包含的基因，得到计算适应度值所需要的计算资源和操作方法。这些计算形式共同组成一个步骤数组，数组内包括计算操作符，运算操作符，参数在计算过程中需要偏移的量以及结果保存的存放地址等；

步骤2根据每个基因和染色体的计算步骤和需要的计算资源，分配固定长度的计算地址用于存放参数和运算的中间结果以及最终结果，在程序设计中对应的即通过栈的写入和取出来执行参数运算；

步骤3根据训练集或测试用例存放在指定的空间内[4]；

步骤4根据步骤1计算出所需要的资源和步骤数组，针对给定的训练集或测试用例对个体的适应度值进行计算，并将结果存放在栈中。栈的顶部位置一定是最新的中间计算结果或最终的适应度值；

步骤5重复步骤3和步骤4，直到种群内所有的个体的适应度值都求完，即结束适应度的计算；

(4)遗传操作。M-GEP的遗传操作包含选择算子、交叉算子、变异算子、插串算子和染色体算子，染色体算子是M-GEP其独有的算子，是对多基因染色体和多层染色体进行遗传操作的算子。

选择算子的作用对适应度值高的个体进行复制遗传。个体被选中直接复制到下一代是利用轮盘赌的方法进行判断的，适应度值高的个体被选中的概率大，适应度值低的个体被选中的概率小。

交叉算子包含单点交叉算子和多点交叉算子。交叉运算指相互配对的染色体根据交叉概率按照指定的交叉规则交换部分基因的过程。

突变算子是指将基因中的信息进行突变处理。变异算子和交叉算子两者互相配合可以达到对空间的全局搜索和局部搜索。变异算子的作用过程即将原本位置上的基因字符改变成其他的基因字符。

插串算子包含了普通插串算子和根插串算子，插串算子在基因的任意位置开始选择一段字符串，随机的插入到基因头部除第一个位置外的任意位置。根插串的子串选择上不同于普通插串，它从基因的头部任意位置开始查找，遇到第一个函数运算符后，以该位置处为起点随机的选择一段长度的子串作为插串子串，将它插入到基因头部的第一个位置。由于插串算子将子串插入的位置在头部，因此会导致超过头部长度的基因字符被舍弃。

染色体算子包含染色体重组算子Pc和基因随机重组算子Pr[4]。

图2 染色体重组算子操作示意图

图3 基因随机重组算子操作示意图

如图2所示，对与两个需要进行染色体重组的个体，染色体重组算子Pc操作的基本单位是染色体，因此随机的选择个体中的某个或某一层染色体，在染色体上随机的找到一个位置，这个位置即作为染色体重组的起点位置。

如图3所示，基因随机重组算子Pr操作的对象是每个个体中的基因，即它操作的最小单位是基因。在基因随机重组算子作用下，随机的选择个体中的染色体上的基因，同时需要确认选择的基因是在哪一层染色体上。

2 M-GEP算法设计

M-GEP算法[4]执行的具体过程如下：

输入训练集和M-GEP配置。

输出最佳的适应度个体。

//加载配置和种群初始化

Init(StepConfig);

//调用评价函数

DefaultJudge(self,Population);

//循环遗传进化，直到达到最大辈数或找到符合适应度值的个体

While(FCurrentGenaration < FMaxGenaration) do begin

//将适应度排名第一的继承下来

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

//依次进行各项遗传算子操作，如交叉变异，染色体重组等

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

//调用评价函数

DefaultJudge(self,tmpPopulation);

//将结果排序并复制到下一代

Sort(tmpPopulation,Population);

//进化辈数加1

Inc(FCurrentGenaration);

//如果最佳进化结果满足指定条件则退出

if tmpPopulation[0].Score

end;

//返回最佳适应度个体

Result=tmpPopulation[0];

根据M-GEP算法的实现步骤绘制算法流程，如图4所示。

图4 M-GEP算法流程图

3 实验结果分析

将M-GEP运用到可逆逻辑电路的综合与优化时，需要注意在基因编码时，函数运算符集合是{⊕,&,!}，而基因字符集采用大写字母来表示，即为{A,B,C,D…}，根据基因字符串的长度来选择需要的字符。本文采用C语言编程实现了初步的实验，在程序编写时，为方便程序的运行操作，将“ ”代替“ ”进行表示，其他函数运算符不变。主要试验参数如表1所示。

表1 实验参数设置

实验1对于6输入变量的逻辑函数，通过M-GEP算法进行自动搜索最优表达式。随机生成输入的真值表和M-GEP算法计算出的表达式结果和相应的基因编码如图5所示。

图5 6输入变量结果

图6 6输入可逆逻辑网络

实验2加大输入变量的个数，对10输入的变量进行综合，随机生成的真值表和根据M-GEP算法计算出的结果如图7所示。

图7 10输入变量结果

图8 10输入可逆逻辑网络

通过上述试验结果的分析可知，M-GEP算法在进行逻辑表达式化简是可行的，且在缺乏复杂的知识背景的情况下，可以综合出理想的结果。相比较于遗传算法[13]、遗传编程[14]和基因表达式编程[15]，M-GEP的编码可以简单也可以根据实际问题改变的更为复杂，但由于有染色体之间的调用关系，使得可以通过不复杂的基因编码在进化的过程中实现复杂的功能的作用，如实验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].北京:国防工业出版社,1999.

[14] 吉根林.遗传算法研究综述[J].计算机应用与软件,2004,21(2):69-73.

[15] 夏凯祥,赵曙光,方聪,等.面向可逆逻辑综合的GEP算法设计与实现[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);上海市教委科研创新重点项目(14ZZ068)

赵曙光(1965-)，男，博士，教授。研究方向：进化电路设计。罗霄(1990-)，男，硕士研究生。研究方向：可逆逻辑综合等。

10.16180/j.cnki.issn1007-7820.2017.11.002