不完全规定函数的启发式ESOP最小化算法

卜登立

(1. 井冈山大学 电子与信息工程学院, 江西 吉安 343009；2. 流域生态与地理环境监测国家测绘地理信息局重点实验室, 江西 吉安 343009)

0 引 言

RM(Reed-Muller)逻辑是基于“与-异或”的逻辑表示， 和基于“与-或”的布尔逻辑相比， 其在算术、 通信、 校验电路等方面具有面积优势[1]， 并且能够实现具有通用测试集的可测试性电路设计[2]， 近年来在信息安全领域的电路设计中也得到了应用[3]， 因此RM逻辑受到了越来越广泛的关注.

积之异或和(Exclusive-or Sum of Products, ESOP)是最一般化的混合极性RM逻辑表示， 它对变量的出现形式没有任何限制， 相对于其他形式的RM逻辑， 其能够获得更为精简的表示， 更有助于降低电路实现开销， 因此被作为一种逻辑模型应用于纳电子电路设计中[4]， 通过对ESOP进行优化实现相应电路的优化. 另外， 由于其能够较为直接地映射到可逆电路中， 因此ESOP表示模型被广泛应用于可逆电路综合[5-6]， 即先由exorcism算法[7]产生ESOP覆盖， 然后再将乘积项映射到可逆门网络.

降低ESOP的复杂度， 有助于降低使用ESOP作为逻辑模型电路的面积[4]， 也有助于降低采用ESOP表示模型进行综合所得可逆电路的量子成本[6]， 因此ESOP最小化成为电路综合中一个非常重要的步骤. 当前也有一些ESOP最小化的研究工作， 如文献[4]结合极性转换和局部变换启发式地优化ESOP逻辑， 文献[8]通过细分立方体进行ESOP的精确最小化， 文献[9]提出了通过检查ESOP多项式包含乘积项数的上限和下限对搜索空间进行剪枝的精确ESOP最小化算法， 以及广泛应用于可逆电路综合中生成ESOP覆盖的exorcism算法[7]. 这些方法和算法均假设函数是完全规定函数， 然而当前的电路设计方法常常不满足这个假设， 为降低设计成本经常需要重用事先设计好的电路模块， 这导致很多函数是包含大量外部无关项的不完全规定函数[10]. 对于不完全规定函数， 如果恰当地对无关项进行赋值， 能够进一步降低其ESOP的复杂度[11]， 从而降低电路开销. 由于ESOP具有指数级的优化空间， 再加上不完全规定函数ESOP的优化空间随无关最小项数量的增加呈指数级增长， 使得不完全规定函数的精确ESOP最小化算法时间效率非常低. 如文献[11]算法在进行输入变量数为6的不完全规定函数的ESOP最小化时就需要若干个小时， 导致其实用性较差， 并且无法应用于输入数较多的不完全规定函数. 文献[12]给出了一种不完全规定函数的MPRM(Mixed polarity RM)展开式最小化算法. MPRM展开式可以看作是ESOP逻辑的一种特例， 与MPRM展开式相比， ESOP逻辑有可能获得更为精简的表示. 因此有必要研究不完全规定函数的启发式ESOP最小化算法， 并将其适用于具有较多输入数的不完全规定函数.

本文采用不完全规定函数的立方体表示， 提出一种边实施无关项赋值边进行化简的启发式ESOP最小化算法. 该算法根据立方体间的邻近关系， 采用前瞻策略在RM域动态实施无关项赋值， 并结合Exorlink运算[7]和回溯策略进行ESOP最小化. 最后， 使用一组MCNC(Microelectronic Center of North China)不完全规定函数对所提算法进行了验证.

1 理论基础

1.1 不完全规定函数及其ESOP逻辑

定义 1 不完全规定函数g∶{0,1}n→{0,1,-}， 函数输出值为“1”的最小项集合为ON集， 输出值为“0”的最小项集合为OFF集， 输出值为“-”的最小项为无关(don’t care, DC)项， 所有无关项构成DC集.

根据定义1， 可将不完全规定函数g所有的最小项划分为3个集合F,D和R， 分别表示该函数的ON集、 DC集和OFF集，F∩D=Ø，F∩R=Ø，D∩R=Ø.

