ISSN 
-
自十九世纪30年代开始就有学者发现并意识到布尔匹配和布尔分类在开关电路中扮演着重要角色，人们开始从各个方面研究电路的设计与优化[1-3]。布尔等价分类和等价匹配作为电路设计和电路优化中的重要技术，逐渐被更多的学者研究[4-5]。
对布尔函数输入或输出的置换运算称为P操作，对输入或输出的非运算称为N操作。根据对布尔函数输入和输出执行P操作和N操作的组合，可产生N变换、P变换、NP变换和NPN变换等，也由此形成了布尔函数的P等价匹配、NP等价匹配和NPN等价匹配。其中NPN等价匹配研究较多，第一个N表示输入非，P表示输入置换，第二个N表示输出非。给定一个
$ n $ 输入布尔函数，其NPN变换共有$ n!{2^{n + 1}} $ 个，采用穷尽法进行匹配，其复杂度是$ O(n!{2^{n + 1}}) $ 。因此，布尔函数的NPN等价分类和匹配是NP难问题。当前，NPN等价分类中n的最大值是10[6]。在数字电路的技术映射和工艺库绑定中，布尔函数NPN等价匹配是一个必要环节，其目的是为当前设计的电路找到一个最优的替代电路[7]。现有的布尔函数NPN等价匹配方法主要集中在成对比较法、基于正规式和基于SAT的方法[8-12]。除此之外，还存在一些基于Walsh谱特征和学习的方法[13-15]。
本文基于对香农扩展定理代数余子式运算的研究发现：1)布尔函数的变量在NP变换中其对称性和独立性不变；2)独立变量具有相位不确定性；3)利用独立变量区分其他变量的不可用性。利用这些特性首先能更早地判定两个布尔函数的不等价性，其次能有效地减少匹配中产生的候选正规式分支数量，从而减少匹配算法的空间复杂度，提高匹配速度。
-
令X是一个
$ n $ 维布尔向量$ ({x_0},{x_1}, \cdots ,{x_{n - 1}}) $ ，布尔函数$ f({\boldsymbol{X}}) $ 表示为$ f({\boldsymbol{X}}):{B^n} \to B $ ，$ f({\boldsymbol{X}}) $ 是一个不含无关项的布尔函数。定义 1 N变换：将一个非操作
$ \varphi $ 作用在$ n $ 维布尔向量$ {\boldsymbol{X}} = ({x_0},{x_1}, \cdots ,{x_{n - 1}}) $ 上，$ {{\boldsymbol{X}}^\varphi }({x_0},{x_1}, \cdots ,{x_{n - 1}}) = (x_0^{\varphi (0)},x_1^{\varphi (1)}, \cdots ,x_{n - 1}^{\varphi (n - 1)}) $ 。当$ \varphi (i) = 1 $ 时，$ x_i^{\varphi (i)} = {x_i} $ ；当$ \varphi (i) = 0 $ 时，$ x_i^{\varphi (i)} = {\overline x _i} $ 。若
$ {\boldsymbol{X}} = (0,1,1,0) $ ，$ {\boldsymbol{\varphi }} = (0,0,1,1) $ ，那么$ {{\boldsymbol{X}}}^{{\boldsymbol{\varphi }}} = (1,0,1,0) $ 。定义 2 P变换：将一个置换操作
$ \pi $ 作用在$ n $ 维布尔向量$ {\boldsymbol{X}} = ({x_0},{x_1}, \cdots ,{x_{n - 1}}) $ 上，$ {{\boldsymbol{X}}_{\boldsymbol{\pi }}}({x_0},{x_1}, \cdots ,{x_{n - 1}}) = ({x_{\pi (0)}},{x_{\pi (1)}}, \cdots ,{x_{\pi (n - 1)}}) $ ，其中$ \pi (i) = j $ 且$ i,j \in \{ 0,1, \cdots , n - 1\} $ 。若
$ {\boldsymbol{X}} = ({x_0},{x_1},{x_2},{x_3}) = (0,1,0,1) $ ，$ {\boldsymbol{\pi }} = (1,3,2,0) $ ，那么$ {{\boldsymbol{X}}_{\boldsymbol{\pi }}}({x_0},{x_1},{x_2},{x_3}) = ({x_1},{x_3},{x_2},{x_0}) = (1,{\text{1}},{\text{0}},0) $ 。定义 3 NP变换：将一个N变换
$ {\boldsymbol{\varphi }}$ 和P变换$ {\boldsymbol{\pi }}$ 先后作用在向量$ {\boldsymbol{X}} = ({x_0},{x_1}, \cdots ,{x_{n - 1}}) $ 上，作用的变换记为$ T $ ，变换$ T $ 作用到布尔向量X上有$ T{\boldsymbol{X}} = X_{\boldsymbol{\pi }}^{\boldsymbol{\varphi }}({x_0},{x_1}, \cdots ,{x_{n - 1}}) = (x_{\pi (0)}^{\varphi (0)},x_{\pi (1)}^{\varphi (1)}, \cdots ,x_{\pi (n - 1)}^{\varphi (n - 1)}) $ 。若
$ {\boldsymbol{X}} = ({x_0},{x_1},{x_2},{x_3}) = (0,1,1,1) $ ，$ {\boldsymbol{\varphi}} = (0,0,1,1) $ ，${\boldsymbol{ \pi }} = (3,0,2,1) $ ，$ T{\boldsymbol{X}} = (1,1,1,0) $ 。定义 4 NPN等价：给定两个布尔函数
$ f({\boldsymbol{X}}) $ 和$ g({\boldsymbol{X}}) $ ，当且仅当存在一个NP变换$ T $ 使得条件$ f(T{\boldsymbol{X}}) = g({\boldsymbol{X}}) $ 或$ f(T{\boldsymbol{X}}) = \overline {g({\boldsymbol{X}})} $ 成立，那么$ f({\boldsymbol{X}}) $ 与$ g({\boldsymbol{X}}) $ 是NPN等价的，记为$ f({\boldsymbol{X}}) \cong g({\boldsymbol{X}}) $ [9]。香农扩展定理：等式
$ f(x) = {x_i}{f_{{x_i}}} + \overline x {}_i{f_{{{\overline x }_i}}} $ 。该等式也称为香农分解，其中
$ {f_{{x_i}}} = f[{x_i} \leftarrow 1] $ 和$ {f_{{{\overline x }_i}}} = f[{x_i} \leftarrow 0] $ 称为香农代数余子式，其中$ {f_{{x_i}}} $ 简记为$ {f_1} $ ，$ {f_{{{\overline x }_i}}} $ 简记为$ {f_0} $ 。如一个
$ n $ 变量布尔函数$ f({\boldsymbol{X}}) $ 通过$ {x_i}{x_j} $ 香农分解后变为4个$ n - 2 $ 变量布尔函数的或，也就是$ f({\boldsymbol{X}}) = {x_i}{x_j}{f_{{x_i}{x_j}}} + {x_i}{\overline x _j}{f_{{x_i}{{\overline x }_j}}} + {\overline x _i}{x_j}{f_{{{\overline x }_i}{x_j}}} + {\overline x _i}{\overline x _j}{f_{{{\overline x }_i}{{\overline x }_j}}} $ 。因此，若两个布尔函数是NP等价的，那么利用NP变换中的变量进行香农分解，依次分解后的布尔函数也一定是NP等价的。
定义 5 布尔差分：布尔函数
$ f({\boldsymbol{X}}) $ 关于变量$ {x_i} $ 的布尔差分是$ \dfrac{{\partial f}}{{\partial {x_i}}} = {f_{{x_i}}} \oplus {f_{{{\overline x }_i}}} $ ，记为$ f_{{x_i}}' $ [10]。定义 6 k阶通用特征：给定一个
$ n $ 变量布尔函数$ f({\boldsymbol{X}}) $ ，令$ b = x_{{i_1}}^{\varphi ({i_1})}x_{{i_2}}^{\varphi ({i_2})} \cdots x_{{i_k}}^{\varphi ({i_k})} $ ，有$ n - k $ 变量香农代数余子式$ {f_b} $ ，$ |{f_b}| $ 是布尔函数$ {f_b} $ 的最小项个数，$ |{f_b}| $ 称为布尔函数$ f({\boldsymbol{X}}) $ 的$ k $ 阶通用特征[1]。布尔函数
$ f({\boldsymbol{X}}) $ 真值表中最小项个数称为0阶特征，记为$ |f| $ 。若$ b = {x_0} $ ，$ |{f_{{x_0}}}| $ 是$ f({\boldsymbol{X}}) $ 的1阶通用特征；若$ b = {x_0}{\overline x _1} $ ，则$ |{f_{{x_0}{{\overline x }_1}}}| $ 是$ f({\boldsymbol{X}}) $ 的2阶通用特征。因此，$ n $ 变量布尔函数$ f({\boldsymbol{X}}) $ 具有$ k(1 \leqslant k \leqslant n) $ 阶特征$ {2^k}C_n^k $ 个。定义 7 布尔差分特征：布尔函数
$ f({\boldsymbol{X}}) $ 关于变量$ {x_i} $ 的布尔差分特征是布尔函数$ f_{{x_i}}' $ 的最小项个数，记为$ |f_{{x_i}}'| $ [7]。定义 8 变量对称：布尔函数
$ f({\boldsymbol{X}}) $ 的两个变量$ {x_i} $ 和$ {x_j}/{\overline x _j} $ 是对称的，当$ {x_i} $ 和$ {x_j}/{\overline x _j} $ 交换后$ f({\boldsymbol{X}}) $ 不变，即$ f( \cdots ,{x_i}, \cdots ,{x_j}, \cdots ) = f( \cdots ,{x_j}{\text{/}}{\overline x _j}, \cdots ,{x_i}, \cdots ) $ [1]。根据香农代数余子式可以判定变量对称，当
$ {f_{01}} \oplus {f_{10}} = 0 $ 时，变量$ {x_i} $ 与$ {x_j} $ 对称；当$ {f_{00}} \oplus {f_{11}} = 0 $ 时，变量$ {x_i} $ 与$ {\overline x _j} $ 对称[16]。定义 9 独立变量：布尔函数
$ f({\boldsymbol{X}}) $ 的变量$ {x_i} $ 是独立变量当且仅当$ |f_{{x_i}}'| = 0 $ [7]。 -
NPN等价分类将
$ n $ 变量布尔函数划分为多个等价类，每个等价类中的所有布尔函数相互是NPN等价的，即它们之间均可相互转换。在上述等价类中选择一个布尔函数作为该类的代表，该代表称为正规式。基于正规式的布尔匹配更多应用于工艺库绑定。对某个电路函数$ f({\boldsymbol{X}}) $ 进行工艺库绑定，即在工艺库中寻找合适的基元实现该电路，通过计算$ f({\boldsymbol{X}}) $ 的正规式并使用哈希查找快速实现[1]。令由m个NPN等价布尔函数构成的等价类
$ E = \{ {f_0}({\boldsymbol{X}}),{f_1}({\boldsymbol{X}}), \cdots ,{f_{m - 1}}({\boldsymbol{X}})\} $ ，对$ \forall i,j \in \{ 0,1, \cdots , m - 1\} $ 都有$ {f_i}({\boldsymbol{X}}) \cong {f_j}({\boldsymbol{X}}) $ ，从$ E $ 中选择一个布尔函数作为该等价类的正规式，记为$ F({\boldsymbol{X}}) $ 。基于正规式的布尔函数NPN等价匹配可描述为：给定两个布尔函数
$ f({\boldsymbol{X}}) $ 和$ g({\boldsymbol{X}}) $ ，它们的正规式分别为$ F({\boldsymbol{X}}) $ 和$ G({\boldsymbol{X}}) $ ，若有$ F({\boldsymbol{X}}) = G({\boldsymbol{X}}) $ ，则有$ f({\boldsymbol{X}}) \cong g({\boldsymbol{X}}) $ 。 -
根据对香农分解代数余子式运算的研究，本文得出在布尔函数NP等价变换中具有以下6个属性。
1) 布尔函数
$ f({\boldsymbol{X}}) $ 中的对称变量$ {x_i} $ 经过NP变换转换为变量$ {x_j}/{\overline x _j} $ ，转换后变量仍为对称变量。2) 若变量
$ {x_i} $ 与变量$ {x_j} $ 对称，经NP变换后为$ x_k^{\varphi (k)} $ 和$ x_l^{\varphi (l)} $ ，$ x_k^{\varphi (k)} $ 和$ x_l^{\varphi (l)} $ 是对称的。3) 若布尔函数
$ f({\boldsymbol{X}}) $ 有独立变量$ {x_i} $ ，那么必有等式$ |{f_{{x_i}}}| = |{f_{{{\overline x }_i}}}| $ 。证明：因为
$ {x_i} $ 与$ f({\boldsymbol{X}}) $ 无关，必有$ {f_{{x_i}}} = {f_{{{\overline x }_i}}} $ ，所以$ |{f_{{x_i}}}| = |{f_{{{\overline x }_i}}}| $ 。4) 若布尔函数
$ f({\boldsymbol{X}}) $ 有独立变量$ {x_i} $ ，其他非独立变量$ {x_j} $ 和$ {x_k} $ ，并有$ (|{f_{{x_j}}}|,|{f'_{{x_j}}}|) = (|{f_{{x_k}}}|,|{f'_{{x_k}}}|) $ ，那么有$ (|{f_{{x_i}{x_j}}}|,|{f'_{{x_i}{x_j}}}|) = (|{f_{{x_i}{x_k}}}|,|{f'_{{x_i}{x_k}}}|) $ 。证明：因变量
$ {x_i} $ 与$ f({\boldsymbol{X}}) $ 是独立的，$ {x_i} $ 与布尔函数$ {f_{{x_j}}} $ 和$ {f_{{x_k}}} $ 也必然是独立的，如果有$ (|{f_{{x_j}}}|,|{f'_{{x_j}}}|) = (|{f_{{x_k}}}|,|{f'_{{x_k}}}|) $ ，那么必有$ (|{f_{{x_i}{x_j}}}|,|{f'_{{x_i}{x_j}}}|) = (|{f_{{x_i}{x_k}}}|,|{f'_{{x_i}{x_k}}}|) $ 。5) 若布尔函数
$ f({\boldsymbol{X}}) $ 有独立变量$ {x_i} $ ，有$ b = x_{{i_1}}^{\varphi ({i_1})} x_{{i_2}}^{\varphi ({i_2})} \cdots x_{{i_k}}^{\varphi ({i_k})}(i \ne {i_1},{i_2}, \cdots ,{i_k}) $ ，则有$ |{f_{b{x_i}}}| = |{f_{b{{\overline x }_i}}}| $ 。证明：因为
$ {x_i} $ 对$ f({\boldsymbol{X}}) $ 是独立的，那么对$ {f_b} $ 也必是独立的，那么必有$ {f_{b{x_i}}}{\text{ = }}{f_{b{{\overline x }_{\text{i}}}}} $ ，所以有$ |{f_{b{x_i}}}| = |{f_{b{{\overline x }_i}}}| $ 。6) 布尔函数
$ f({\boldsymbol{X}}) $ 中的独立变量$ {x_i} $ 经过NP变换后，独立性不变。如有3变量布尔函数
$ f({\boldsymbol{X}}) = {x_1}{x_2} + {\overline x _1}{\overline x _2} $ ，若有N变换$ {\boldsymbol{\varphi }} = (0,0,1) $ 和P变换$ {\boldsymbol{\pi }}=(2，0，1) $ ，$ f({\boldsymbol{X}}) $ 中有独立变量$ {x_0} $ 且经过变换$ {x_0} $ 变换为$ {\overline x _2} $ ，$ f(T{\boldsymbol{X}}) = {\overline x _0}{x_1} + {x_0}{\overline x _1} $ ，明显$ f(T{\boldsymbol{X}}) $ 中有独立变量$ {x_2} $ 。充分条件：根据属性1)、属性2)和属性6)可知，若两个布尔函数
$ f({\boldsymbol{X}}) $ 和$ g({\boldsymbol{X}}) $ 是NP等价的，那么这两个布尔函数的变量具有相同的对称变量结构和独立变量结构。因此，可通过上述充分条件先比较两个布尔函数变量的结构，尽早确定不等价情况。
-
文献[1]提出了基于高阶通用特征的匹配算法，0～n阶特征构成高阶通用特征向量，且NP等价类中具有最大特征向量的布尔函数作为正规式，证明了每个布尔函数具有唯一的由0～n阶特征值组成的特征向量
$ {{\boldsymbol{V}}}^{f}=(0阶特征, 1阶特征,\cdots ,n阶特征) $ ，其中0阶特征1个，$ m $ 阶特征有$ C_n^m $ 个。利用特征向量计算正规式：按照0阶特征、1阶特征、···、n阶特征顺序计算布尔函数的通用特征，每计算完一次特征后，根据特征值的大小对变量进行排序，从而找出在某个或某几个排序下使特征向量值最大的情况，最后所得排序就是一个能将布尔函数转换为对应正规式的NP变换，再根据该NP变换计算出相应的正规式。在文献[1]的基础上，文献[7]提出了DC(difference and cofactor)特征向量增加了布尔差分特征，这样能够更加快速地找到布尔函数所在等价类中具有最大DC特征向量的正规式。
定义 10 DC特征给定一个
$ n $ 变量布尔函数$ f({\boldsymbol{X}}) $ ，令$ b = x_{{i_1}}^{\varphi ({i_1})}x_{{i_2}}^{\varphi ({i_2})} \cdots x_{{i_k}}^{\varphi ({i_k})} $ ，有$ n - k $ 变量香农代数余子式$ {f_b} $ 和布尔差分$ f_b' $ ，$ (|{f_b}|,|f_b'|) $ 称为布尔函数$ f({\boldsymbol{X}}) $ 的$ k $ 阶($ k = 1,2, \cdots ,n $ )DC特征[7]。本文将延续使用DC特征向量[7]，利用NP变换时变量变换前后对称性与独立性不变的属性，独立变量的属性3)、4)、5)和6)，加快正规式的计算，从而提高布尔函数NPN等价匹配速度。
-
本文将布尔函数的变量分为3类：独立变量、对称变量和非对称变量。在计算布尔函数正规式的过程中，根据变量的类型和DC特征值进行分组。具有相同DC特征值的变量为一组，每组根据变量类型分为独立变量类、对称变量类和非对称变量类。当所有的组都是“已解决”状态，产生一个候选NP变换。上述3类变量所在组处于“已解决”状态需满足的条件为：
1) 非对称变量，变量相位确定且所在组就一个非对称变量；
2) 对称变量，变量相位确定且所在组只有一个对称类，无其他对称类和非对称变量；
3) 独立变量，因独立变量的布尔差分特征值为0，即使有其他对称变量与其具有相同的通用特征值，但布尔差分特征值一定不同，直接标记“已解决”。
加快匹配的关键方法为：
1) 给定两个布尔函数
$ f({\boldsymbol{X}}) $ 和$ g({\boldsymbol{X}}) $ ，首先计算他们的0阶特征、1阶DC特征，判断所有变量的对称性和独立性，并根据以上结果对两个布尔函数的变量进行分组。2) 根据上面的计算结果，比较两个布尔函数的变量是否具有相同的结构，即相同的0阶特征、1阶DC特征、对称变量结构和独立变量结构。如果
$ f({\boldsymbol{X}}) $ 和$ g({\boldsymbol{X}})/\overline {g({\boldsymbol{X}})} $ 具有相同结构再分别计算它们的正规式$ F({\boldsymbol{X}}) $ 和$ G({\boldsymbol{X}}) $ ，若等式$ F({\boldsymbol{X}}) = G({\boldsymbol{X}}) $ 成立，则NPN等价，否则不等价。3) 分别利用本文所提出的独立变量所具有的属性3)、属性4)和属性5)，能更好地减少计算正规式过程中的搜索空间，具体步骤为：
① 在计算特征值的过程中独立变量的相位始终无法确定。若布尔函数具有独立变量，必有一个对称类且只有独立变量。在计算候选正规式的过程中一定会产生两个分支[1,7]，分别尝试同相对称和反相对称，所需探测的正规NP变换数增加1倍。本文直接将独立变量标记为正相且“已解决”。
② 在文献[1,7]的算法中使用“已解决”的变量来计算“未解决”变量的高阶特征值，以期“未解决”变量能够获得不同的高阶特征值而变为“已解决”。
假设有已解决非独立变量
$ {x_j} $ 和独立变量组$ \{ {x_{{i_1}}},{x_{{i_2}}}, \cdots ,{x_{{i_k}}}\} $ ，因为独立变量组的相位不定，因此需要通过变量$ {x_j} $ 计算$ |{f_{{x_j}{x_{{i_1}}}}}| $ 和$ |{f_{{x_j}{{\overline x }_{{i_1}}}}}| $ 来确定独立变量的相位。根据属性5)可知，无论计算多少次都无法确定独立变量相位，增加了不必要的计算，本算法直接将独立变量相位设置为正向，解决了该问题。③ 同样，参考文献[1,7]的算法，利用独立变量去解决其他“未解决”的变量，以期用独立变量对“未解决”变量计算高阶特征值，从而使这些“未解决”的变量得以“解决”。
假设有独立变量组
$ \{ {x_{{i_1}}},{x_{{i_2}}}, \cdots ,{x_{{i_k}}}\} $ 和未解决的一个变量组$ \{ {x_{{j_1}}},{x_{{j_2}}}, \cdots ,{x_{{j_m}}}\} $ ，且变量$ {x_{{j_1}}},{x_{{j_2}}}, \cdots ,{x_{{j_m}}} $ 均为非对称变量。先根据独立变量组产生两个分支，一分支为同相对称，一个分支为反相对称[1,7]。即两个分支都分别利用独立变量$ {x_{{i_1}}} $ 对变量$ {x_{{j_1}}},{x_{{j_2}}}, \cdots ,{x_{{j_m}}} $ 计算其更高阶特征或DC特征。变量$ {x_{{j_1}}},{x_{{j_2}}}, \cdots ,{x_{{j_m}}} $ 之所以没有“解决”是因为这些变量具有一样的DC特征值。以正相为例，文献[7]计算二阶特征值$ (|{f_{{x_{{i_1}}}{x_{{j_1}}}}}|, |{f'_{{x_{{i_1}}}{x_{{j_1}}}}}|),(|{f_{{x_{{i_1}}}{x_{{j_2}}}}}|,|{f'_{{x_{{i_1}}}{x_{{j_2}}}}}|), \cdots ,(|{f_{{x_{{i_k}}}{x_{{j_k}}}}}|,|{f'_{{x_{{i_k}}}{x_{{j_k}}}}}|) $ ，根据属性4)，必然有$ (|{f_{{x_{{i_1}}}{x_{{j_1}}}}}|,|{f'_{{x_{{i_1}}}{x_{{j_1}}}}}|) {\text{ = }} (|{f_{{x_{{i_1}}}{x_{{j_2}}}}}|,|{f'_{{x_{{i_1}}}{x_{{j_2}}}}}|) {\text{ = }} \cdots {\text{ = }} (|{f_{{x_{{i_k}}}{x_{{j_k}}}}}|,|{f'_{{x_{{i_k}}}{x_{{j_k}}}}}|) $ ，增加了不必要的计算。根据属性4)，本算法不使用独立变量计算后面组的高阶特征。利用属性3)、4)或5)，本文对于独立变量所在的组直接标记为“已解决”，针对具有独立变量的布尔函数NPN等价匹配，可降低空间复杂度50%。
例1：布尔函数
$ f = {x_1}{x_3} + {\overline x _1}{\overline x _3} + {x_3}{x_4}{\text{ + }}{\overline x _3}{\overline x _4} $ ，计算一阶DC特征向量和对称变量检测，${{\boldsymbol{V}}_f} = \left\{ \left( {10,10,0} \right), \left( {12,8,12} \right),\left( {10,10,0} \right),\left( {8,12,12} \right),\left( {8,12,12} \right) \right\}$ ，对称检测得到两个对称类，$ \{ {x_1},{\overline x _{\text{3}}},{\overline x _{\text{4}}}\} $ 和$ {{\{ }}{x_{\text{0}}},{x_2}{\text{\} }} $ ，其中$ {{\{ }}{x_{\text{0}}},{x_2}{\text{\} }} $ 又是独立变量类。因此产生两组$ {G_1} = {{\{ }}{x_1},{\overline x _{\text{3}}},{\overline x _{\text{4}}}{\text{\} }} $ ，$ {G_{\text{2}}} = {{\{ }}{x_{\text{0}}},{x_2}{\text{\} }} $ ，根据上述“已解决”的判断，这里$ {G_1} $ 和$ {G_{\text{2}}} $ 都“已解决”，获得排序$ \{ {x_1},{\overline x _3},{\overline x _4},{x_0},{x_2}\} $ ，直接得到正规式$F({\boldsymbol{X}}) = {x_0}{\overline x _3} + {\overline x _0}{x_3} + {x_0}{x_2} + {\overline x _0}{\overline x _2}$ 。例1中如果不考虑本文方法，那么需要利用变量
$ {x_1} $ 计算$ {x_{\text{0}}} $ 和$ {x_2} $ 的二阶特征，其目的是获得这两个变量的相位，结果一定是相位不确定，因此产生两个排序$ \{ {x_1},{\overline x _3},{\overline x _4},{x_0},{x_2}\} $ 和$ \{ {x_1},{\overline x _3},{\overline x _4},{x_0},{\overline x _2}\} $ 。 -
本算法采用树形结构存储计算正规式过程中产生的候选正规式，利用树的深度优先搜索实现。当第m个组之前的所有组已经解决且都无法解决后续尚未“解决”的组；同时，第m个组需要分为p种情况，这时都将产生p个分支。本文通过上述的关键方法减少分支数，以提高匹配速度。
函数Initial()用来计算布尔函数f和g的0阶特征、1阶DC特征值、对称性、独立性、相位信息和初始分组信息，伪代码如下。
Procedure 1 Initial Boolean Variable
Function Initial(
$ f $ )Input:
$ f $ Output:
$ {{\boldsymbol{V}}_f} $ Compute 0st signature
$ |f| $ of$ f $ Compute 1st DC signature
$ {{\boldsymbol{V}}_f} $ of fDetermine the phase of
$ \left(x_{0}, x_{1}, \cdots, x_{n-1}\right) $ of$ f $ Check the independent variables of
$ f $ Check the symmetric variables of
$ f $ Update
$ {{\boldsymbol{V}}_f} $ k=group(
$ {{\boldsymbol{V}}_f} $ ) //分组Return
$ {{\boldsymbol{V}}_f} $ End function
函数Canonical()用来计算布尔函数的最大正规变换，伪代码如下。
Procedure 2 Compute the Maximum Transformation
Function Canonical(
$ f,{{\boldsymbol{V}}_f},k $ )Input:
$ f,{{\boldsymbol{V}}_f},k $ Output:
$ {M_f} $ If (E1) //如果获得一个候选变换
If (Empty(
$ {M_f} $ ))$ {M_f} $ =TElse
If (
$ {{\boldsymbol{V}}^{{M_f}}} < {V^T} $ )$ {M_f} $ =TEnd if
End if
Else
For all
$ {G_i},i \in \{ 1,2, \cdots ,k\} $ doIf (E2)//如果所有组都“已解决”
break
End if
End for
If (i==k+1)
return
$ {M_f} $ Else
If (E3) //如果
$ {G_i} $ “已解决”Add the variable of
$ {G_i} $ to CT_ListUpdate
$ {{\boldsymbol{V}}_f} $ k=k+1
Canonial(
$ f,{{\boldsymbol{V}}_f},k $ )Else
For all
$ {G_i},i \in \{ 1,2, \cdots ,m\} $ doSplit
$ {G_i} $ Create node_list
End For
For all node_j in node_list do
Update (node_j, group)
k=k+1
If (E1)then
If (Empty(
$ {M_f} $ ))$ {M_f} $ =TElse
If (
$ {{\boldsymbol{V}}^{{M_f}}} < {V^T} $ )$ {M_f} $ =TEnd if
End if
Else
Add the variables in
$ {G_i} $ to CT_listUpdate_signature(
$ f $ )m=group(
$ {{\boldsymbol{V}}_f} $ )Canonical(
$ f,{\rm{CT}}\_{\rm{List}},{\rm{group}},k $ )End if
End for
End if
End if
End if
return
$ {M_f} $ End function
给定两个n变量布尔函数
$ f $ 和$ g $ ，算法先分别调用Initial()计算它们的初始特征向量和变量结构，如果变量结构相同再分别调用Canonical()函数计算它们两个的正规变换，最后计算正规式F和G，如果F=G成立，那么布尔函数f和g是NPN等价的。其中，当出现$ |f| = |g| = {2^{n - 1}} $ 时，处理方法同文献[1]。 -
基于MCNC标准电路库中电路和随机生成电路的布尔函数，对本文提出的算法和文献[1]中的基于高阶通用特征的算法进行了测试、比较和验证。测试环境配置为3.3 GHz CPU、8 GB RAM。
表 1 MCNC标准库电路NPN等价匹配结果
n AVG/s A.T/个 AVG[1]/s A.T[1]/个 7 0.00024 1.7 0.00215 66.7 8 0.00591 20.0 0.00989 27.1 9 0.00108 2.1 0.00163 3.0 10 0.00067 1.5 0.00098 2.1 11 0.00138 1.7 0.00283 3.2 12 0.00112 1.6 0.00177 2.7 13 0.01932 5.0 0.04242 7.8 14 0.00507 1.5 0.00713 2.1 15 0.01834 1.7 0.02730 2.4 16 0.01601 1.8 0.02380 2.9 17 0.12548 1.9 0.18872 2.8 18 0.14111 1.8 0.21707 4.4 19 0.68186 1.5 1.13960 3.4 20 1.34587 2.6 1.90159 3.8 21 4.34512 1.3 7.12478 2.0 22 9.30826 2.1 13.95470 4.5 表1为对MCNC标准电路库中电路的布尔函数NPN等价匹配的实验结果，表2为随机生成电路的布尔函数NPN等价匹配的结果。两表中的第1列是变量个数，第2～3列和4～5列是本文和文献[1]算法的匹配平均时间(AVG)和平均候选正规变换数(A.T)。
根据表1中的实验结果可以看出，本文算法对MCNC标准电路库中电路的布尔函数的匹配速度比文献[1]提升了40.1%，搜索空间减少了42.1%。根据表2可以看出本文算法对随机电路的布尔函数匹配速度比文献[1]提升了51%，搜索空间减少75.4%。可以NPN等价匹配对随机电路的布尔函数匹配速度提升更高，其原因是随机产生电路的布尔函数中具有独立变量的情况更多一些。
通过实验可以看出，本文算法能够大大减少计算正规式过程中的搜索空间，并大幅提高了布尔函数匹配速度。
表 2 随机生成电路NPN等价匹配结果
n AVG/s A.T/个 AVG[1]/s A.T[1]/个 7 0.00020 5.4 0.0007 13.2 8 0.00031 4.2 0.0009 22.1 9 0.00055 4.7 0.0010 16.8 10 0.00033 2.8 0.0013 19.6 11 0.00164 3.2 0.0032 19.1 12 0.00372 3.1 0.0068 12.5 13 0.00342 2.9 0.0099 17.2 14 0.00496 3.0 0.0097 14.8 15 0.00352 3.1 0.0078 16.5 16 0.01053 3.8 0.0249 13.9 17 0.01646 4.5 0.0326 23.4 18 0.02117 3.8 0.0423 13.3 19 0.08473 4.2 0.1565 15.8 20 0.07691 4.4 0.1195 12.5 21 0.05598 3.7 0.0859 13.3 22 0.09480 5.4 0.1349 18.3 -
本文通过对布尔函数香农分解代数余子式运算的研究，得出6个有利于布尔匹配的属性。利用这些属性提出了更有效的基于正规式的NPN布尔匹配算法，有效减少了算法的搜索空间和提高了布尔函数NPN等价匹配的速度。该算法能够更好地应用到电路设计和优化中去，具有一定的应用价值。如何解决布尔函数在最坏情况下的NPN等价匹配难题，是下一步的研究难点。
A Boolean Function NPN Equivalent Matching Algorithm Based on Canonical Form
-
摘要: 通过对香农分解代数余子式的运算研究，发现了对称变量和独立变量在NP等价变换中的6个属性，充分利用变量的对称性和独立性NP变换后的不变性、独立变量相位不确定性、在NP匹配中独立变量识别其他变量和其他变量识别独立变量的不可用性，提出了一种基于正规式的布尔函数NPN等价匹配算法。通过对大量MCNC标准电路库中电路和随机生成电路的7-22变量布尔函数的匹配实验，在两个实验电路集上本文算法与基于高阶通用特征匹配算法相比，匹配过程中的搜索空间平均减少了58.8%、布尔匹配的速度提高了45.6%，能够为电路优化和电路映射提供更加快速和有效的布尔匹配。Abstract: By studying the operation of the cofactor of Shannon decomposition, six attributes of symmetric variables and independent variables in NP equivalent transformation are found. By making full use of the invariance of the symmetry and independence of variables after NP transformation, the phase uncertainty of independent variables, the unavailability of both independent variables to identify other variables and other variables to identify independent variables in the process of matching, we propose an NPN equivalent matching algorithm based on canonical form. We performed matching experiments on the 7-22 variable Boolean functions of a large number of MCNC benchmark circuits and randomly generated circuits.. The experimental results show that the algorithm of this paper reduces the search space in the matching process by 58.8% and increases matching speed by 45.6% on the two experimental circuit sets compared with the algorithm based on higher order general signature. This indicates that the algorithm of this paper can provide faster and more effective Boolean matching for circuit optimization and circuit mapping.
-
Key words:
- Boolean difference /
- canonical form /
- NPN equivalence /
- independent variable /
- Shannon decomposition
-
表 1 MCNC标准库电路NPN等价匹配结果
n AVG/s A.T/个 AVG[1]/s A.T[1]/个 7 0.00024 1.7 0.00215 66.7 8 0.00591 20.0 0.00989 27.1 9 0.00108 2.1 0.00163 3.0 10 0.00067 1.5 0.00098 2.1 11 0.00138 1.7 0.00283 3.2 12 0.00112 1.6 0.00177 2.7 13 0.01932 5.0 0.04242 7.8 14 0.00507 1.5 0.00713 2.1 15 0.01834 1.7 0.02730 2.4 16 0.01601 1.8 0.02380 2.9 17 0.12548 1.9 0.18872 2.8 18 0.14111 1.8 0.21707 4.4 19 0.68186 1.5 1.13960 3.4 20 1.34587 2.6 1.90159 3.8 21 4.34512 1.3 7.12478 2.0 22 9.30826 2.1 13.95470 4.5 
下载: 导出CSV
表 2 随机生成电路NPN等价匹配结果
n AVG/s A.T/个 AVG[1]/s A.T[1]/个 7 0.00020 5.4 0.0007 13.2 8 0.00031 4.2 0.0009 22.1 9 0.00055 4.7 0.0010 16.8 10 0.00033 2.8 0.0013 19.6 11 0.00164 3.2 0.0032 19.1 12 0.00372 3.1 0.0068 12.5 13 0.00342 2.9 0.0099 17.2 14 0.00496 3.0 0.0097 14.8 15 0.00352 3.1 0.0078 16.5 16 0.01053 3.8 0.0249 13.9 17 0.01646 4.5 0.0326 23.4 18 0.02117 3.8 0.0423 13.3 19 0.08473 4.2 0.1565 15.8 20 0.07691 4.4 0.1195 12.5 21 0.05598 3.7 0.0859 13.3 22 0.09480 5.4 0.1349 18.3
下载: 导出CSV
-
[1] ABDOLLAHI A, PEDRAM M. Symmetry detection and Boolean matching utilizing a signature-based canonical form of Boolean functions[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(6): 1128-1137. doi: 10.1109/TCAD.2008.923256 [2] CHEN K C, YANG C Y. Boolean matching algorithms[J]. International Symposium on VLSI Technology Systems and Applications Proceedings, 1993(1): 44-48. [3] LUO Q B, LI X Y, YANG G W. Quantum circuit implementation of S-box for SM4 cryptographic algorithm[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(6): 820-826. [4] ZHANG Y, YANG G W, HUNG W, et al. Computing affine equivalence classes of Boolean functions by group isomorphism[J]. IEEE Transactions on Computers, 2016, 65(12): 3606-3616. doi: 10.1109/TC.2016.2557329 [5] JOHNSTON F E. The theory of group representations[M]. Maryland, Baltimore: The Johns Hopkins University Press, 1938. [6] ZHANG J L, YANG G W, HUNG W, et al. A group algebraic approach to NPN classification of Boolean functions[J]. Theory of Computing Systems, 2019, 63: 1278-1297. doi: 10.1007/s00224-018-9903-0 [7] ZHANG J L, YANG G W, HUNG W, et al. A canonical-based NPN Boolean matching algorithm utilizing Boolean difference and cofactor signature[J]. IEEE Access, 2017, 5: 27777-27785. doi: 10.1109/ACCESS.2017.2778338 [8] ABDOLLAHI A. Signature based Boolean matching in the presence of don’t cares[C]//Design Automation Conference Proceedings. Anaheim: [s. n. ], 2008: 642-647. [9] 张菊玲, 杨国武, 吴尽昭, 等. 基于对称及特征的NPN布尔匹配算法[J]. 电子科技大学学报, 2018, 47(6): 876-881. ZHANG J L, YANG G W, WU J Z, et al. NPN Boolean matching algorithm based on symmetry and signature[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(6): 876-881. [10] ZHANG J L, YANG G W, HUNG W, et al. A new pairwise NPN Boolean matching algorithm based on structural difference signature[J]. Symmetry, 2019, 11(1): 27. [11] SAFARPOUR S, VENERIS A, BAECKLER G, et al. Efficient SAT-based Boolean matching for FPGA technology mapping[C]//Design Automation Conference Proceedings. San Francisco: [s. n. ], 2006: 466-471. [12] WANG X Q, YANG Y. New approach of exploiting symmetry in SAT-based Boolean matching for FPGA technology mapping[C]//IEEE International Conference on Vehicular Electronics and Safety Proceedings. Dongguan: IEEE, 2013: 282-285. [13] MUZIO J, MILLER D M, HURST S L. Number of spectral coefficients necessary to identify a class of Boolean functions[J]. Electronics Letters, 2007, 18(13): 577-578. [14] THORNTON M A, DRECHSLER R, GUNTHER W. Logic circuit equivalence checking using Haar spectral coefficients and partial BDDs[J]. VLSI Design, 2014, 14(1): 53-64. [15] LAI C F, JIANG J, WANG K H, et al. Boolean matching of function vectors with strengthened learning[C]//IEEE/ACM International Conference on Computer-Aided Design Proceedings. San Jose: IEEE, 2010: 596-601. [16] ZHANG J S, CHRZANOWSKAJESKE M, MISHCHENKO A, et al. Linear cofactor relationships in Boolean functions[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(6): 1011-1023. doi: 10.1109/TCAD.2005.855951 -
