A New Pairwise NPN Boolean Matching Algorithm Based on Structural Difference Signature

In this paper, we address an NPN Boolean matching algorithm. The proposed structural difference signature (SDS) of a Boolean function significantly reduces the search space in the Boolean matching process. The paper analyses the size of the search space from three perspectives: the total number of possible transformations, the number of candidate transformations and the number of decompositions. We test the search space and run time on a large number of randomly generated circuits and Microelectronics Center of North Carolina (MCNC) benchmark circuits with 7–22 inputs. The experimental results show that the search space of Boolean matching is greatly reduced and the matching speed is obviously accelerated.

Keywords: NPN Boolean matching; structural difference signature vector; independent variable; variable symmetry

Boolean equivalence classification and matching constitute a long-standing and open problem. The authors of [[1]] applied a group algebraic approach to NP and NPN Boolean equivalence classification. Reference [[2]] computed the classification results for 10 inputs. Affine equivalence classification is also an important field of study with applications in logic synthesis and cryptography [[3]]. All Boolean functions in an equivalence class are equivalent to each other. NPN Boolean matching determines whether two Boolean functions are equivalent under input negation and/or permutation and/or output negation. This paper studies NPN Boolean matching for single-output completely specified Boolean functions.

NPN Boolean matching is an important research topic that can be applied to a number of applications in integrated circuit design, such as technology mapping, cell library binding and logic verification [[4]]. When a Boolean circuit is functionally NPN-equivalent to another Boolean circuit, one of these circuits can be realized by means of the other. There are $$n!2^{n+1}$$ NPN transformations for a n-variable Boolean function. If Boolean function f is NPN-equivalent to Boolean function g, there must be a NPN transformation that can transform f to g. On the contrary, no NPN transformation can transform f to g. The purpose of our proposed algorithm is to find the NPN transformation that can transform Boolean function f to g as early as possible. Based on the structural signature (SS) vector in our previous study [[5]], we proposes a new combined signature vector, i.e., SDS vector. In this paper, Boolean difference sigture is introduced into SS vector to form SDS vector. The new signature vector SDS is better able to distinguish variables and reduce the research space for NPN Boolean matching. Experimental results show that the search space is reduced by more than 48% compared with [[5]] and that the run time of our algorithm is reduced by 42% and 80% compared with [[5]], respectively.

In the following, Section 2 introduces relevant works on NPN-equivalence matching. Section 3 introduces some terminology and notation. Section 4 describes the proposed algorithm in detail. In Section 5, we present experimental results to demonstrate the effectiveness of our algorithm. Section 6 concludes the paper.

Many methods can be exploited to solve the problem of NPN Boolean matching. The main results of such research are focused on four methods: (1) algorithms on canonical forms; (2) pairwise matching algorithms using signatures; (3) algorithms based on satisfiability (SAT) and (4) algorithms based on spectral analysis.

Each method has its own advantages. In canonical-form-based matching algorithms, the canonical form of each Boolean circuit of cell library is stored in advance. When cell-library binding is implemented, the canonical form of each Boolean circuit to be matched is computed and compared with the canonical forms of each Boolean circuits in the cell library via a hash table. All Boolean functions in an equivalence class have the same canonical form. The canonical form of each equivalence class has a special value. References [[6]] studied Boolean matching based on canonical forms and attained significant achievements.

Reference [[12]] reported P-equivalence matching for 20-input Boolean functions. The canonical forms considered in reference [[12]] was the binary strings with the maximal scores in lexicographic comparison. Reference [[7]] devised a procedure to canonicalize a threshold logic function and judged equivalence of two threshold logic functions by their canonicalized linear inequalities. Based on the canonical form of Boolean function, the reference [[8]] reduced the number of configuration bits in an FPGA architecture. The authors of [[10]] proposed fast Boolean matching based on NPN Boolean classification; their canonical form has the maximal truth table. The authors of [[6]] proposed new canonical forms based on signatures.

A pairwise matching algorithm searches the NPN transformations between two Boolean functions using signatures, which is a semi-exhaustive search algorithm. The merit of this method is that once it finds a transformation that can prove the equivalence of two Boolean functions, other transformations will not be checked. The authors of [[4], [13]] proposed Boolean matching algorithms based on pairwise matching and used binary decision diagrams (BDDs) to represent Boolean functions. The authors of [[5]] proposed a structural signature vector to search the transformations between two Boolean functions and implemented NPN Boolean matching for 22 inputs. In pairwise matching algorithms, signatures are usually used as a necessary condition for judging whether two Boolean functions are equivalent, and variable symmetry is commonly utilized to reduce the search space. Symmetric attributes are used in many fields. Reference [[15]] studied the symmetries of the unitary Lie group. The variable symmetric attributes of Boolean function are widely used in NPN Boolean equivalence matching. In reference [[5]], the search space was reduced and the matching speed was improved by means of structural signatures, variable symmetry, phase collision check and variable grouping.

Since a SAT solver can help solve the problem of NPN Boolean matching and because many quick SAT solvers can be utilized, many Boolean matching algorithms based on SAT have emerged in recent years. The authors of [[16]] studied SAT-based Boolean matching. Based on graphs, simulation and SAT, Matsunaga [[16]] achieved PP-equivalence Boolean matching with larger inputs and outputs. The authors of [[17]] studied Boolean matching for FPGAs utilizing SAT technology. Cong et al. [[19]] used the implicant table to derive the SAT formulation and achieved significant improvements. The authors of [[20]] combined simulation and SAT to perform P-equivalent Boolean matching for large Boolean functions. Compared with studies based on the previous three methods, studies on Boolean matching that use spectral techniques are fewer in number. Moore et al. [[21]] presented an NPN Boolean matching algorithm using Walsh spectra. The authors of [[22]] utilized Haar spectra to check the equivalence of two logic circuits.

Regardless of which method is used, the key to Boolean matching is to reduce the search space. It is universally known that the search space for exhaustive NPN Boolean matching is $$O(n!2^{n+1})$$ . In the methods discussed above, many strategies are used to reduce the search space. The authors of [[6]] used general signatures and symmetry to reduce the search space.

Based on our previous study [[5]], we propose a new combined signature, i.e., the structural difference signature. We present a new pairwise algorithm based on the following conditions: (1) two NP-equivalent Boolean functions have the same SDS vectors; (2) two variables of a variable mapping have the same SDS values; and (3) two groups of Boolean functions Shannon decomposed with splitting variables are NP-equivalent.

Let $$f(x_0,x_1,\cdots ,x_{n-1})$$ and $$g(x_0,x_1,\cdots ,x_{n-1})$$ be two single-output completely specified Boolean functions. The problem to be solved in this paper is to determine whether f is NPN-equivalent to g. Some related terminology has been introduced in [[5]].

An NP transformation T is composed of input negations and/or permutations. It can also be expressed as a group of variable mappings. In reference [[5]], the mapping from the variable $$x_i$$ of f to the variable $$x_j$$ of g, $${\phi }_i$$ , can be classified into two cases: (1) $$x_i$$ maps to $$x_j$$ with the same phase, in which case the mapping is $$x_i\to x_j$$ or $${\overline{x}}_i\to {\overline{x}}_j$$ ; or (2) $$x_i$$ maps to $$x_j$$ with the opposite phase, in which case the mapping is $$x_i\to {\overline{x}}_j$$ or $${\overline{x}}_i\to x_j$$ . A same-phase relation indicates no input negation, whereas an opposite-phase relation indicates input negation. A same-phase variable mapping between the variables $$x_i$$ and $$x_j$$ is abbreviated as $$i\to j-0$$ , and an opposite-phase variable mapping between the variables $$x_i$$ and $$x_j$$ is abbreviated as $$i\to j-1$$ . For two NPN-equivalent Boolean functions f and g, there may be an output negation when $$\left|f\right|=\left|\overline{g}\right|$$ .

(NPN equivalence) Two Boolean functions f and g are NPN equivalent, $$f\cong g$$ , if and only if there exists an NP transformation T that satisfies $$f\left(TX\right)=g\left(X\right)$$ or $$f\left(TX\right)=\overline{g\left(X\right)}$$ .

As a general signature, the cofactor signature is widely applied in NPN Boolean matching. The cofactor signature of $$f\left(X\right)$$ with respect to $$x_i$$ $$\left({\overline{x}}_i\right)$$ is $$\left|f_{x_i}\right|$$ $$\left(\left|f_{{\overline{x}}_i}\right|\right)$$ [[5]].

Reference [[5]] proposed SS vector. The SS value of f with respect to $$x_i$$ , $$V_i$$ , is $$(\left|f_{x_i}\right|,\left|f_{{\overline{x}}_i}\right|,\left|C_i\right|,C_i,G_i)$$ . $$(\left|f_{x_i}\right|,\left|f_{{\overline{x}}_i}\right|)$$ is the 1st signature of the variable $$x_i$$ , and $$C_i$$ and $$|C_i|$$ are the symmetry mark, and $$G_i$$ is group mark. According to their symmetry properties, the variables of a Boolean function are classified as either asymmetric and symmetric. An asymmetric variable may have a single-mapping set or a multiple-mapping set. The variable mapping set of the asymmetric variable $$x_i$$ is denoted by $${\chi }_i$$ . Similarly, a symmetric variable may have a single symmetry-mapping set or a multiple symmetry-mapping set. The symmetry-mapping set of the symmetry class $$C_i$$ is denoted by $$S_i$$ , and the symmetry mapping between $$C_i$$ and $$C_j$$ is denoted by $$C_i\to C_j$$ . The literal $${\psi }_i$$ represents a group of two or more variable mappings generated by $$C_i\to C_j$$ .

A P transformation does not change the cofactor signature of a variable. However, an N transformation changes the order of the positive and negative cofactor signatures without changing their numerical values. Therefore, we do not consider the order of the positive and negative cofactor signatures when comparing the 1st signature values of two variables. A variable $$x_i$$ may be transformed into an arbitrary variable $$x_j$$ , $$0\le j\le n-1$$ ; therefore, we also do not consider the order of the variables when we compare two SS vectors.

Given two NP-equivalent Boolean functions f and g with a variable mapping $$x_i\to x_j$$ between them, we have the following four facts: (1) $$V_f=V_g$$ and $$V_i=V_j$$ ; (2) The Boolean functions decomposed with $$x_i$$ and $$x_j$$ using the Shannon expansion must be NP equivalent. Specifically, $$x_i{f}_{x_i}$$ is NP equivalent to $$x_j{g}_{x_j}$$ , and $${\overline{x}}_i{f}_{{\overline{x}}_i}$$ is NP equivalent to $${\overline{x}}_j{g}_{{\overline{x}}_j}$$ ; (3) $$x_i$$ and $$x_j$$ are either both asymmetric variables or both symmetric variables; (4) If there is a variable mapping between $$x_l$$ of f and $$x_h$$ of g, then the SS values of $$x_l$$ must be the same as those of $$x_h$$ no matter how many times the Boolean functions f and g are decomposed [[5]].

Two Boolean functions f and g may undergo one or more transformations in the process of matching. A transformation consists of n variable mappings. The algorithm of [[5]] and the algorithm presented in this paper detect all possible transformations between f and g according to their SS and SDS vectors, respectively.

The goal of the proposed algorithm is to reduce the size of the search space as much as possible, thereby improving the speed of NPN Boolean matching.

For n inputs, there are $$2^{2^n}$$ different Boolean functions. Many Boolean functions have one or more independent variables. Whether a variable $$x_i$$ of f is independent can be determined using cofactors.

The Boolean difference of a Boolean function f with respect to $$x_i$$ , $$f_{x_i}^{\prime }$$ , is the Boolean function $$f_{x_i}\oplus f_{{\overline{x}}_i}$$ , where $$f_{x_i}=f[x_i\leftarrow 1]$$ and $$f_{{\overline{x}}_i}=f[x_i\leftarrow 0]$$ [[23]].

(Boolean difference signature) The Boolean difference signature of a Boolean function f with respect to $$x_i$$ , $$|f_{x_i}^{\prime }|$$ , is the number of minterms of $$f_{x_i}^{\prime }$$ .

When a variable $$x_i$$ of f is NP transformed into $$x_j$$ $$\left({\overline{x}}_j\right)$$ , its Boolean difference signature does not change. Thus, Boolean difference signature, like cofactor signature, can be used to distinguish variables.

Consider an 5-input Boolean function $$f\left(X\right)=x_0{\overline{x}}_2{\overline{x}}_3+{\overline{x}}_0{x}_1{x}_2{\overline{x}}_3+x_0{x}_1{x}_3{x}_4+{\overline{x}}_0{\overline{x}}_1{x}_3{\overline{x}}_4+x_0{\overline{x}}_1{\overline{x}}_3{\overline{x}}_4+x_0{x}_2{x}_3{x}_4+{\overline{x}}_0{\overline{x}}_1{\overline{x}}_2{x}_3+{\overline{x}}_0{x}_2{\overline{x}}_3{x}_4+x_0{x}_1{x}_2{x}_3+{\overline{x}}_0{\overline{x}}_2{x}_3{\overline{x}}_4$$ . Let us compute the 1st signature and the Boolean difference signature of each variable.

The 1st signatures of $$x_0$$ , $$x_1$$ , $$x_2$$ , $$x_3$$ and $$x_4$$ are $$(9,7)$$ , $$(8,8)$$ , $$(8,8)$$ , $$(8,8)$$ and $$(8,8)$$ , respectively. The variable $$x_1$$ is symmetric to $$x_4$$ . The Boolean difference signatures of the variables are 32, 12, 20, 28 and 12, respectively. From the 1st signatures and a symmetry check, we can distinguish variables $$x_0$$ , $$x_1$$ and $$x_4$$ . Variables $$x_2$$ and $$x_3$$ are both asymmetric variables and have the same 1st signature values. If we only utilize on their 1st signatures, the variables $$x_2$$ and $$x_3$$ cannot be distinguished. However, these two variables have different Boolean difference signatures. Thus, the variables $$x_2$$ and $$x_3$$ are actually different and can be distinguished.

(Independent variable) A variable $$x_i$$ of a Boolean function f is an independent variable if it satisfies $$|f_{x_i}^{\prime }|=0$$ .

NP transformations do not change the independence of a variable. Thus, an independent variable is still an independent variable after NP transformation.

(Independent-variable set) The independent-variable set of a Boolean function f, $$D_f$$ , is a set that consists of all independent variables of f.

Two NPN-equivalent Boolean functions f and g have the same number of independent variables.

If the Boolean function f is NPN-equivalent to g, then f and g are in the same NPN equivalence class. There must exist an NP transformation T that can transform f into g or $$\overline{g}$$ . After NP transformation, an independent variable is still an independent variable. Therefore, it can be deduced that f and g have the same number of independent variables. □

The cofactor signature of a Boolean function f with respect to its variable $$x_i$$ is $$\left|f_{x_i}\right|=\left|f_{{\overline{x}}_i}\right|=\frac{1}{2}\left|f\right|$$ when the variable $$x_i$$ is an independent variable.

Since $$f_{x_i}^{\prime }=f_{x_i}\oplus f_{{\overline{x}}_i}$$ and $$|f_{x_i}^{{}^{\prime }}|=0$$ and $$|f_{x_i}|+|f_{{\overline{x}}_i}|=|f|$$ , it holds that $$\left|f_{x_i}\right|=\left|f_{{\overline{x}}_i}\right|=\frac{1}{2}\left|f\right|$$ . □

Because the positive cofactor signature is the same as the negative cofactor signature for an independent variable, the phases of independent variables cannot determined by using the phase assignment method presented in [[5]]. However, independent variables have no influence on a Boolean function. Thus, the proposed algorithm assigns a positive phase to all independent variables.

Consider two 6-input Boolean functions $$f\left(X\right)={\overline{x}}_0{x}_1{\overline{x}}_2+{\overline{x}}_0{x}_1{x}_2{x}_3+x_0{\overline{x}}_1{\overline{x}}_2+x_0{\overline{x}}_1{x}_2{x}_3$$ and $$g\left(X\right)={\overline{x}}_0{\overline{x}}_1{\overline{x}}_3{x}_4+{\overline{x}}_0{x}_1{x}_3{x}_4+x_0{\overline{x}}_1{\overline{x}}_3+x_0{x}_1{x}_3$$ . Let us compute the SS vectors, Boolean difference signatures and independent-variable sets.

The SS vectors of f and g are as follows:

$$V_f=\{(12,12,2,0,1),(12,12,2,0,1),(8,16,2,2,0),(16,8,2,2,0),(12,12,2,4,1),(12,12,2,4,1)\},$$

$$V_g=\{(16,8,2,0,0),(12,12,2,1,1),(12,12,2,2,1),(12,12,2,1,1),(16,8,2,0,0),(12,12,2,2,1)\}.$$

The Boolean difference signatures of the variables of f are 48, 48, 16, 16, 0 and 0. The Boolean difference signatures of the variables of g are 16, 48, 0, 48, 16 and 0. The independent-variable sets of f and g are $$D_f=\{x_4,x_5\}$$ and $$D_g=\{x_2,x_5\}$$ .

(Independent mapping set) The independent mapping set between Boolean functions f and g is $$D=\{{\phi }_i:x_i\to x_j|x_i\in D_f,x_j\in D_g\}$$ .

Consider two NP-equivalent Boolean functions f and g with independent-variable sets of $$D_f=\{x_{i_1},x_{i_2},\cdots x_{i_k}\}$$ and $$D_g=\{x_{j_1},x_{j_2},\cdots x_{j_k}\}$$ , respectively. If we do not consider the symmetry and independence of variables, then there are $$2^{k}k!$$ groups of different variable mappings between $$D_f$$ and $$D_g$$ according to their 1st signatures. However, according to the properties of independent variables, we need to consider only the positive phase and create one independent-mapping set $$\{x_{i_1}\to x_{j_1},x_{i_2}\to x_{j_2},\cdots x_{i_k}\to x_{j_k}\}$$ . Therefore, the search space is reduced significantly if there are independent variables in the Boolean functions.

In Example 2, the Boolean function f has the three symmetry classes $$C_0=\{x_0,x_1\}$$ , $$C_2=\{x_2,x_3\}$$ and $$C_4=\{x_4,x_5\}$$ , and the Boolean function g has the three symmetry classes $$C_0=\{x_0,x_4\}$$ , $$C_1=\{x_1,x_3\}$$ and $$C_2=\{x_2,x_5\}$$ if we do not consider the Boolean difference signatures. The symmetry class $$C_0$$ of f can be mapped to the symmetry classes $$C_1$$ and $$C_2$$ of g using the method of reference [[5]]. In other words, the symmetry classes $$C_0$$ and $$C_4$$ of Boolean function f cannot be distinguished. However, the variables in $$C_0$$ and $$C_4$$ of Boolean function f have different Boolean difference signatures. Thus, if we consider the Boolean difference signatures when searching the variable mappings, the symmetry class $$C_0$$ of f can be mapped only to the symmetry class $$C_1$$ of g, and the symmetry class $$C_4$$ of f can be mapped only to the symmetry class $$C_2$$ of g. There exists an independent-mapping set $$\{x_4\to x_2,x_5\to x_5\}$$ .

(Structural difference signature vector) An n-input Boolean function f has a structural difference signature (SDS) vector $$V_f=\{V_0,V_1,\cdots ,V_{n-1}\}$$ , where $$V_i=(\left|f_{x_i}\right|,\left|f_{{\overline{x}}_i}\right|,\left|C_i\right|,C_i,G_i,|f_{x_i}^{\prime }\left|\right)$$ .

The algorithm presented in [[5]] groups variables by their 1st signature values. The algorithm proposed in this paper groups variables by their 1st signature values and Boolean difference signatures. We define the '<' relation between $$x_i$$ and $$x_j$$ as follows.

(<) The variables $$x_i$$ and $$x_j$$ have the relation $$x_i<x_j$$ if one of the following two cases is satisfied: (1) $$(\left|f_{x_i}\right|,\left|f_{{\overline{x}}_i}\right|)<(\left|f_{x_j}\right|,\left|f_{{\overline{x}}_j}\right|)$$ or (2) $$(\left|f_{x_i}\right|,\left|f_{{\overline{x}}_i}\right|)=(\left|f_{x_j}\right|,\left|f_{{\overline{x}}_j}\right|)\wedge \left|f_{x_i}^{{}^{\prime }}\right|<\left|f_{{\overline{x}}_i}^{{}^{\prime }}\right|$$ .

The group numbers of the variables are generated with the above '<' relation. The SDS vectors of f and g in example 2 are as follows: $$V_f=\{(12,12,2,0,1,48),(12,12,2,0,1,48),(8,16,2,2,0,16),$$ $$(16,8,2,2,0,16),(12,12,2,4,2,0),(12,12,2,4,2,0)\}$$ and $$V_g=\{(16,8,2,0,0,16),(12,12,2,1,1,48),$$ $$(12,12,2,2,2,0),(12,12,2,1,1,48),(16,8,2,0,0,16),(12,12,2,2,2,0)\}$$ . In the process of grouping variables of Boolean function f, we first compare their 1st signature and do not consider the order of positive and negative cofactor signature. Therefore, variables $$x_2$$ and $$x_3$$ are grouped into group 0. The varibales in symmetry class $$C_0$$ and $$C_4$$ have the same 1st signature, so we compare their Boolean difference signature. Because the Boolean difference signature of variables in $$C_0$$ is greater than that of variables in symmetry class $$C_4$$ , the group number of variables $$x_0$$ and $$x_1$$ are 1 and the group number of variables $$x_4$$ and $$x_5$$ are 2.

The SDS vector is a new signature vector that consists of the SS vector plus a Boolean difference mark. The variable mapping search and the transformation detection of our algorithm are based on two facts: (1) two NP-equivalent Boolean functions have the same SDS vectors; and (2) there exists a possible variable mapping between the variables $$x_i$$ and $$x_j$$ if they have the same SDS values.

NPN Boolean matching is defined as follows:

Given two Boolean functions f and g, if there exists an NP transformation T that satisfies $$f\left(TX\right)=g\left(X\right)$$ or $$f\left(TX\right)=\overline{g\left(X\right)}$$ , then f is NPN-equivalent to g.

Before searching the variable mappings, the proposed algorithm first determines whether there is an output negation for Boolean function f. If there is, then our algorithm will match f and $$\overline{g}$$ . The method of identifying the presence of an output negation is the same as that in reference [[5]]. If $$\left|f\right|=\left|g\right|\wedge \left|f\right|\ne |\overline{g}|$$ , then there is no output negation. There is an output negation if $$\left|f\right|\ne \left|g\right|\wedge \left|f\right|=|\overline{g}|$$ . There is a tie if $$\left|f\right|=\left|g\right|\wedge \left|f\right|=|\overline{g}|$$ . Our algorithm handles first the condition without output negation and then the condition with output negation if f is not NP equivalent to g.

The algorithm will terminate when it finds a transformation T that satisfies $$f\left(TX\right)=g\left(X\right)$$ $$(\overline{g\left(X\right)})$$ or when all candidate transformations have been checked and found not to satisfy $$f\left(TX\right)=g\left(X\right)$$ $$(\overline{g\left(X\right)})$$ . The algorithm will attempt all possible variable mappings, and thus, it will certainly find an NP transformation T between two NP-equivalent Boolean functions f and g $$\left(\overline{g}\right)$$ .

