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

Xiao-hua LI; Ji-zhong SHEN

doi:10.1631/jzus.C1400093

Your Location：

Home >

Browse articles >

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

Electronic Engineering | Updated：2022-05-19

- An algorithm for identifying symmetric variables in the canonical OR-coincidence algebra system
- 或-符合代数系统中的对称变量检测算法
- Frontiers of Information Technology & Electronic Engineering Vol. 15, Issue 12, Pages: 1174-1182(2014)
- Affiliations：
  
  1.Campus Information Center, Zhejiang University, Hangzhou 310027, China
  2.Department of Information Science & Electronic Engineering, Zhejiang University, Hangzhou 310027, China
- Author bio：
  
  Ji-zhong SHEN, E-mail: jzshen@zju.edu.cn
- Funds：
- DOI：10.1631/jzus.C1400093
  CLC： TN431
- Received：16 March 2014，
  
  Revised：2014-11-13，
  
  Published：2014-12
- Accepted：
Scan QR Code
Xiao-hua LI, Ji-zhong SHEN. An algorithm for identifying symmetric variables in the canonical OR-coincidence algebra system[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(12): 1174-1182.
DOI：

Xiao-hua LI, Ji-zhong SHEN. An algorithm for identifying symmetric variables in the canonical OR-coincidence algebra system[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(12): 1174-1182. DOI： 10.1631/jzus.C1400093.

摘要

研究目的

逻辑变量对称性在逻辑综合、OBDD化简、故障检测、电路分析及密码学函数构造等领域具有广泛的应用。为简化或-符合代数系统中12类对称变量的检测过程，提出一种新的检测算法。

创新要点

提出新的基于或-符合展开系数对称性检测算法。该算法可实现12类对称变量的完备性检测，同样适用于与-或-非代数系统和与-异或代数系统。

研究方法

首先，分析基于或-符合展开布尔函数的子函数系数矩阵和有序子系数矩阵之间的关系（公式5），提出基于有序子系数矩阵的12类对称形式的约束条件（表3）。根据该约束条件，通过判别

图的有序特征格值，提出逻辑变量12类对称形式的快速检测算法（图4）。与其他方法相比（表7），该方法有效避免或-符合展开系数和与-异或展开系数及与-或-非展开系数之间的转换，同时解决了

图方法中的完备性问题。算法用C语言实现并用MCNC91 benchmarks（表6）进行测试。

重要结论

提出或-符合代数系统中12类对称变量的检测算法。与其他方法相比，该算法在适用的检测变量数、检测类型、检测过程的复杂度方面最优。

Abstract

To simplify the process for identifying 12 types of symmetric variables in the canonical OR-coincidence (COC) algebra system

we propose a new symmetry detection algorithm based on OR-NXOR expansion. By analyzing the relationships between the coefficient matrices of sub-functions and the order coefficient subset matrices based on OR-NXOR expansion around two arbitrary logical variables

the constraint conditions of the order coefficient subset matrices are revealed for 12 types of symmetric variables. Based on the proposed constraints

the algorithm is realized by judging the order characteristic square value matrices. The proposed method avoids the transformation process from OR-NXOR expansion to AND-OR-NOT expansion

or to AND-XOR expansion

and solves the problem of completeness in the

-map method. The application results show that

compared with traditional methods

the new algorithm is an optimal detection method in terms of applicability of the number of logical variables

detection type

and complexity of the identification process. The algorithm has been implemented in C language and tested on MCNC91 benchmarks. Experimental results show that the proposed algorithm is convenient and efficient.

关键词

Keywords

references

J. Acharya , , , A. Jafarpour , , , A. Orlitsky . . Expected query complexity of symmetric Boolean functions . . Proc. 49th Annual Allerton Conf. on Communication, Control, and Computing , , 2011 . . p.26 - - 29 . . DOI: 10.1109/Allerton.2011.6120145 http://doi.org/10.1109/Allerton.2011.6120145 . .

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 . .

J. Cheng , , , X. Chen , , , K.M. Faraj , , , 等 . . Expansion of logical function in the OR-coincidence system and the transform between it and maxterm expansion . . IEE Proc.-Comput. Dig. Tech. , , 2003 . . 150 ( ( 6 ): ): 397 - - 402 . . DOI: 10.1049/ip-cdt:20030969 http://doi.org/10.1049/ip-cdt:20030969 . .

B. 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 . .

L. Heinrich-Litan , , , P. Molitor . . Least upper bounds for the size of OBDDs using symmetry properties . . IEEE Trans. Comput. , , 2000 . . 49 ( ( 4 ): ): 360 - - 368 . . DOI: 10.1109/12.844348 http://doi.org/10.1109/12.844348 . .

S.L. Hurst . . Detection of symmetries in combinatorial functions by spectral means . . IEE J. Electron. Circ. Syst. , , 1977 . . 1 ( ( 5 ): ): 173 - - 180 . . . .

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

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

H. Kowshik , , , P.R. Kumar . . Optimal computation of symmetric Boolean functions in collocated networks . . IEEE J. Sel. Area Commun. , , 2013 . . 31 ( ( 4 ): ): 639 - - 654 . . DOI: 10.1109/JSAC.2013.130403 http://doi.org/10.1109/JSAC.2013.130403 . .

Y. Lian , , , X. Li , , , X. Chen . . Detection of partial symmetric functions based on tabular method . . Bull. Sci. Tech. , , 2005 . . 21 ( ( 2 ): ): 214 - - 217 . . . .

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 ( ( 5 ): ): 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 to error detection . . IRE Trans. Electron. Comput. , , 1954 . . EC-3 ( ( 3 ): ): 6 - - 12 . . 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 . . 57 ( ( 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 . . Mapping symmetric functions to hierarchical modules for path-delay 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.J. Falkowski . . Symmetry conditions of Boolean functions in complex Hadamard transform . . Electron. Lett. , , 1998 . . 34 ( ( 17 ): ): 1634 - - 1635 . . DOI: 10.1049/el:19981164 http://doi.org/10.1049/el:19981164 . .

I. Reed . . A class of multiple-error-correcting code and the decoding scheme . . IRE Trans Inform. Theory , , 1954 . . 4 ( ( 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 . . 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 . .

A. Shpilka , , , A. Tal . . On the minimal Fourier degree of symmetric Boolean functions . . Proc. IEEE 26th Annual Conf. on Computational Complexity , , 2011 . . p.200 - - 209 . . DOI: 10.1109/CCC.2011.16 http://doi.org/10.1109/CCC.2011.16 . .

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

M. Zhao , , , J. Lou , , , X. Chen . . Denotation and application for d j -map of symmetric function . . J. Zhejiang Univ. (Sci. Ed.) , , 2006 . . 33 ( ( 1 ): ): 62 - - 65 . . . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

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

Related Author

Xiao-hua LI

Ji-zhong SHEN

Related Institution

Campus Information Center, Zhejiang University

College of Information Science & Electronic Engineering, Zhejiang University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