2.1.
相位分配
-
给定两个布尔函数$f$和$g$,NPN匹配需要确定对函数的输入非、输入置换和输出非:
1) 输出非:NPN等价的两个布尔函数具有相同或互补的最小项个数。若$|f| = |g|$且$|f| \ne |\overline g |$,$f$无非运算,$f$和$g$同为正相;若$|f| = |\overline g |$且$|f| \ne |g|$,$f$有非运算,$f$为正相g为反相;若$|f| = |\overline g |$且$|f| = |g|$,可能有输出非,可能没有输出非,$f$为正相$g$的相位不定。
2) 输入非:若变量${x_i}$和${x_j}$之间有映射关系,并且它们是同相位的,${x_i}$无非运算;如果它们是相反相位的,${x_i}$有非运算。若$|{f_{{x_i}}}| > |{f_{\overline {{x_i}} }}|$,${x_i}$的相位为正;若$|{f_{{x_i}}}| < |{f_{\overline {{x_i}} }}|$,${x_i}$的相位为反;若$|{f_{{x_i}}}| = |{f_{\overline {{x_i}} }}|$,${x_i}$的相位不能确定。
3) 输入置换:若变量${x_i}$和${x_j}$具有相同的1阶特征,那么它们之间可能存在映射。
满足式(1)时,两个变量是同相;满足式(2)时,两个变量是反相;同时满足式(1)和式(2),两个变量的相位不能确定,相位需要后续判定或同时检测同相和反相两种情况。
2.2.
候选变换搜索
-
给定要匹配的布尔函数$f$和$g$,本算法的目的是找到一个NP变换T,该变换能够将$f$转换为$g$或者$\overline g $。对于任意n变量输入的布尔函数$f$,有$n!{2^{n + 1}}$个NPN变换,但是能够将$f$转换为$g/\overline g $的是少数。本算法通过对称和1阶特征向量搜索在$f$和$g/\overline g $之间可能存在的NP变换,这些变换称为候选变换。每找到一个候选变换就验证该候选变换是否能将$f$转换为$g/\overline g $。
每个候选变换由n个变量映射组成,本算法根据函数$f$和$g$的1阶特征向量及香农分解来搜索它们之间可能存在的NP变换。假设当前搜索函数$f$的变量${x_i}$的映射,有以下几种情况:
1) 函数$g$中只有一个变量${x_j}$与其具有相同的1阶特征,并且变量${x_i}$的相位确定。那么$|{\chi _i}| = 1$,${x_i}$的映射唯一。
2) 函数$g$中只有一个变量${x_j}$与其具有相同的1阶特征,并且变量${x_i}$的相位不确定。那么$|{\chi _i}| = 2$,算法生成映射${x_i} \to {x_j}$和${x_i} \to \overline {{x_j}} $。算法先处理${x_i} \to {x_j}$,如果该映射所生成的NP变换不能将$f$转换为$g/\overline g $,然后再处理${x_i} \to \overline {{x_j}} $。
3) 变量${x_i}$是非对称变量且相位确定,$g$有变量${x_{j1}}, {x_{j2}}, \cdots, {x_{jk}}$与其有相同的1阶特征。那么$|{\chi _i}| = k$,本算法按顺序先生成${x_i}$和${x_{j1}}$之间的映射并处理由此映射所产生的NP变换。如果该NP变换不能将$f$转换为$g/\overline g $,那么算法选取下一个即${x_i}$和${x_{j2}}$之间的映射处理,直到有一个NP变换可以将$f$转换为$g/\overline g $或${\chi _i}$中所有的映射处理完毕。
4) 变量${x_i}$是非对称变量并且相位不确定,$g$中有变量${x_{j1}}, {x_{j2}}, \cdots, {x_{jk}}$与其有相同的1阶特征。那么$|{\chi _i}| = 2k$,算法检测映射集$\{ {x_i} \to {x_{j1}}, {x_i} \to $ $\overline {{x_{j1}}}, {x_i} \to {x_{j2}}, {x_i} \to \overline {{x_{j2}}}, \cdots, {x_i} \to {x_{jk}}, {x_i} \to \overline {{x_{jk}}} \} $,处理方式同步骤3)。
5) 变量${x_i}$是对称变量且相位确定,所在对称类是${S_i} = \{ {x_i}, {x_{i1}}, {x_{i2}}, \cdots, {x_{i(k - 1)}}\} $,$g$中只有一个对称类${S_j} = \{ {x_j}, {x_{j1}}, {x_{j2}}, \cdots, {x_{j(k - 1)}}\} $与${S_i}$具有相同的变量个数和相同的1阶特征。那么$|{\beta _i}| = 1$,算法只需检测由${S_i}$和${S_j}$之间产生的一个种映射关系即可。
6) 变量${x_i}$是对称变量且相位不确定,所在对称类为${S_i} = \{ {x_i}, {x_{i1}}, {x_{i2}}, \cdots, {x_{i(k - 1)}}\} $,函数$g$中只有一个对称类${S_j} = \{ {x_j}, {x_{j1}}, {x_{j2}}, \cdots, {x_{j(k - 1)}}\} $与${S_i}$具有相同的变量个数和相同的1阶特征。令${x_i}$和${x_j}$分别为同相和异相两种情况,在${S_i}$与${S_j}$之间可以产生2组不同映射关系,即$|{\beta _i}| = 2$。算法先处理同相,若同相所产生的NP变换不能将$f$转换为$g/\overline g $,再处理异相。
7) 变量${x_i}$是对称变量且相位确定,所在对称类为${S_i} = \{ {x_i}, {x_{i1}}, {x_{i2}}, \cdots, {x_{i(k - 1)}}\} $,$g$有对称类${S_{j1}}, {S_{j2}}, \cdots, $ ${S_{jk}}$均与${S_i}$具有相同的变量个数和相同的1阶特征。那么${\beta _i} = \{ {S_i} \to {S_{j1}}, {S_i} \to {S_{j2}}, \cdots, {S_i} \to {S_{jk}}\} $,对称类${S_i}$有k组对称映射关系,即$|{\beta _i}| = k$,算法依次处理每一种对称映射关系,直到找到一个NP变换将$f$转换为$g/\overline g $或所有的对称映射关系处理完毕。
8) 变量${x_i}$是对称变量且相位不确定,所在对称类为${S_i} = \{ {x_i}, {x_{i1}}, {x_{i2}}, \cdots, {x_{i(k - 1)}}\} $,$g$有对称类${S_{j1}}, $ ${S_{J2}}, \cdots, {S_{jk}}$均与${S_i}$具有相同的变量个数和相同的1阶特征。那么${\beta _i} = \{ {S_i} \to {S_{j1}}, {S_i} \to {S_{j2}}, \cdots, {S_i} \to {S_{jk}}\} $,由于这些对称类中变量的相位都是不确定的,算法在处理每个对称映射关系时需要考虑正相和反相两种情况,因此对称类${S_i}$有2k组对称映射关系,即$|{\beta _i}| = 2k$。对这2k组对称映射关系的处理方式与情况7相同。
本算法采用树来存储每个变量可能的映射,树中的每个节点是一个变量的一个映射,树共有n层。若第k层只有一个节点,那么该层的变量只有一个映射;如果有多个节点,那么该层的变量有多个可能的映射。这颗树称之为候选变换树,该树的每个分支为一个候选NP变换。本算法采用深度优先搜索方式,只要找到一个满足条件的候选变换,算法就终止。用伪代码描述的候选变换搜索如下:
Procedure 1 Search Transformation
Input data_f, data_g, f, g, map_tree
Output 0 or 1
Function Search(data_f, data_g, f, g, map_tree)
Int min_num=32 768, min;
If D1
Generate a candidate transformation
Return Verify(f, g, map_tree)
Else if compute_vector(f, g, data_f, data_g)=0 then
Return 0
Else
For each xi∈f(X)
|χi/βi|=num(xi, f, g)
If |χi|=1 then
αi→map_tree
Else if |βi|=1
βi→map_tree
Else if |βi|=k1
If (k1 < min_num)
min_num= k1
min=i
End if
Else // |χi|=k2
If(k2 < min_num)
min_num= k2
min=i
End if
End if
End for
If |χi|=1 || |βi|=1
Update data_f, data_g
Search(data_f, data_g, f, g, map_tree)
Else
For each α∈χmin or β∈βmin
α/β→map_tree
Update data_f, data_g
Search(data_f, data_g, f, g, map_tree)
End for
End if
Return 0
End function
Procedure 1中的条件D1表示map_tree是否产生一个完整分支,每产生一个完整分支即生成一个候选变换T,Procedure 1调用verify()验证T。data_f和data_g是由分解变量构成的两个BDD表达式。data_f和data_g的初始值为常量bddtrue,函数Search()每调用一次需要更新data_f和data_g。若第k次调用时的分解变量分别是${x_l}$和${x_p}$,那么data_f=data_fxl, data_g=data_gxp。然后,Procedure 1调用compute_vector()更新变量的1阶特征并判断两个1阶特征向量是否相等,如果不相等则返回0。
2.3.
匹配算法
-
NPN布尔匹配可描述如下:给定两个布尔函数$f({\mathit{\boldsymbol{X}}})$和$g({\mathit{\boldsymbol{X}}})$,是否存在一个NP变换T使得条件$f(T{\mathit{\boldsymbol{X}}}) = g({\mathit{\boldsymbol{X}}})$或$f(T{\mathit{\boldsymbol{X}}}) = \overline {g({\mathit{\boldsymbol{X}}})} $成立,如果存在这样的T,那么$f({\mathit{\boldsymbol{X}}})$与$g({\mathit{\boldsymbol{X}}})$NPN等价,否则,$f({\mathit{\boldsymbol{X}}})$与$g({\mathit{\boldsymbol{X}}})$不NPN等价。
匹配算法首先确定函数$f$和$g$的相位,如果相位能够确定,则计算$f$和$g/\overline g $的1阶特征向量,同时计算变量的相位。然后,比较两个1阶特征向量是否相等。如果不相等,则$f$和$g$不NPN等价;如果相等,则调用Search()函数。如果Search()返回1,则$f$和$g$是NPN等价的,否则,不NPN等价。
如果$|f| = |\overline g |$且$|f| = |g|$,则$g$的相位不确定。首先为函数$g$分配正相位,然后检测$f$和$g$是否NP等价,如果NP等价,那么$f$和$g$是NPN等价;如果$f$和$g$是不NP等价,就检测$f$和$\overline g $是否NP等价,如果等价,那么$f$和$g$是NPN等价,否则,$f$和$g$不NPN等价。
例2:给定布尔函数$f({\mathit{\boldsymbol{X}}}) = \overline {{x_1}} \overline {{x_2}} \overline {{x_3}} {x_4} + $ $\overline {{x_1}} \overline {{x_2}} {x_3}(\overline {{x_4}} {x_5} + {x_4}\overline {{x_5}} ) + \overline {{x_1}} {x_2}(\overline {{x_3}} {x_4}\overline {{x_5}} + {x_3}\overline {{x_4}} ) + {x_1}\overline {{x_2}} \overline {{x_3}} \overline {{x_4}} + $${x_1}\overline {{x_2}} {x_3}(\overline {{x_4}} \overline {{x_5}} + {x_4}{x_5}) + {x_1}{x_2}(\overline {{x_3}} \overline {{x_4}} + \overline {{x_3}} {x_4}{x_5} + {x_3}{x_4})$,$g({\mathit{\boldsymbol{X}}}) = \overline {{x_1}} \overline {{x_2}} (\overline {{x_3}} {x_5} + {x_3}\overline {{x_5}} ) + \overline {{x_1}} {x_2}(\overline {{x_3}} {x_5} + {x_3}\overline {{x_4}} {x_5} + $ ${x_3}{x_4}\overline {{x_5}} ) + {x_1}\overline {{x_2}} (\overline {{x_3}} \overline {{x_4}} \overline {{x_5}} + \overline {{x_3}} {x_4}{x_5} + {x_3}\overline {{x_4}} {x_5} + {x_3}{x_4}\overline {{x_5}} ) + $ ${x_1}{x_2}(\overline {{x_3}} \overline {{x_5}} + {x_3}{x_5})$,检测$f$和$g$是否NPN等价,其过程如下:
1) data_f=bddtrue,data_g=bddtrue,建立$f$和$g$的BDD,计算1阶特征向量,结果为Vf={(9, 7), (8, 8), (8, 8), (8, 8), (8, 8)}, Vg={(8, 8), (8, 8), (8, 8), (8, 8), (9, 7)}。经过对称检测得到函数$f$有对称类${S_2} = \{ {x_2}, {x_5}\} $,函数$g$有对称类${S_2} = \{ {x_2}, {x_4}\} $。根据1阶特征向量可知$f$的变量${x_1}$相位为正,$g$的变量${x_5}$相位为正,其他变量相位不能确定。计算$f$中每个变量的变量映射集,可得${\chi _1} = \{ {x_1} \to {x_5}\} $是第一个要处理的映射集,data_f更新为${x_1}$, data_g更新为${x_5}$。
2) 更新1阶特征向量,结果为:Vf={(0, 0), (5, 4), (4, 5), (4, 5), (5, 4)}, Vg={(4, 5), (5, 4), (4, 5), (4, 5), (0, 0)},已经确定了的映射关系中的变量的1阶特征更新为(0, 0)。从该结果可以看出,所有变量的相位已经确定,并且可以得到${\chi _2} = \{ {S_2} \to {S_2}\} $是当前要处理的映射集。算法搜索到一种对称映射关系${\beta _2} = \{ {x_2} \to {x_2}, {x_5} \to \overline {{x_4}} \} $。更新data_f为${x_1}{x_2}$、data_g为${x_5}{x_2}$。
3) 更新1阶特征向量,结果为Vf={(0, 0), (0, 0), (2, 3), (3, 2), (0, 0)}, Vg={(2, 3), (0, 0), (3, 2), (0, 0), (0, 0)}。搜索到要处理的映射集为${\chi _3} = \{ \overline {{x_3}} \to \overline {{x_1}}, \overline {{x_3}} \to {x_3}\} $。算法选择第一个变量映射处理并更新data_f和data_g,data_f=${x_1}{x_2}\overline {{x_3}} $并且data_f=${x_5}{x_2}\overline {{x_1}} $。
4) 更新1阶特征向量,结果为Vf={(0, 0), (0, 0), (0, 0), (1, 2), (0, 0)}, Vg={(0, 0), (0, 0), (1, 2), (0, 0), (0, 0)}。搜索到变量映射集${\chi _4} = \{ \overline {{x_4}} \to \overline {{x_3}} \} $。至此,找到一个候选变换$T = \{ {x_1} \to {x_5}, {x_2} \to {x_2}, {x_5} \to \overline {{x_4}}, \overline {{x_3}} \to $ $\overline {{x_1}}, \overline {{x_4}} \to \overline {{x_3}} \} $,通过验证$f(T{\mathit{\boldsymbol{X}}}) = g({\mathit{\boldsymbol{X}}})$,所以$f$和$g$是NPN等价的。
例2的候选变换树如图 1所示。
5变量输入布尔函数有NP变换$5!{2^5}$个,例1中的候选变换树总共可能的NP变换为2个,匹配中验证第一个NP变换后算法就终止了。如果采用文献[7]中的算法对例1的两个函数进行匹配,在上述的第2步中要处理的变量映射集是${\chi _2} = \{ {x_2} \to {x_2}, {x_2} \to $ $\overline {{x_3}}, {x_2} \to \overline {{x_4}} \} $,那么其候选变换树中的第二层将会产生4个分支。从例1可以看出,本算法相对文献[7]的搜索空间减小了很多,其主要原因是对称变量的使用。