The pseudo-code for NPN Boolean matching is given in Procedure 1.

In Procedure 1, $$trans\_list$$ is a tree that stores the NP transformations generated in the process of transformation detection. A candidate transformation is an unabridged branch in $$trans\_list$$ . $$sp\_f$$ and $$sp\_g$$ are the decomposition expressions for f and g, respectively. After the existence of an output negation has been determined, Procedure 1 calls Handle_SDS() to detect the NP transformations between f and g ( $$\overline{g}$$ ) and judge the NP equivalence of f and g $$\left(\overline{g}\right)$$ .

Any one NP transformation between the Boolean functions f and g $$\left(\overline{g}\right)$$ is composed of n variable mappings. Thus, the proposed algorithm searches variable mappings and generates NP transformations. In this paper, the necessary condition for two Boolean functions to be judged NP equivalent is that they must have the same SDS vector. For a variable mapping to be established between $$x_i$$ and $$x_j$$ , these two variables must satisfy the following conditions:

(1) $$x_i$$ and $$x_j$$ have the same 1st signature values, i.e., $$\left(\right|f_{x_i}|,|f_{{\overline{x}}_i}\left|\right)=\left(\right|f_{x_j}|,|f_{{\overline{x}}_j}\left|\right)\vee \left(\right|f_{x_i}|,|f_{{\overline{x}}_i}\left|\right)=\left(\right|f_{{\overline{x}}_j}|,|f_{x_j}\left|\right)$$ .

(2) $$x_i$$ and $$x_j$$ have the same Boolean difference signature, i.e., $$|f_{x_i}^{{}^{\prime }}|=|f_{x_j}^{{}^{\prime }}|$$ .

(3) $$x_i$$ and $$x_j$$ have the same symmetry class cardinality, i.e., $$|C_i|=|C_j|$$ .

(4) $$x_i$$ and $$x_j$$ have the same group number, i.e., $$G_i=G_j$$ .

In the process of the variable mapping search, Handle_SDS() searches the variable mappings for each variable that has not been identified. A variable is identified when its phase and variable mappings are determined in a transformation. After searching all variable mapping sets, Handle_SDS() selects the minimal variable mapping set to handle. The minimal variable mapping set is the one with the lowest cardinality. There are eight possible cases for the variable mapping set of the variable $$x_i$$ of f, as follows.

(1) The variable $$x_i$$ is an asymmetric variable. The phase of $$x_i$$ is determined, and there is only one variable $$x_j$$ of g that has the same SDS values as those of $$x_i$$ . The variable mapping set of $$x_i$$ is a single-mapping set. $${\chi }_i=\{i\to j-k\}$$ , $$k\in \{0,1\}$$ , and $$|{\chi }_i|=1$$ .

(2) The variable $$x_i$$ is an asymmetric variable. There exist multiple variables $$x_{j_1},x_{j_2},\cdots ,x_{j_m}$$ of g, where $$m\ge 2$$ , that have the same SDS values as those of $$x_i$$ , and their phases are determined. The variable mapping set of $$x_i$$ is a multiple-mapping set. $${\chi }_i=\{i\to j_1-k_1,i\to j_2-k_2,\cdots ,i\to j_m-k_m\}$$ , where $$k_1,k_2,\cdots ,k_m\in \{0,1\}$$ , and $$|{\chi }_i|=m$$ .

(3) The variable $$x_i$$ is an asymmetric variable. There exist one or more variables $$x_{j_1},x_{j_2},\cdots ,x_{j_m}$$ of g, where $$m\ge 1$$ , that have the same SDS values as those of $$x_i$$ , and their phases are not determined. The variable mapping set of $$x_i$$ is a multiple-mapping set. $${\chi }_i=\{i\to j_1-0,i\to j_1-1,i\to j_2-0,i\to j_2-1,\cdots ,i\to j_m-0,i\to j_m-1\}$$ , and $$|{\chi }_i|=2m$$ .

(4) The variable $$x_i$$ is a symmetric variable, and its symmetry class is $$C_i=\{x_i,x_{i_1},x_{i_2},\cdots ,x_{i_{m-1}}\}$$ . There exists only one symmetry class $$C_j=\{x_j,x_{j_1},x_{j_2},\cdots ,x_{j_{m-1}}\}$$ of g whose variables have the same SDS values as those of the variables in $$C_i$$ , where $$|C_i|=|C_j|$$ , and the phase of $$x_i$$ is determined. The variable mapping set of $$x_i$$ , $$S_i$$ , is a single symmetry-mapping set, i.e., $$|S_i|=1$$ . There exists one group of variable mappings $$\{i\to j-k,i_1\to j_1-k_1,i_2\to j_2-k_2,\cdots ,i_{m-1}\to j_{m-1}-k_{m-1}\}$$ , where $$k,k_1,k_2,\cdots ,k_{m-1}\in \{0,1\}$$ , between $$C_i$$ and $$C_j$$ .

(5) The variable $$x_i$$ is a symmetric variable, and its symmetry class is $$C_i=\{x_i,x_{i_1},x_{i_2},\cdots ,x_{i_{m-1}}\}$$ . There is only one symmetry class $$C_j=\{x_j,x_{j_1},x_{j_2},\cdots ,x_{j_{m-1}}\}$$ of g whose variables have the same SDS values as those of the variables in $$C_i$$ , where $$|C_i|=|C_j|$$ , and the phase of $$x_i$$ is not determined. The variable mapping set of $$x_i$$ , $$S_i$$ , is a multiple symmetry-mapping set: $$|S_i|=2$$ . There are two groups of variable mappings, $$\{i\to j-0,i_1\to j_1-k_1,i_2\to j_2-k_2,\cdots ,i_{m-1}\to j_{m-1}-k_{m-1}\}$$ , where $$k_1,k_2,\cdots ,k_{m-1}\in \{0,1\}$$ , and $$\{i\to j-1,i_1\to j_1-p_1,i_2\to j_2-p_2,\cdots ,i_{m-1}\to j_{m-1}-p_{m-1}\}$$ , where $$p_1,p_2,\cdots ,p_{m-1}\in \{0,1\}$$ , between $$C_i$$ and $$C_j$$ .

