基于有序特征值矩阵的对称变量检测算法

厉晓华; 沈继忠

doi:10.1631/FITEE.1601052

Your Location：

Home >

Browse articles >

基于有序特征值矩阵的对称变量检测算法

常规文章 | Updated：2022-05-19

- 基于有序特征值矩阵的对称变量检测算法
- An algorithm for identifying symmetric variables based on the order eigenvalue matrix
- 信息与电子工程前沿（英文） 2017年18卷第10期页码：1644-1653
- Affiliations：
  
  Campus Information Center, Zhejiang University, Hangzhou 310027, China
  College of Information Science & Electronic Engineering, Zhejiang University, Hangzhou 310027, China
- Author bio：
  
  Ji-zhong SHEN, jzshen@zju.edu.cn
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61471314 and 61271124), the Zhejiang Provincial Natural Science Foundation (No. LY13F010001), and the National Key Technology R & D Program of China (Nos. 2013BAH27F01, 2013BAH27F02, and 2013BAH27F03)
- DOI：10.1631/FITEE.1601052
  中图分类号： TN431
- 收稿：2016-03-05，
  
  修回：2017-11-;3，
  
  纸质出版：2017-10
- Accepted：
Scan QR Code
厉晓华, 沈继忠. 基于有序特征值矩阵的对称变量检测算法[J]. 信息与电子工程前沿（英文）, 2017,18(10):1644-1653.