对于无关项的赋值没有进行规定， 可以取0也可以取1， 不会影响函数g的逻辑功能[13]. 可根据需要将无关项赋值为0或者1， 从而形成不完全规定函数的不同实现.

定义 2 假设集合H⊆D， 即H为DC集的子集， 通过将H中的无关项赋值为1， 将差集DH中的无关项赋值为0， 那么由ON集Fy=F∪H和OFF集Ry=R∪(DH)构成的完全规定布尔函数y是函数g的一个实现， 记作g→y.

对于由定义2得到的完全规定布尔函数y， 由于其ON集Fy=F∪H， 因此可将y分解为2个布尔函数y=f+h， 函数f和函数h的ON集分别为F和H.

定义 3 假设完全规定函数f的ESOP为fe， 那么f与fe功能等价， 记作f↔fe.

对于输入变量数为n的布尔函数f， 其ESOP逻辑可以表示为

定理 1 假设函数f的ESOP为fe， 函数h的ESOP为he， 函数y=f+h的ESOP为ye， 那么有fe⊕he↔ye， g→fe⊕he， 即fe⊕he为不完全规定函数g的ESOP.

证明 根据定义2可知集合H是将集合D一个子集中的所有无关项均赋值为1的结果， 由于F∩D=Ø， 故F∩H=Ø， 因此y=f+h=f⊕h. 由于f↔fe， h↔he， 因此y=f⊕h↔fe⊕he， 而y↔ye， 故fe⊕he↔ye. 又因为g→y， 所以g→fe⊕he.

根据定义2， 当H=Ø， 即将不完全规定函数g的集合D中所有无关项均赋值0， 此时完全规定函数y的ON集Fy=F，OFF集Ry=R∪D. 将这种特殊情况下所得到的完全规定布尔函数记为y0， 由定理1可以得到如下推论.

推论 1 假设完全规定布尔函数y0的ESOP为y0,e， 那么g→y0,e.

本文根据定义2, 3和定理1所描述的函数之间的逻辑关系， 启发式地确定集合H， 得到函数y， 然后对y进行ESOP最小化， 从而得到不完全规定函数g的近优ESOP, 目的是希望通过无关项赋值来降低ESOP的复杂度.

1.2 立方体表示

对于n-输入/m-输出的多输出布尔函数， 可以使用立方体表示乘积项. 采用位置标记法的立方体表示为

c=[ci,co],

式中： 输入部分ci=[c0,c1,…,cn-1]； 输出部分co=[cn,cn+1,…,cn+m-1].cj∈{0,1,-}， 对于ci， 分别表示相应变量xj以反变量形式、 原变量形式出现以及不出现在乘积项中； 对于co， 则表示ci对应的乘积项分别为函数第j-n(n≤j≤n+m-1)个输出的OFF, ON和DC乘积项. 对于ci， 如果cj∈{0,1}， 则称cj为立方体中的一个文字(literal).

假设n≤j≤n+m-1， 如果∀j,cj=0， 则记作co=0.

定义 4 对于立方体c， 如果∀j(n≤j≤n+m-1)， 有cj∈{0,1}， 则称之为完全规定立方体， 如果co=0则称之为OFF立方体， 如果完全规定立方体c的co≠0则称之为ON立方体； 如果∀j(n≤j≤n+m-1)， 有cj∈{0,-}， 且∃j,cj=-， 则称之为DC立方体.

根据定义4， 不完全规定函数的ON集F由所有ON立方体构成， OFF集R则由所有OFF立方体构成， DC集则由所有DC立方体构成， 并且F∩D=Ø，F∩R=Ø，D∩R=Ø.

对于一个表示多输出函数的立方体集合C， 如果∀c∈C均为完全规定立方体， 那么该函数为完全规定函数. 如果∃c∈C为DC立方体， 那么该函数为不完全规定函数.

定义 5 对于两个完全规定的立方体a和b，ao∧bo=[an∧bn,…,an+m-1∧bn+m-1]， 其中“∧”表示逻辑与， 由于此时aj,bj∈{0,1}(n≤j≤n+m-1)， 因此“∧”的运算规则为0∧0=0， 0∧1=0， 1∧1=1.