When the variable symmetry is checked, the phase relation between two symmetric variables is known. The variable mapping relations between $$C_i$$ and $$C_j$$ can be generated in the following way.

We first consider the case in which $$x_i$$ and $$x_j$$ have the same phase, i.e., there exists a variable mapping $$i\to j-0$$ . A variable mapping $$i_1\to j_1-0$$ exists in two cases: (1) $$x_i$$ is symmetric to $$x_{i_1}$$ and $$x_j$$ is symmetric to $$x_{j_1}$$ or (2) $$x_i$$ is symmetric to $${\overline{x}}_{i_1}$$ and $$x_j$$ is symmetric to $${\overline{x}}_{j_1}$$ . A variable mapping $$i_1\to j_1-1$$ exists in two cases: (1) $$x_i$$ is symmetric to $$x_{i_1}$$ and $$x_j$$ is symmetric to $${\overline{x}}_{j_1}$$ or (2) $$x_i$$ is symmetric to $${\overline{x}}_{i_1}$$ and $$x_j$$ is symmetric to $$x_{j_1}$$ . Then, we consider the case in which $$x_i$$ and $$x_j$$ have the opposite phase, i.e., there exists a variable mapping $$i\to j-1$$ . A variable mapping $$i_1\to j_1-1$$ exists in two cases: (1) $$x_i$$ is symmetric to $$x_{i_1}$$ and $$x_j$$ is symmetric to $$x_{j_1}$$ or (2) $$x_i$$ is symmetric to $${\overline{x}}_{i_1}$$ and $$x_j$$ is symmetric to $${\overline{x}}_{j_1}$$ . A variable mapping exists $$i_1\to j_1-0$$ in two cases: (1) $$x_i$$ is symmetric to $$x_{i_1}$$ and $$x_j$$ is symmetric to $${\overline{x}}_{j_1}$$ or (2) $$x_i$$ is symmetric to $${\overline{x}}_{i_1}$$ and $$x_j$$ is symmetric to $$x_{j_1}$$ . Thus, two groups of variable mappings between $$C_i$$ and $$C_j$$ will be generated via this method.

(6) The variable $$x_i$$ is a symmetric variable, and its symmetry class is $$C_i$$ . There exist multiple symmetry classes $$C_{j_1},C_{j_2},\cdots ,C_{j_m}$$ , where $$2\le m\le ⌊\frac{n}{2}⌋$$ , whose variables have the same SDS values as the variables in $$C_i$$ , where $$|C_i|=|C_{j_1}|=|C_{j_2}|=\cdots =|C_{j_m}|$$ , and the phase of $$x_i$$ is determined. The variable mapping set of $$x_i$$ , $$S_i$$ , is a multiple symmetry-mapping set: $$|S_i|=m$$ . There exists one group of variable mappings between $$C_i$$ and each $$C_{j_p}$$ , where $$p\in \{1,2,\cdots ,m\}$$ .

(7) The variable $$x_i$$ is a symmetric variable, and its symmetry class is $$C_i$$ . There exist one or more symmetry classes $$C_{j_1},C_{j_2},\cdots ,C_{j_m}$$ , where $$1\le m\le ⌊\frac{n}{2}⌋$$ , whose variables have the same SDS values as those of the variables of $$C_i$$ , where $$|C_i|=|C_{j_1}|=|C_{j_2}|=\cdots =|C_{j_k}|$$ , and the phase of $$x_i$$ is not determined. The variable mapping set of $$x_i$$ , $$S_i$$ , is a multiple symmetry-mapping set: $$|S_i|=2m$$ . There exist two groups of variable mappings between $$C_i$$ and each $$C_{j_p}$$ , where $$p\in \{1,2,\cdots ,m\}$$ .

(8) The variable $$x_i$$ is an independent variable. The variable mapping set of $$x_i$$ is an independent mapping set.

All possible variable mapping sets are listed above. To generate an NP transformation, n variable mappings are needed for $$x_1,x_2,\cdots ,x_n$$ . Each node in the NP transformation tree, $$trans\_list$$ , represents a variable mapping, and all nodes in a given layer belong to the same variable mapping set. The methods for handling the variable mapping sets are as follows.

(1) If it is the first computation of SDS vectors, a check for independent variables is performed. If there are one or more independent variables, an independent-mapping set is created and added to $$trans\_list$$ , and the minimal variable mapping set is then sought among the remaining variables. If there are no independent variables, Handle_SDS() searches the variable mapping sets for all variables.

(2) If the current variable mapping set of $$x_i$$ is a single-mapping set, our algorithm adds the variable mapping in $${\chi }_i$$ to $$trans\_list$$ . The variable $$x_i$$ is identified.

(3) If the current variable mapping set of $$x_i$$ is a single symmetry-mapping set and $$x_i$$ belongs to $$C_i$$ , where $$|C_i|=m$$ , then the group $${\psi }_i$$ of variable mappings of $$S_i$$ is added to $$trans\_list$$ . To the NP transformation tree, m layers are added, where each layer contains a variable mapping node. The variables in the symmetry class $$C_i$$ are all identified.

(4) If the current variable mapping set of $$x_i$$ is a multiple-mapping set or a multiple symmetry-mapping set, then the cardinalities of the variable mapping sets are computed, and the minimal variable mapping set is recorded.

After searching all variable mapping sets, as in reference [[5]], our algorithm updates the two decomposition expressions $$sp\_f$$ and $$sp\_g$$ in the case of a single-mapping set or a single symmetry-mapping set. Otherwise, our algorithm handles the minimal variable mapping set. If the cardinality m of the minimal variable mapping set satisfies $$m\ge 2$$ , then m branches will be generated in $$trans\_list$$ . Each branch is handled in order.

