Full Text:   <748>

Summary:  <181>

CLC number: TN431

On-line Access: 2017-12-04

Received: 2016-03-05

Revision Accepted: 2016-08-14

Crosschecked: 2017-11-03

Cited: 0

Clicked: 1785

Citations:  Bibtex RefMan EndNote GB/T7714


Ji-zhong SHEN


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2017 Vol.18 No.10 P.1644-1653


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

Author(s):  Xiao-hua Li, Ji-zhong Shen

Affiliation(s):  Campus Information Center, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s):   jzshen@zju.edu.cn

Key Words:  Boolean function, Symmetric variable, Boolean logic algebra system, Order eigenvalue matrix, Truth table

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.

@article{title="An algorithm for identifying symmetric variables based on the order eigenvalue matrix",
author="Xiao-hua Li, Ji-zhong Shen",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T An algorithm for identifying symmetric variables based on the order eigenvalue matrix
%A Xiao-hua Li
%A Ji-zhong Shen
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 10
%P 1644-1653
%@ 2095-9184
%D 2017
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1601052

T1 - An algorithm for identifying symmetric variables based on the order eigenvalue matrix
A1 - Xiao-hua Li
A1 - Ji-zhong Shen
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 10
SP - 1644
EP - 1653
%@ 2095-9184
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1601052

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.




Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Blais, E., Weinstein, A., Yoshida, Y., 2012. Partially symmetric functions are efficiently isomorphism-testable. Proc. IEEE 53rd Annual Symp. on Foundation of Computer Science, p.551-560.

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

[3]Cheng, D.I., Sadowska, M., 1993. Verifying equivalence of functions with unknown input correspondence. IEEE Trans. Comput., 41(6):81-85.

[4]Falkowski, B.J., Kannurao, S., 1999. Identification of Boolean symmetries in spectral domain of Reed-Muller transform. Electron. Lett., 35(16):1315-1316.

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

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

[7]Kannurao, S., Falkowski, B., 2002. Identification of complement single variable symmetry in Boolean functions through Walsh transform. Proc. IEEE Int. Symp. on Circuits and Systems, p.745-748.

[8]Kannurao, S., Falkowski, B., 2003. Single variable symmetry conditions in Boolean functions through Reed-Muller transform. Proc. IEEE Int. Symp. on Circuits and Systems, p.680-683.

[9]Kim, B., Dietmeyer, D., 1991. Multilevel logic synthesis of symmetric switching functions. IEEE Trans. Comput.-Aided Des., 10(9):436-446.

[10]Lai, Y., Pedram, M., 1992. Boolean matching using binary decision diagrams with application to logic synthesis and verification. IEEE Int. Conf. on Computer Design: VLSI in Computers and Processors, p.452-458.

[11]Li, X., Shen, J., 2016. An algorithm for identifying symmetric variables in the canonical Reed–Muller algebra system. J. Circ. Syst. Comput., 25(10):1650126.

[12]Mishchenko, A., 2003. Fast computation of symmetries in Boolean functions. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 22(11):1588-1593.

[13]Mukhopadhyay, A., 1963. Detection of total or partial symmetry of a switching function with the use of decomposition charts. IEEE Trans. Electron. Comput., EC(12): 553-557.

[14]Muller, D.E., 1954. Application of Boolean algebra to switching circuit design and error detection. IRE Trans. Electron. Comput., EC(3):6-14.

[15]Peng, J., Wu, Q., Kan, H., 2011. On symmetric Boolean functions with high algebraic immunity on even number of variables. IEEE Trans. Inform. Theory, 157(10):7205-7220.

[16]Rahaman, H., Das, D.K., Bhattacharya, B.B., 2002. A new synthesis of symmetric functions. Proc. 7th Asia and South Pacific and 15th Int. Conf. on VLSI Design, p.160-165.

[17]Rahaman, H., Das, D.K., Bhattacharya, B.B., 2003. Mapping symmetric functions to hierarchical modules for path-delay fault testability. Proc. 12th Asian Test Symp., p.284-289.

[18]Rahardja, S., Falkowski, B., 1998. Symmetry conditions of Boolean functions in complex Hadamard transform electron. Electron. Lett., 34(17):1634-1635.

[19]Reed, I.S., 1954. A class of multiple-error-correcting code and the decoding scheme. IRE Trans. Electron. Comput.,


[21]Rice, J.E., Muzio, J.C., 2002. Antisymmetries in the realization of Boolean functions. Proc. IEEE Int. Symp. on Circuits and Systems, p.69-72.

[22]Wang, H., Peng, J., 2012. On 2k-variable symmetric Boolean functions with maximum algebraic immunity. IEEE Trans. Inform. Theory, 58(8):5612-5624.

[23]Wu, X., Chen, X., Hurst, S.L., 1982. Mapping of Reed-Muller coefficients and the minimisation of exclusive OR-switching functions. IEE Proc. E, 129(1):15-20.

[24]Young, M., Muroga, S., 1985. Symmetric minimal covering problem and minimal PLA’s with symmetric variables. IEEE Trans. Comput., 34(6):312-318.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE