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

 ORCID:

Ji-zhong SHEN

http://orcid.org/0000-0002-9031-2379

-   Go to

Article info.
Open peer comments

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

http://doi.org/10.1631/FITEE.1601052


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",
volume="18",
number="10",
pages="1644-1653",
year="2017",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1601052"
}

%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

TY - JOUR
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


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.

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

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

关键词:布尔函数;对称变量;布尔逻辑代数系统;有序特征值矩阵;真值表

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

Reference

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

[20]EC(4):38-49.

[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

<1>

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