The purpose of Procedure 2 is to search the variable mappings for all possible NP transformations. In the process of recursive_search, Procedure 2 uses the same methods applied in [[5]] to find and prune error NP transformation branches. That is, the current branch will be pruned if the two SDS vectors are not the same or if the current variable mapping has a phase collision.

The pseudo-code for Procedure 2 is as follows.

The meanings of conditions $$D_1$$ , $$D_2$$ , $$D_3$$ , $$D_4$$ , $$D_5$$ and $$D_6$$ and the operations that need to be performed when these conditions are satisfied are defined as follows:

$$D_1$$ : When $$D_1$$ is true, a candidate transformation is generated. Procedure 2 checks whether the current NP transformation T can transform f into g $$\left(\overline{g}\right)$$ .

$$D_2$$ : When $$D_2$$ is true, the transformation tree is NULL, and this is the first time that the SDS vectors have been computed. Procedure 2 checks and handles the independent-mapping set between f and g $$\left(\overline{g}\right)$$ .

$$D_3$$ : When $$D_3$$ is true, the current variable $$x_i$$ has already been identified, and Procedure 2 fetches the next $$x_i$$ to handle.

$$D_4$$ : When $$D_4$$ is true, the variable-mapping set of $$x_i$$ is a single-mapping set or a single symmetry-mapping set.

$$D_5$$ : When $$D_5$$ is true, there is a phase collision.

$$D_6$$ : When $$D_6$$ is true, the cardinality of the minimal variable mapping set is 1.

In the process of transformation detection, Procedure 2 attempts each variable mapping in each multiple-mapping set or each group of variable mappings in each multiple symmetry-mapping set. For two NP-equivalent Boolean functions f and g ( $$\overline{g}$$ ), Procedure 2 must find a candidate transformation that satisfies $$f\left(TX\right)=g\left(X\right)$$ $$(\overline{g\left(X\right)})$$ . The purpose of VERIFY() is to check whether $$f\left(TX\right)=g\left(X\right)$$ $$(\overline{g\left(X\right)})$$ .

UPDATE() serves the following functions:

(1) Updates the SDS vector $$V_f$$ of f and the SDS vector $$V_g$$ of g by means of Shannon decomposition and the decomposition expressions $$sp\_f$$ and $$sp\_g$$ .

(2) Updates the phases of the variables in f and g.

(3) Checks the variable symmetry when the SDS vectors are computed for the first time.

(4) Groups the variables of f and g by their 1st signature values and Boolean difference signatures.

In Example 2, if we use the SS values to search the variable mappings, then there are one single symmetry-mapping set $$S_2=\{C_2\to C_0\}$$ and two multiple symmetry-mapping sets $$S_0=\{C_0\to C_1,C_0\to C_2\}$$ and $$S_4=\{C_4\to C_1,C_4\to C_2\}$$ , where $$\left|S_0\right|=\left|S_4\right|=4$$ . Procedure 2 handles the single symmetry-mapping set $$S_2$$ , and the variable mappings $${\overline{x}}_2\to x_0$$ and $$x_3\to x_4$$ are added to $$trans\_list$$ . $$sp\_f$$ and $$sp\_g$$ are updated to $${\overline{x}}_2$$ and $$x_0$$ . After the SS vectors are updated, the 1st signatures of the remaining variables of f and g are all $$(8,8)$$ . Therefore, the remaining four variables still cannot be distinguished, and there are two multiple symmetry-mapping sets, $$S_0$$ and $$S_4$$ . The first symmetry-mapping set $$S_0$$ is selected to be handled. The transformation tree for Example 2 using SS vectors is shown in Figure 1.

If we use the SDS values to search the variable mappings, then there are one independent-mapping set, one single symmetry-mapping set and one multiple symmetry-mapping set according to the first computed SDS vectors. Procedure 2 first adds the variable mappings $$x_4\to x_2$$ and $$x_5\to x_5$$ to the transformation tree. Then, the two variable mappings $${\overline{x}}_2\to x_0$$ and $$x_3\to x_4$$ of the symmetry mapping $$C_2\to C_0$$ are added to the transformation tree. The catch is that the independent variable is not a splitting variable because the decomposition results obtained via Shannon expansion with the independent variable are unchanged. Thus, the decomposition expressions $$sp\_f$$ and $$sp\_g$$ are updated to $${\overline{x}}_2$$ and $$x_0$$ . UPDATE() is called to compute new SDS vectors, and the SDS vectors are updated in accordance with $$sp\_f$$ and $$sp\_g$$ .

In this way, Procedure 2 determines 4 variable mappings, namely, $$x_4\to x_2$$ , $$x_5\to x_5$$ , $${\overline{x}}_2\to x_0$$ and $$x_3\to x_4$$ , after the first variable mapping search for example 2. In the next variable mapping search, there is one multiple symmetry-mapping set, $$S_0=\{\{x_0\to x_1,x_1\to x_3\},\{x_0\to {\overline{x}}_1,x_1\to {\overline{x}}_3\}\}$$ . The transformation tree for Example 2 using SDS vectors is shown in Figure 2.

From Example 2, we can see that the number of candidate transformations decreases from 8 to 2. The use of Boolean difference signatures helps to distinguish symmetry classes $$C_1$$ and $$C_5$$ , and we need to consider only the positive phase for independent variables. Thus, Boolean difference signatures are very beneficial for distinguishing variables.

In cell library binding, a benchmark Boolean circuit is found to realize another NPN equivalent Boolean function. Example 3 demonstrates the process of NPN equivalent matching by SS and SDS vectors respectively, and illustrates the validity of the SDS vectors proposed in this paper.

Consider two 6-input Boolean functions $$f\left(X\right)$$ and $$g\left(X\right)$$ :