当且仅当∀j(n≤j≤n+m-1)，aj=bj时，ao=bo. 而立方体a和b间的距离定义为

1.3 Exorlink运算

立方体变换是将满足某种关系的一组立方体在不改变其逻辑含义的前提下进行组合变形， 经常被用来实现函数的化简[4]. Exorlink运算[7]是立方体变换的扩展， 根据立方体间的邻近关系， 依次与相邻的立方体进行连接， 从而减少乘积项数或文字数. 距离为1或2立方体间的Exorlink运算根据式(1)所示的规则进行.

(1)

由式(1)可知， 如果D(a,b)=1且aj,bj≠-， 实施a和b之间的Exorlink运算可以减少乘积项数， 也可以看作将b和a归并， 并使a中的文字数减少1. 如果D(a,b)=2， 虽然实施a和b之间的Exorlink运算不能减少乘积项数， 但如果条件

Ca,b=(ao∧bo≠Ø)∧(aj≠bj)∧

(ak≠bk)∧(aj,ak,bj,bk≠-)

2 不完全规定函数的ESOP最小化

本文采用立方体表示法， 使用exorcism算法中的Exorlink运算并结合前瞻策略与回溯策略进行不完全规定函数的ESOP最小化. 先由不完全规定函数的ON集F借助exorcism算法得到ESOP覆盖(立方体集合)G； 然后采用前瞻策略启发式地实施无关项赋值， 确定集合H， 并得到其ESOP覆盖He； 再借助Exorlink运算对G∪He进行ESOP最小化， 并对不能降低ESOP复杂度的无关项赋值采用回溯策略进行回溯.

2.1 启发式无关项赋值

已知DC立方体c和ESOP覆盖G中的立方体a， 采用前瞻策略的启发式无关项赋值是根据“实施c和a间的Exorlink运算对ESOP复杂度所产生影响”的先验知识来决定是否将c作为ON立方体(即将c中的无关项赋值为1)加入到G. 如果D(a,c)=1且aj,bj≠-， 根据式(1)可知， 实施a和c间的Exorlink运算， 可以将c和a归并， 并使立方体a中的文字数减少1， 能够降低ESOP的复杂度， 因此将c作为ON立方体加入到G， 并实施c和a间的Exorlink运算， 以便在降低ESOP复杂度的同时也为后续的无关项赋值产生距离为1的立方体. 由于G在无关项赋值过程中是动态变化的， 因此无关项赋值是动态实施的.

为区分DC立方体与G中的非DC立方体， 对立方体a设置DC标志wa， 如果wa=1表明a是DC立方体， 如果wa=0则表明a是非DC立方体.

算法1所示的lookahead判断将DC立方体c作为ON立方体加入到G对降低ESOP复杂度是否有帮助， 如果确定有帮助或者可能有帮助则返回非0值， 否则返回0值. 算法1体现了本文的前瞻策略.

算法 1lookahead(s,c,G,D)

1)t←0;

2) for eacha∈Gandwa=0 andao∧co≠0{

3) if (s=1 andD(a,c)=2 andCa,c=true) {

4)t←t+1;

5) } else if(D(a,c)=1) {∥假设al≠cl(0≤l≤n-1)

6) ifao=co{

7) if (al≠- andcl≠-) return 2;

8) else if (s=1) return 3;}

9)} else if (D(a,c)=0) {

10) if (ao=co) {

11)G←G{a},D←D{c};

12) return 1; }

13) else return 2; } }

14) if (s=1 andt>1) return 3;

15) return 0.

算法lookahead搜索ESOP覆盖G中是否存在与不相交DC集D(D中的立方体两两不相交)中的立方体c满足所指定条件的立方体， 如果存在则返回非0值. 其中G←G{a}表示从集合G中删除立方体a，D←D{c}也有类似的含义.

