Research Of Boolean Function NPN Equivalence Classification And Equivalence Matching

The equivalence classification of Boolean functions is one of the most important problems in logic design and switching theory.The goal of Boolean function equivalence classification is to find Boolean functions that are equivalent to each other by a classification rules.Classification of switching functions is a way to handle a large amount of switching functions by a small set of representative functions.Boolean function equivalence matching is an algorithm that was used to judge whether two Boolean functions are equivalent under a classification criterion.The two equivalent Boolean functions can use the circuit of one of the Boolean functions to realize the circuit of the other Boolean function.Boolean function matching has important applicants in the field of logic synthesis,and it has become one of the research hot spots.This dissertation studies Boolean function equivalence classification and equivalence matching under the NPN equivalent criterion.Based on the study of group algebra theory,this dissertation studies Boolean function NPN equivalence classification enumeration problem.It constructs the??group by all permutation mapping and negation mapping,and transforms the problem of NP Boolean equivalence classification to the equivalence class problem acting on the??group.It utilizes P?olya enumeration method and Burnside lemma to derivate a new method for computing Boolean function NP and NPN equivalence classification.This method reduces the computing complexity of NP equivalence classification from2^2mto?8?+1)!for8)inputs Boolean function,which improves the efficiency of Boolean function NP and NPN equivalence classification dramatically.Using the method of this dissertation proposed,we compute the number of NP AND NPN Boolean equivalence classification of 3-10 variables Boolean functions.Boolean function NPN equivalence matching algorithm has been applied widelyin the technology mapping and combination logic verification.People propose several different kinds of Boolean function NPN equivalence matching methods.Pairwise comparison and based-canonical Boolean function NPN equivalence matching algorithm are studied in this dissertation.Through the studies of the Boolean function NPN equivalence matching algorithms proposed by the previous researchers,this dissertation proposes two pairwise comparison and one based-canonical Boolean function NPN equivalence matchingalgorithm.Through the running of these three algorithms,the dissertation tests the search space and matching speed for 7-22 variables Boolean functions,and compares the test results with the algorithm proposed by the reference[1].Based on the Binary Decision Diagrams?BDD?representation of Boolean function,this dissertation proposes a combined signature i.e.Structural Signature?SS?.According to the independence between the 1signature and symmetry of input variable with NP transformation and the change of the 1signature of the two variables that have a mapping relation are synchronal,this dissertation proposes a Boolean function NPN equivalence matching algorithm base on structural signature.The algorithm uses the SS values of variables to create variable mapping.Through variable symmetry,phase collision check and variable group,the algorithm filters the error variable mappings and deletes the error NP transformation.The using of these methods reduces the search space and improves Boolean function NPN equivalence matching speed.This dissertation proposes structural Boolean difference signature?SDS?combining the structural signature and the Boolean difference operation of Shannon cofactor.The introduction of Boolean difference signature can extract the independent variables of Boolean function,and distinguish the different variables better relative to structural signature,and search correct variable mapping and NP transformation faster.The proposal of structural Boolean difference signature reduces the search space and speeds up matching process better.The dissertation analyzes and explains the superiority of the Boolean function NPN equivalence matching algorithm based on the SDS from the number of NP transformations searched,the number of candidate NP transformations and the number of decompositions.The dissertation also proposes a based-canonical Boolean function NPN equivalence matching algorithm.It explains that each Boolean function has an unique DC?Boolean Difference and Cofactor?signature vector.The Boolean function having the maximum DC signature vector is the canonical form of its NPN equivalence class in this algorithm.It sorts the variables of Boolean function by the comparison of DC signature value and computes the canonical form of Boolean function quickly to implement fast Boolean function NPN equivalence matching finally.