张菊玲，郭文强，杨晓梅，朱义鑫，杨国武
(1. 新疆财经大学信息管理学院 乌鲁木齐 830012；
2. 电子科技大学计算机科学与工程学院 成都 611731；
3. 电子科技大学大数据研究中心 成都 611731)
自十九世纪30 年代开始就有学者发现并意识到布尔匹配和布尔分类在开关电路中扮演着重要角色，人们开始从各个方面研究电路的设计与优化[1-3]。布尔等价分类和等价匹配作为电路设计和电路优化中的重要技术，逐渐被更多的学者研究[4-5]。
对布尔函数输入或输出的置换运算称为P 操作，对输入或输出的非运算称为N 操作。根据对布尔函数输入和输出执行P 操作和N 操作的组合，可产生N 变换、P 变换、NP 变换和NPN 变换等，也由此形成了布尔函数的P 等价匹配、NP 等价匹配和NPN 等价匹配。其中NPN 等价匹配研究较多，第一个N 表示输入非，P 表示输入置换，第二个N 表示输出非。给定一个n输入布尔函数，其NPN 变换共有n!2n+1个，采用穷尽法进行匹配，其复杂度是O(n!2n+1)。因此，布尔函数的NPN 等价分类和匹配是NP 难问题。当前，NPN 等价分类中n的最大值是10[6]。
在数字电路的技术映射和工艺库绑定中，布尔函数NPN 等价匹配是一个必要环节，其目的是为当前设计的电路找到一个最优的替代电路[7]。现有的布尔函数NPN 等价匹配方法主要集中在成对比较法、基于正规式和基于SAT 的方法[8-12]。除此之外，还存在一些基于Walsh 谱特征和学习的方法[13-15]。
本文基于对香农扩展定理代数余子式运算的研究发现：1)布尔函数的变量在NP 变换中其对称性和独立性不变；
2)独立变量具有相位不确定性；
3)利用独立变量区分其他变量的不可用性。利用这些特性首先能更早地判定两个布尔函数的不等价性，其次能有效地减少匹配中产生的候选正规式分支数量，从而减少匹配算法的空间复杂度，提高匹配速度。
1.1 基本概念
1.2 正规式
NPN 等价分类将n变量布尔函数划分为多个等价类，每个等价类中的所有布尔函数相互是NPN等价的，即它们之间均可相互转换。在上述等价类中选择一个布尔函数作为该类的代表，该代表称为正规式。基于正规式的布尔匹配更多应用于工艺库绑定。对某个电路函数f(X)进行工艺库绑定，即在工艺库中寻找合适的基元实现该电路，通过计算f(X)的正规式并使用哈希查找快速实现[1]。
令由m个NPN 等价布尔函数构成的等价类E={f0(X),f1(X),···,fm−1(X)}， 对∀i,j∈{0,1,···,m−1}都有fi(X)≅fj(X)， 从E中选择一个布尔函数作为该等价类的正规式，记为F(X)。
基于正规式的布尔函数NPN 等价匹配可描述为：给定两个布尔函数f(X)和g(X)，它们的正规式 分 别 为F(X)和G(X)， 若 有F(X)=G(X)，则 有f(X)≅g(X)。
2.1 布尔函数NP 变换中变量的属性
根据对香农分解代数余子式运算的研究，本文得出在布尔函数NP 等价变换中具有以下6 个属性。
6) 布尔函数f(X)中 的独立变量xi经过NP 变换后，独立性不变。
如有3 变量布尔函数f(X)=x1x2+x1x2，若有N 变换φ =(0,0,1) 和 P 变换π =(2，0，1)，f(X)中有独立变量x0且 经过变换x0变换为x2，f(T X)=x0x1+x0x1， 明显f(T X)中 有独立变量x2。
充分条件：根据属性1)、属性2)和属性6)可知，若两个布尔函数f(X)和g(X)是NP 等价的，那么这两个布尔函数的变量具有相同的对称变量结构和独立变量结构。
因此，可通过上述充分条件先比较两个布尔函数变量的结构，尽早确定不等价情况。
2.2 本文使用的正规式
文献[1]提出了基于高阶通用特征的匹配算法，0～n阶特征构成高阶通用特征向量，且NP 等价类中具有最大特征向量的布尔函数作为正规式，证明了每个布尔函数具有唯一的由0～n阶特征值组成的特征向量Vf=(0阶特征,1阶特征,···,n阶特征)，其中0 阶特征1 个，m阶 特征有Cnm个。利用特征向量计算正规式：按照0 阶特征、1 阶特征、···、n阶特征顺序计算布尔函数的通用特征，每计算完一次特征后，根据特征值的大小对变量进行排序，从而找出在某个或某几个排序下使特征向量值最大的情况，最后所得排序就是一个能将布尔函数转换为对应正规式的NP 变换，再根据该NP 变换计算出相应的正规式。
在文献[1]的基础上，文献[7]提出了DC(difference and cofactor)特征向量增加了布尔差分特征，这样能够更加快速地找到布尔函数所在等价类中具有最大DC 特征向量的正规式。
本文将延续使用DC 特征向量[7]，利用NP 变换时变量变换前后对称性与独立性不变的属性，独立变量的属性3)、4)、5)和6)，加快正规式的计算，从而提高布尔函数NPN 等价匹配速度。
2.3 加快匹配的关键方法
本文将布尔函数的变量分为3 类：独立变量、对称变量和非对称变量。在计算布尔函数正规式的过程中，根据变量的类型和DC 特征值进行分组。具有相同DC 特征值的变量为一组，每组根据变量类型分为独立变量类、对称变量类和非对称变量类。当所有的组都是“已解决”状态，产生一个候选NP 变换。上述3 类变量所在组处于“已解决”状态需满足的条件为：
1) 非对称变量，变量相位确定且所在组就一个非对称变量；
2) 对称变量，变量相位确定且所在组只有一个对称类，无其他对称类和非对称变量；
3) 独立变量，因独立变量的布尔差分特征值为0，即使有其他对称变量与其具有相同的通用特征值，但布尔差分特征值一定不同，直接标记“已解决”。
加快匹配的关键方法为：
1) 给定两个布尔函数f(X)和g(X)，首先计算他们的0 阶特征、1 阶DC 特征，判断所有变量的对称性和独立性，并根据以上结果对两个布尔函数的变量进行分组。
2) 根据上面的计算结果，比较两个布尔函数的变量是否具有相同的结构，即相同的0 阶特征、1 阶DC 特征、对称变量结构和独立变量结构。如果f(X)和g(X)/g(X)具有相同结构再分别计算它们的正 规 式F(X)和G(X)， 若 等 式F(X)=G(X)成 立，则NPN 等价，否则不等价。
3) 分别利用本文所提出的独立变量所具有的属性3)、属性4)和属性5)，能更好地减少计算正规式过程中的搜索空间，具体步骤为：
① 在计算特征值的过程中独立变量的相位始终无法确定。若布尔函数具有独立变量，必有一个对称类且只有独立变量。在计算候选正规式的过程中一定会产生两个分支[1,7]，分别尝试同相对称和反相对称，所需探测的正规NP 变换数增加1 倍。本文直接将独立变量标记为正相且“已解决”。
② 在文献[1,7]的算法中使用“已解决”的变量来计算“未解决”变量的高阶特征值，以期“未解决”变量能够获得不同的高阶特征值而变为“已解决”。
③ 同样，参考文献[1,7]的算法，利用独立变量去解决其他“未解决”的变量，以期用独立变量对“未解决”变量计算高阶特征值，从而使这些“未解决”的变量得以“解决”。
利用属性3)、4)或5)，本文对于独立变量所在的组直接标记为“已解决”，针对具有独立变量的布尔函数NPN 等价匹配，可降低空间复杂度50%。
例1：布尔函数f=x1x3+x1x3+x3x4+x3x4，计算一阶DC 特征向量和对称变量检测，Vf={(10,10,0),(12,8,12),(10,10,0),(8,12,12),(8,12,12)}，对称检测得到两个对称类， {x1,x3,x4}和 {x0,x2}， 其中{x0,x2}又是独立变量类。因此产生两组G1={x1,x3,x4}，G2={x0,x2}，根据上述“已解决”的判断，这里G1和G2都 “已解决”，获得排序 {x1,x3,x4,x0,x2}，直接得到正规式F(X)=x0x3+x0x3+x0x2+x0x2。
例1 中如果不考虑本文方法，那么需要利用变量x1计 算x0和x2的二阶特征，其目的是获得这两个变量的相位，结果一定是相位不确定，因此产生两个排序{x1,x3,x4,x0,x2} 和{x1,x3,x4,x0,x2}。
2.4 匹配算法
本算法采用树形结构存储计算正规式过程中产生的候选正规式，利用树的深度优先搜索实现。当第m个组之前的所有组已经解决且都无法解决后续尚未“解决”的组；
同时，第m个组需要分为p种情况，这时都将产生p个分支。本文通过上述的关键方法减少分支数，以提高匹配速度。
函数Initial()用来计算布尔函数f和g的0 阶特征、1 阶DC 特征值、对称性、独立性、相位信息和初始分组信息，伪代码如下。
函数Canonical()用来计算布尔函数的最大正规变换，伪代码如下。
给定两个n变量布尔函数f和g，算法先分别调用Initial()计算它们的初始特征向量和变量结构，如果变量结构相同再分别调用Canonical()函数计算它们两个的正规变换，最后计算正规式F和G，如果F=G成立，那么布尔函数f和g是NPN 等价的。其中，当出现 |f|=|g|=2n−1时，处理方法同文献[1]。
基于MCNC 标准电路库中电路和随机生成电路的布尔函数，对本文提出的算法和文献[1]中的基于高阶通用特征的算法进行了测试、比较和验证。测试环境配置为3.3 GHz CPU、8 GB RAM。
表1 为对MCNC 标准电路库中电路的布尔函数NPN 等价匹配的实验结果，表2 为随机生成电路的布尔函数NPN 等价匹配的结果。两表中的第1 列是变量个数，第2～3 列和4～5 列是本文和文献[1]算法的匹配平均时间(AVG)和平均候选正规变换数(A.T)。
表1 MCNC 标准库电路NPN 等价匹配结果
根据表1 中的实验结果可以看出，本文算法对MCNC 标准电路库中电路的布尔函数的匹配速度比文献[1]提升了40.1%，搜索空间减少了42.1%。根据表2 可以看出本文算法对随机电路的布尔函数匹配速度比文献[1]提升了51%，搜索空间减少75.4%。可以NPN 等价匹配对随机电路的布尔函数匹配速度提升更高，其原因是随机产生电路的布尔函数中具有独立变量的情况更多一些。
表2 随机生成电路NPN 等价匹配结果
通过实验可以看出，本文算法能够大大减少计算正规式过程中的搜索空间，并大幅提高了布尔函数匹配速度。
本文通过对布尔函数香农分解代数余子式运算的研究，得出6 个有利于布尔匹配的属性。利用这些属性提出了更有效的基于正规式的NPN 布尔匹配算法，有效减少了算法的搜索空间和提高了布尔函数NPN 等价匹配的速度。该算法能够更好地应用到电路设计和优化中去，具有一定的应用价值。如何解决布尔函数在最坏情况下的NPN 等价匹配难题，是下一步的研究难点。
猜你喜欢布尔等价特征向量二年制职教本科线性代数课程的几何化教学设计——以特征值和特征向量为例九江职业技术学院学报(2022年1期)2022-12-02等价转化新高考·高三数学(2022年3期)2022-04-28克罗内克积的特征向量保定学院学报(2022年2期)2022-04-07布尔和比利幽默大师(2019年4期)2019-04-17布尔和比利幽默大师(2019年3期)2019-03-15布尔和比利幽默大师(2018年11期)2018-10-27布尔和比利幽默大师(2018年3期)2018-10-27一类特殊矩阵特征向量的求法许昌学院学报(2018年4期)2018-05-02n次自然数幂和的一个等价无穷大中文信息(2017年12期)2018-01-27EXCEL表格计算判断矩阵近似特征向量在AHP法检验上的应用中华建设(2017年1期)2017-06-07