参数s控制搜索的行为， 如果s=0， 则仅判断将无关项赋值为1是否能够确定降低ESOP的复杂度， 如步骤7)和步骤9)～13). 对于步骤7)， 由于D(a,c)=1,ao=co,al≠-且cl≠-， 根据式(1)可知将c作为ON立方体加入到G并实施a和c间的Exorlink运算能够减少a中的文字数. 在步骤9)～13)中， 如果D(a,c)=0且ao=co， 则说明将c作为ON立方体加入到G并实施a和c间的Exorlink运算可使ESOP减少一个立方体(立方体a被消除)； 如果ao≠co， 由于步骤2)中限定了ao∧co≠0， 因此实施a和c间的Exorlink运算能够使ao中的1数减少， 从而可以减少函数某些输出所包含的乘积项数.

如果s=1， 则还需判断将c作为ON立方体加入到G是否有降低ESOP复杂度的可能， 如步骤8)和步骤14). 对于步骤8)， 尽管D(a,c)=1且ao=co， 但是当al=-或cl=-时， 将c作为ON立方体并实施a和c间的Exorlink运算仅能够使立方体a中输入变量xl的出现形式发生变化(例如当al=1,cl=-时， 实施a和c间的Exorlink运算将使al=0，xl的出现形式由正极性变为负极性)， 虽不能确定降低ESOP的复杂度， 但是有可能使覆盖G中立方体间的距离发生变化， 在进行后续的ESOP化简时， 有可能降低ESOP的复杂度. 对于步骤14)， 其中的t由步骤3)和步骤4)决定. 步骤3)表明立方体a和c间的距离为2且条件Ca,c为真， 将c作为ON立方体并实施a和c间的Exorlink运算虽然能够使立方体a和c中的文字数均减少1， 但由于立方体c的加入却使ESOP增加了一个立方体. 由于立方体a文字数的减少和立方体c的加入， 将使覆盖G中立方体间的距离发生变化， 从而在进行后续的ESOP化简时， 也有可能降低ESOP的复杂度， 因此如果在覆盖G中存在着多个与立方体c间满足距离为2且条件Ca,c为真的立方体时返回非0值.

2.2 ESOP最小化算法

算法2所示的dc_min是不完全规定函数ESOP最小化算法的主体部分， 通过启发式地实施无关项赋值， 将满足条件的DC立方体通过无关项赋值作为ON立方体加入到ESOP覆盖G后， 对G中距离为1的立方体实施Exorlink运算， 降低ESOP的复杂度， 并对覆盖G使用Exorlink运算进行ESOP化简， 对能够降低ESOP复杂度的无关项赋值进行确认， 对于那些不能有效降低ESOP复杂度的无关项赋值， 则采用回溯策略进行回溯.

算法 2dc_min(s,G,D)

1) do {

2)u←0;

3) for eachc∈D{

4)z←lookahead(s,c,G,D);

5) ifz≥2 {

6)G←G∪{c},D←D{c};

7)linkd1cubes(G); }

8)u←u+z;}

9) if(u>0)iterativelinks(G);

10) }until(u=0);

11) for eacha∈G{

12) if (wa=1) {

13)G←G{a},D←D∪{a};}}

在算法2中， 步骤7)的linkd1cubes对ESOP覆盖G中距离为1的立方体a和b实施Exorlink运算， 如果a或b的DC标志为1， 则将其DC标志清零， 确认无关项赋值. 步骤9)中的iterativelinks则采用Exorlink运算迭代地对ESOP覆盖G进行化简， 直至进行Exorlink运算无法降低ESOP覆盖G的复杂度为止[7]， 如果G中DC标志为1的立方体能够减少立方体数或文字数， 则将其DC标志清零， 确认无关项赋值. 步骤11)～13)是算法dc_min中的无关项赋值回溯策略， 即将覆盖G中DC标志为1的立方体删除， 并将之重新添加至DC覆盖D， 因为通过无关项赋值将这些立方体作为ON立方体不能降低ESOP的复杂度.

由算法1和算法2可以看出， 本文将无关项赋值结合到了ESOP的化简过程中， 因此无关项赋值是在RM域内实施的， 并且实现了边实施无关项赋值边进行ESOP化简. 下面给出不完全规定函数的启发式ESOP最小化算法.

算法 3 启发式ESOP最小化算法

1) 解析逻辑网表, 得到其ON集F和DC集D;

