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

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

Keywords

Boolean function / Symmetric variable / Boolean logic algebra system / Order eigenvalue matrix / Truth table

References

[1] Blais , E., Weinstein , A., Yoshida , Y., 2012. Partially sym-metric functions are efficiently isomorphism-testable. Proc. IEEE 53rd Annual Symp. on Foundation of Com-puter Science,p.551–560. https://doi.org/10.1109/FOCS.2012.53

[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. https://doi.org/10.1109/EDAC.1993.386496

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

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

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

[7] Kannurao , S.,Falkowski , B., 2002. Identification of comple-ment single variable symmetry in Boolean functions through Walsh transform. Proc. IEEE Int. Symp. on Circuits and Systems, p.745–748. https://doi.org/10.1109/ISCAS.200.101081

[8] Kannurao , S., Falkowski , B., 2003. Single variable symmetry conditions in Boolean functions through Reed-Muller transform. Proc. IEEE Int. Symp. on Circuits and Sys-tems,p.680–683. https://doi.org/10.1109/ISCAS.2003.1206200

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

[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. https://doi.org/10.1109/ICCD.1992.276313

[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. https://doi.org/10.1142/S0218126616501267

[12] Mishchenko , A., 2003. Fast computation of symmetries in Boolean functions. IEEE Trans. Comput.-Aided Des. In-tegr. Circ. Syst., 22(11):1588–1593. https://doi.org/10.1109/TCAD.2003.818371

[13] Mukhopadhyay , A., 1963. Detection of total or partial sym-metry of a switching function with the use of decompo-sition charts. IEEE Trans. Electron. Comput., EC(12): 553–557. https://doi.org/10.1109/PGEC.1963.263654

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

[15] Peng , J., Wu , Q., Kan , H., 2011. On symmetric Boolean func-tions with high algebraic immunity on even number of variables. IEEE Trans. Inform. Theory, 157(10):7205–7220. https://doi.org/10.1109/TIT.2011.2132113

[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. https://doi.org/10.1109/ASPDAC.2002.994910

[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. https://doi.org/10.1109/ATS.2003.1250824

[18] Rahardja , S., Falkowski , B., 1998. Symmetry conditions of Boolean functions in complex Hadamard transform elec-tron. Electron. Lett., 34(17):1634–1635. https://doi.org/10.1049/el:19981164

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

[20] Rice , J.E., Muzio , J.C., 2002. Antisymmetries in the realiza-tion of Boolean functions. Proc. IEEE Int. Symp. on Circuits and Systems, p.69–72. https://doi.org/10.1109/ISCAS.2002.1010390

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

[22] 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. https://doi.org/10.1049/ip-e:19820004

[23] Young , M., Muroga , S., 1985. Symmetric minimal covering problem and minimal PLA’s with symmetric variables. IEEE Trans. Comput., 34(6):312–318. https://doi.org/10.1109/TC.1985.5009404

RIGHTS & PERMISSIONS

2017 Zhejiang University and Springer-Verlag GmbH Germany