An algorithm for identifying symmetric variables based on the order eigenvalue matrix
An algorithm for identifying symmetric variables based on the order eigenvalue matrix
复制标题
基于阶特征值矩阵的对称变量识别算法
DOI：
10.1631/fitee.1601052
复制
发表时间：
2017-10
影响因子：
3
通讯作者：
Ji-zhong Shen
中科院分区：
文献类型：
--
作者：
Xiao-hua Li;Ji-zhong Shen
为了简化布尔函数中12种对称变量的识别过程，提出了一种新的基于最小项展开或真值表的对称性检测算法。首先，根据逻辑变量的对称性定义，定义了基于真值表的阶特征值矩阵。通过分析12种对称变量的阶特征值矩阵的约束条件，提出了一种识别布尔函数对称变量的算法。该算法可用于识别有无无关项的布尔函数的对称变量。该方法避免了图解法、谱系数法和与异或展开系数法对逻辑变量个数的限制，解决了快速计算方法的完备性问题。该算法已用C语言实现，并在MCNC91基准测试程序上进行了测试。应用结果表明，与传统方法相比，新算法在逻辑变量个数、包含无关项的布尔函数、检测类型和识别过程的复杂性等方面都是一种最优的检测方法。
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 compu-tation 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.