2) 对D实施不相交锐积运算, 使其成为不相交覆盖;

3) 将集合F作为输入, 使用GenerateInitialEsopCover得到初始ESOP覆盖G;

4) 使用exorcism算法中的ReduceEsopCover对G进行化简;

5)dc_min(0,G,D);

6)dc_min(1,G,D);dc_min(0,G,D);

7) 算法结束, 覆盖G为不完全规定函数g的近优ESOP覆盖.

由于算法3的步骤2)中通过不相交锐积运算使D成为不相交覆盖(D中的立方体两两不相交)， 因此D也可以视为ESOP覆盖D. 步骤3)中的GenerateInitialEsopCover使用exorcism算法[7]中的ESOP初始覆盖生成方法获得ESOP初始覆盖， 步骤4)则使用exorcism算法中的ReduceEsopCover[7]对G进行化简. 步骤5)和步骤6)动态获得H， 并对G∪H进行ESOP化简. 由于D是不相交覆盖， 而H⊆D， 因此H也是不相交覆盖， 也可视为ESOP覆盖He， 根据1.1节的分析， 可知算法3结束时的G为不完全规定函数的ESOP覆盖.

3 算法验证及结果分析

文中算法采用C语言实现， 并在Linux操作系统下使用gcc编译器进行编译. 在配置为Intel Core i3-2350M CPU 6GB RAM的个人计算机上对12个不同规模的MCNC不完全规定函数进行ESOP最小化， 并分别与exorcsim算法[7]的结果以及文献[12]算法的结果进行比较， 其中文献[12]算法也采用C语言实现.

分别使用exorcism算法和算法3对不完全规定函数进行ESOP最小化， 并统计算法结果ESOP的立方体数和文字数， 结果如表 1 所示. 其中的“I/O”表示函数的“输入/输出数”， “改进”是指相对于exorcism算法的结果， 算法3结果的立方体数以及文字数分别减少的百分比. 在使用exorcism算法进行ESOP最小化时， 采用了“-q 2”选项.

表 1 与exorcism算法结果比较

由表 1 可以看出， 与exorcism算法的结果相比， 对于绝大多数不完全规定函数， 算法3均能减少其ESOP的立方体数和文字数， 最大分别减少了10.53%和14.49%(函数fout)， 有2个函数(dk48和mark1)， 尽管不能减少立方体数， 但却能够减少文字数. 从总体角度看， 对于这些不完全规定函数， 本文算法3使其ESOP的立方体数减少了4.15%， 文字数减少了4.86%， 这验证了本文算法的有效性.

由于文献[12]算法是针对单输出函数进行最小化， 为与之进行比较， 在对不完全规定的多输出函数进行ESOP最小化时， 将多输出函数视为多个单输出函数分别进行最小化， 然后分别统计各个单输出函数ESOP结果的立方体数之和(总立方体数)以及文字数之和(总文字数)， 结果如表 2 所示.

表 2 与文献[12]算法结果比较

由表 2 可以看出， 与文献[12]算法相比， 在将多输出函数视为多个单输出函数进行ESOP最小化时， 本文算法3能够有效减少其ESOP的总立方体数和总文字数. 从表2最后一行的总体角度看， 与文献[12]算法相比， 对于这些不完全规定函数， 本文算法3使其ESOP的立方体数减少了44.37%， 文字数减少了48.46%， 这进一步验证了本文算法的有效性. 从时间角度看， 虽然对输入数小于20的函数， 文献[12]算法具有较高的时间效率， 但是对于输入数大于或等于20的函数(bcd和mark1)而言， 本文算法具有更高的时间效率， 特别是对于函数bcd. 相对于文献[12]算法， 本文算法所需时间降低了3个数量级之多， 这说明本文算法对于输入数较多的不完全规定函数具有更好适用性.

综上所述， 本文算法能够减少不完全规定函数ESOP的立方体数以及文字数， 能够适用于输入数较多的不完全规定函数， 既适用于单输出函数， 也适用于多输出函数.

4 结 论

