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.

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

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