Xiao-hua LI, Ji-zhong SHEN. An algorithm for identifying symmetric variables based on the order eigenvalue matrix[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1644-1653.
厉晓华, 沈继忠. 基于有序特征值矩阵的对称变量检测算法[J]. 信息与电子工程前沿（英文）, 2017,18(10):1644-1653. DOI： 10.1631/FITEE.1601052.

Xiao-hua LI, Ji-zhong SHEN. An algorithm for identifying symmetric variables based on the order eigenvalue matrix[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1644-1653. DOI： 10.1631/FITEE.1601052.

摘要

为简化布尔函数中12类对称变量的检测过程，本文提出基于最小项展开或真值表的对称性检测新算法。首先，根据逻辑变量的对称性定义，定义基于真值表的有序特征值矩阵。通过分析12类对称变量有序特征值矩阵的约束条件，提出对称变量检测算法。该算法适用于含无关项布尔函数和不含无关项布尔函数中的对称变量检测。该算法避免了图形方法、谱系数方法、与-异或方法中的变量数限制，也解决了快速算法中的完备性问题。算法用C语言实现并对MCNC91标准电路进行测试。结果表明，与传统方法相比，新算法在适用的变量数、检测含无关项布尔函数、检测类型、检测过程复杂度方面是最优算法。

Abstract

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.

关键词

Keywords

references

E. Blais , , , A. Weinstein , , , Y. Yoshida . . Partially symmetric functions are efficiently isomorphism-testable . . Proc. IEEE 53rd Annual Symp. on Foundation of Computer Science , , 2012 . . p.551 - - 560 . . DOI: 10.1109/FOCS.2012.53 http://doi.org/10.1109/FOCS.2012.53 . .

G. Boole . . Investigation of the Lows of Thought . . New York, USA , , 1854 . . .

D.I. Cheng , , , M. Sadowska . . Verifying equivalence of functions with unknown input correspondence . . IEEE Trans. Comput. , , 1993 . . 41 ( ( 6 ): ): 84 - - 85 . . DOI: 10.1109/EDAC.1993.386496 http://doi.org/10.1109/EDAC.1993.386496 . .

B.J. Falkowski , , , S. Kannurao . . Identification of Boolean symmetries in spectral domain of Reed-Muller transform . . Electron. Lett. , , 1999 . . 35 ( ( 16 ): ): 1315 - - 1316 . . DOI: 10.1049/el:19990955 http://doi.org/10.1049/el:19990955 . .

S.L. Hurst . . Detection of symmetries in combinatorial functions by spectral means . . IEE J. Electron. Circ. Syst. , , 1977 . . 1 ( ( 5 ): ): 173 - - 180 . . DOI: 10.1049/ij-ecs:19770026 http://doi.org/10.1049/ij-ecs:19770026 . .

S.L. Hurst . . The Logic Processing of Digital Systems . . Crane-Russak, New York , , 1978 . . .

S. Kannurao , , , B. Falkowski . . Identification of complement single variable symmetry in Boolean functions through Walsh transform . . Proc. IEEE Int. Symp. on Circuits and Systems , , 2002 . . p.745 - - 748 . . DOI: 10.1109/ISCAS.200.101081 http://doi.org/10.1109/ISCAS.200.101081 . .

S. Kannurao , , , B. Falkowski . . Single variable symmetry conditions in Boolean functions through Reed-Muller transform . . Proc. IEEE Int. Symp. on Circuits and Systems , , 2003 . . p.680 - - 683 . . DOI: 10.1109/ISCAS.2003.1206200 http://doi.org/10.1109/ISCAS.2003.1206200 . .

B. Kim , , , D. Dietmeyer . . Multilevel logic synthesis of symmetric switching functions . . IEEE Trans. Comput.-Aided Des. , , 1991 . . 10 ( ( 9 ): ): 436 - - 446 . . DOI: 10.1109/43.75627 http://doi.org/10.1109/43.75627 . .

Y. Lai , , , M. Pedram . . Boolean matching using binary decision diagrams with application to logic synthesis and verification . . IEEE Int. Conf. on Computer Design: VLSI in Computers and Processors , , 1992 . . p.452 - - 458 . . DOI: 10.1109/ICCD.1992.276313 http://doi.org/10.1109/ICCD.1992.276313 . .

X. Li , , , J. Shen . . An algorithm for identifying symmetric variables in the canonical Reed–Muller algebra system . . J. Circ. Syst. Comput. , , 2016 . . 25 ( ( 10 ): ): 1650126 DOI: 10.1142/S0218126616501267 http://doi.org/10.1142/S0218126616501267 . .

A. Mishchenko . . Fast computation of symmetries in Boolean functions . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 2003 . . 22 ( ( 11 ): ): 1588 - - 1593 . . DOI: 10.1109/TCAD.2003.818371 http://doi.org/10.1109/TCAD.2003.818371 . .

A. Mukhopadhyay . . Detection of total or partial symmetry of a switching function with the use of decomposition charts . . IEEE Trans. Electron. Comput. , , 1963 . . EC ( ( 12 ): ): 553 - - 557 . . DOI: 10.1109/PGEC.1963.263654 http://doi.org/10.1109/PGEC.1963.263654 . .

D.E. Muller . . Application of Boolean algebra to switching circuit design and error detection . . IRE Trans. Electron. Comput. , , 1954 . . EC ( ( 3 ): ): 6 - - 14 . . DOI: 10.1109/IREPGELC.1954.6499441 http://doi.org/10.1109/IREPGELC.1954.6499441 . .

J. Peng , , , Q. Wu , , , H. Kan . . On symmetric Boolean functions with high algebraic immunity on even number of variables . . IEEE Trans. Inform. Theory , , 2011 . . 157 ( ( 10 ): ): 7205 - - 7220 . . DOI: 10.1109/TIT.2011.2132113 http://doi.org/10.1109/TIT.2011.2132113 . .

H. Rahaman , , , D.K. Das , , , B.B. Bhattacharya . . A new synthesis of symmetric functions . . Proc. 7th Asia and South Pacific and 15th Int. Conf. on VLSI Design , , 2002 . . p.160 - - 165 . . DOI: 10.1109/ASPDAC.2002.994910 http://doi.org/10.1109/ASPDAC.2002.994910 . .

H. Rahaman , , , D.K. Das , , , B.B. Bhattacharya . . Mapping symmetric functions to hierarchical modules for pathdelay fault testability . . Proc. 12th Asian Test Symp. , , 2003 . . p.284 - - 289 . . DOI: 10.1109/ATS.2003.1250824 http://doi.org/10.1109/ATS.2003.1250824 . .

S. Rahardja , , , B. Falkowski . . Symmetry conditions of Boolean functions in complex Hadamard transform electron . . Electron. Lett. , , 1998 . . 34 ( ( 17 ): ): 1634 - - 1635 . . DOI: 10.1049/el:19981164 http://doi.org/10.1049/el:19981164 . .

I.S. Reed . . A class of multiple-error-correcting code and the decoding scheme . . IRE Trans. Electron. Comput. , , 1954 . . EC ( ( 4 ): ): 38 - - 49 . . DOI: 10.1109/TIT.1954.1057465 http://doi.org/10.1109/TIT.1954.1057465 . .

J.E. Rice , , , J.C. Muzio . . Antisymmetries in the realization of Boolean functions . . Proc. IEEE Int. Symp. on Circuits and Systems , , 2002 . . p.69 - - 72 . . DOI: 10.1109/ISCAS.2002.1010390 http://doi.org/10.1109/ISCAS.2002.1010390 . .

H. Wang , , , J. Peng . . On 2 k -variable symmetric Boolean functions with maximum algebraic immunity . . IEEE Trans. Inform. Theory , , 2012 . . 58 ( ( 8 ): ): 5612 - - 5624 . . DOI: 10.1109/TIT.2012.2201350 http://doi.org/10.1109/TIT.2012.2201350 . .

X. Wu , , , X. Chen , , , S.L. Hurst . . Mapping of Reed-Muller coefficients and the minimisation of exclusive ORswitching functions . . IEE Proc. E , , 1982 . . 129 ( ( 1 ): ): 15 - - 20 . . DOI: 10.1049/ip-e:19820004 http://doi.org/10.1049/ip-e:19820004 . .

M. Young , , , S. Muroga . . Symmetric minimal covering problem and minimal PLA's with symmetric variables . . IEEE Trans. Comput. , , 1985 . . 34 ( ( 6 ): ): 312 - - 318 . . DOI: 10.1109/TC.1985.5009404 http://doi.org/10.1109/TC.1985.5009404 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

An algorithm for identifying symmetric variables in the canonical OR-coincidence algebra system