ESOP因其紧凑的表示形式在可测试性电路设计、 纳电子电路设计与优化以及可逆电路综合中得到了较为广泛的应用. 对于不完全规定函数， 合理的无关项赋值有助于降低ESOP的复杂度， 从而有利于降低采用ESOP作为模型所实现电路的开销. ESOP最小化问题本身就具有指数级的复杂度， 并且不完全规定函数ESOP的优化空间又随着无关最小项的增加呈指数级增长， 需要研究不完全规定函数的启发式ESOP最小化算法. 本文根据不完全规定函数与其完全规定函数实现之间的逻辑关系以及立方体间的邻近关系， 提出了一种在RM域边实施无关项赋值边进行ESOP化简的不完全规定函数ESOP最小化算法. 使用不完全规定函数对所提算法进行验证的结果表明， 所提算法能够减少不完全规定函数ESOP的立方体数和文字数， 并且适用于输入数较多的不完全规定函数.

[1]卜登立, 江建慧. 基于对偶逻辑的混合极性RM电路极性转换和优化方法[J]. 电子学报, 2015, 43(1): 79-85. Bu Dengli, Jiang Jianhui. Dual logic based polarity conversion and optimization of mixed polarity RM circuits[J]. Acta Electronica Sinica, 2015, 43(1)： 79-85. (in Chinese)

[2]Rahaman H, Das D K, Bhattacharya B B. Testable design of AND-EXOR logic networks with universal test sets[J]. Computers and Electrical Engineering, 2009, 35(5)： 644-658.

[3]Monteiro C, Takahashi Y, Sekine T. Low-power secure S-box circuit using charge-sharing symmetric adiabatic logic for advanced encryption standard hardware design[J]. IET Circuits, Devices & Systems, 2015, 9(5)： 362-369.

[4]卜登立. 快速启发式ESOP电路面积优化算法[J]. 计算机辅助设计与图形学学报, 2015, 27(11)： 2161-2168. Bu Dengli. Fast heuristic area optimization algorithm for ESOP circuits[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(11)： 2161-2168. (in Chinese)

[5]Shafaei A, Saeedi M, Pedram M. Cofactor sharing for reversible logic synthesis[J]. ACM Journal on Emerging Technologies in Computing Systems, 2014, 11(2)： 1-21.

[6]Datta K, Gokhale A, Sengupta I, et al. An ESOP-based reversible circuit synthesis flow using simulated annealing[J]. Applied Computation and Security Systems, 2015, 305： 131-144.

[7]Mishchenko A, Perkowski M. Fast heuristic minimization of exclusive-sums-of-products[C]. Proceedings of the 5th Reed-Muller Workshop, Mississippi, 2001： 241-249.

[8]张巧文, 汪鹏君, 胡江. 基于分层超立方体的精确ESOP最小化[J]. 计算机辅助设计与图形学学报, 2016, 28(1)： 172-179. Zhang Qiaowen, Wang Pengjun, Hu Jiang. Exact minimization of ESOP expressions based on hierarchical hypercube[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(1)： 172-179. (in Chinese)[9]Hirayama T, Nishitani Y. Exact minimization of AND-EXOR expressions of practical benchmark functions[J]. Journal of Circuits, Systems, and Computers, 2009, 18(3)： 465-486.

[10]Chang K H, Bertacco V, Markov I L, et al. Logic synthesis and circuit customization using extensive external don’t-cares[J]. ACM Transactions on Design Automation of Electronic Systems, 2010, 15(3)： 1-26.

[11]Sampson M, Kalathas M, Voudouris D, et al. Exact ESOP expression for incompletely specified functions[J]. Integration, the VLSI Journal, 2012, 45(2)： 197-204.

[12]汪迪生, 汪鹏君. 包含无关项的MPRM展开式最小化算法[J]. 浙江大学学报(理学版), 2014, 41(1)： 38-42. Wang Disheng, Wang Pengjun. Algorithm about minimization of MPRM expansions including don’t care terms[J]. Journal of Zhejiang University(Science Edition), 2014, 41(1)： 38-42. (in Chinese)

[13]Brand D, Bergamaschi R A, Stok L. Don’t cares in synthesis： theoretical pitfalls and practical solutions[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998, 17(4)： 285-304.