An algorithm for identifying symmetric variables based on the order eigenvalue matrix  

作　　者：Xiao-hua LI Ji-zhong SHEN 

机构地区：[1]Campus Information Center, Zhejiang University, Hangzhou 310027, China [2]College of lnformation Science & Electronic Engineering, Zhejiang University, Hangzhou 310027, China

出　　处：《Frontiers of Information Technology & Electronic Engineering》2017年第10期1644-1653,共10页信息与电子工程前沿（英文版）

基　　金：supported by the National Natural Science Foundation of China(Nos.61471314 and 61271124);the Zhejiang Provincial Natural Science Foundation(No.LY13F010001);the National Key Technology R&D Program of China(Nos.2013BAH27F01,2013BAH27F02,and 2013BAH27F03)

摘　　要：To simplify the process for identifying 12 types of symmetric variables in Boolean functions, we propose a new symmetry detection algorithm based on minterm expansion or the truth table. First, the order eigenvalue matrix based on a truth table is defined according to the symmetry definition of a logic variable. By analyzing the constraint conditions of the order eigenvalue matrix for 12 types of symmetric variables, an algorithm is proposed for identifying symmetric variables of the Boolean function. This algorithm can be applied to identify the symmetric variables of Boolean functions with or without don't-care terms. The proposed method avoids the restriction by the number of logic variables of the graphical method, spectral coefficient methods, and AND-XOR expansion coefficient methods, and solves the problem of completeness in the fast computation method. The algorithm has been implemented in C language and tested on MCNC91 benchmarks. The application results show that, compared with the traditional methods, the new algorithm is an optimal detection method in terms of the applicability of the number of logic variables, the Boolean function including don't-care terms, detection type, and complexity of the identification process.To simplify the process for identifying 12 types of symmetric variables in Boolean functions, we propose a new symmetry detection algorithm based on minterm expansion or the truth table. First, the order eigenvalue matrix based on a truth table is defined according to the symmetry definition of a logic variable. By analyzing the constraint conditions of the order eigenvalue matrix for 12 types of symmetric variables, an algorithm is proposed for identifying symmetric variables of the Boolean function. This algorithm can be applied to identify the symmetric variables of Boolean functions with or without don＇t-care terms. The proposed method avoids the restriction by the number of logic variables of the graphical method, spectral coefficient methods, and AND-XOR expansion coefficient methods, and solves the problem of completeness in the fast computation method. The algorithm has been implemented in C language and tested on MCNC91 benchmarks. The application results show that, compared with the traditional methods, the new algorithm is an optimal detection method in terms of the applicability of the number of logic variables, the Boolean function including don＇t-care terms, detection type, and complexity of the identification process.

关 键 词：Boolean function Symmetric variable Boolean logic algebra system Order eigenvalue matrix Truth table 

分 类 号：O174[理学—数学]