$$f\left(X\right)=x_0{x}_1(x_3{x}_5+x_4{x}_5)+x_0{\overline{x}}_1(x_4{\overline{x}}_5+x_2{x}_3{\overline{x}}_4{\overline{x}}_5)+x_1{\overline{x}}_3{\overline{x}}_4{\overline{x}}_5+x_1{\overline{x}}_2{\overline{x}}_4{\overline{x}}_5+{\overline{x}}_0{\overline{x}}_1({\overline{x}}_4{x}_5+x_2{\overline{x}}_3{x}_4{x}_5)+{\overline{x}}_1{\overline{x}}_3{\overline{x}}_4{x}_5+{\overline{x}}_0{x}_1({\overline{x}}_2{x}_3{x}_4+x_2{\overline{x}}_3{x}_4+x_3{x}_4{x}_5+x_2{\overline{x}}_4{\overline{x}}_5+{\overline{x}}_2{x}_4{\overline{x}}_5)+{\overline{x}}_1{x}_2{x}_3{x}_4{\overline{x}}_5,$$

$$g\left(X\right)={\overline{x}}_0{x}_1{x}_2{\overline{x}}_3+x_0{x}_1{\overline{x}}_2{\overline{x}}_3+{\overline{x}}_0{\overline{x}}_1{\overline{x}}_2{x}_3+{\overline{x}}_0{x}_1{x}_2{x}_5+{\overline{x}}_0{x}_1{x}_3{x}_4{\overline{x}}_5+x_0{\overline{x}}_1{x}_2{\overline{x}}_5+x_0{x}_1{\overline{x}}_2{x}_5+{\overline{x}}_0{\overline{x}}_1{\overline{x}}_2{\overline{x}}_3{\overline{x}}_4+{\overline{x}}_0{\overline{x}}_1{x}_2{\overline{x}}_3{x}_5+{\overline{x}}_0{\overline{x}}_1{x}_2{x}_4{x}_5+{\overline{x}}_0{\overline{x}}_1{\overline{x}}_2{x}_4{\overline{x}}_5+{\overline{x}}_0{x}_1{\overline{x}}_2{x}_3{\overline{x}}_4{\overline{x}}_5+x_0{x}_1{x}_2{x}_3{\overline{x}}_4{\overline{x}}_5+x_0{\overline{x}}_1{\overline{x}}_2{\overline{x}}_3{x}_4{x}_5.$$

The transformation detection process using SS vectors is as follows:

(1) Compute the SS vectors of f and g. The results are:

$$V_f=\{(16,16,-1,-1,1),(19,13,-1,-1,0),(16,16,-1,-1,1),(16,16,-1,-1,1),(16,16,-1,-1,1),(16,16,-1,-1,1)\},$$

$$V_g=\{(13,19,-1,-1,1),(16,16,-1,-1,0),(16,16,-1,-1,1),(16,16,-1,-1,1),(16,16,-1,-1,1),(16,16,-1,-1,1)\}.$$

From the above results, we can draw three conclusions: (1) these two SS vectors are the same; (2) the phases of the variable $$x_1$$ of f and the variable $$x_0$$ of g are determined; and (3) there is only one variable $$x_0$$ of g with the same SS values as those of the variable $$x_1$$ of f. Therefore, there is a single-mapping set $$\{x_1\to {\overline{x}}_0\}$$ . Concerning the splitting variables, the new splitting expressions are $$sp\_f=x_1$$ and $$sp\_g={\overline{x}}_0$$ .

(2) The algorithm enters the next iteration and computes the new SS vectors. The new SS vectors are:

$$V_f=\{(9,10,-1,-1,1),(0,0,-1,-1,0),(9,10,-1,-1,1),(10,9,-1,-1,1),(10,9,-1,-1,1),(9,10,-1,-1,1)\},$$

$$V_g=\{(0,0,-1,-1,1),(9,10,-1,-1,0),(10,9,-1,-1,1),(10,9,-1,-1,1),(10,9,-1,-1,1),(10,9,-1,-1,1)\}.$$

The results show the following: (1) the two new SS vectors are the same; (2) the phases of all variables are determined; and (3) the next variable-mapping set to be handled is $${\chi }_0=\{{\overline{x}}_0\to {\overline{x}}_1,{\overline{x}}_0\to x_2,{\overline{x}}_0\to x_3,{\overline{x}}_0\to x_4,{\overline{x}}_0\to x_5\}$$ . Procedure 2 adds 5 nodes to the second layer of the transformation tree. Procedure 2 handles the first variable mapping in the order of the variable mappings in the set and updates $$sp\_f=x_1{\overline{x}}_0$$ and $$sp\_g=x_0{\overline{x}}_1$$ .

In the subsequent variable mapping search, the $${\overline{x}}_0\to {\overline{x}}_1$$ branch is pruned by a phase collision. The $${\overline{x}}_0\to x_2$$ , $${\overline{x}}_0\to x_3$$ and $${\overline{x}}_0\to x_4$$ branches are pruned by having different SS vectors.

(3) Then, Procedure 2 handles the variable mapping $${\overline{x}}_0\to x_5$$ and detects a candidate transformation $$T=\{x_1\to {\overline{x}}_0,{\overline{x}}_0\to x_5,x_4\to {\overline{x}}_1,{\overline{x}}_5\to x_2,{\overline{x}}_2\to x_4,{\overline{x}}_3\to {\overline{x}}_3\}$$ . After verification, this transformation is found to satisfy $$f\left(TX\right)=g\left(X\right)$$ . Therefore, f is NPN-equivalent to g.

The transformation tree for Example 3 using SS vectors is shown in Figure 3.

Figure 3 shows that this transformation tree for Example 3 has 6 branches and that the two Boolean functions are decomposed 4 times. Let us examine the detection process using SDS vectors.

(1) The SDS vectors of f and g are as follows:

$$V_f=\{(16,16,-1,-1,3,28),(19,13,-1,-1,0,64),(16,16,-1,-1,5,12),(16,16,-1,-1,4,20),(16,16,-1,-1,2,36),(16,16,-1,-1,1,52)\},$$

$$V_g=\{(13,19,-1,-1,0,64),(16,16,-1,-1,2,36),(16,16,-1,-1,1,52),(16,16,-1,-1,4,20),(16,16,-1,-1,5,12),(16,16,-1,-1,3,28)\}.$$