Similar articles

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

或-符合代数系统中的对称变量检测算法

逻辑变量对称性在逻辑综合、OBDD化简、故障检测、电路分析及密码学函数构造等领域具有广泛的应用。为简化或-符合代数系统中12类对称变量的检测过程，提出一种新的检测算法。 提出新的基于或-符合展开系数对称性检测算法。该算法可实现12类对称变量的完备性检测，同样适用于与-或-非代数系统和与-异或代数系统。 首先，分析基于或-符合展开布尔函数的子函数系数矩阵和有序子系数矩阵之间的关系（公式5），提出基于有序子系数矩阵的12类对称形式的约束条件（表3）。根据该约束条件，通过判别图的有序特征格值，提出逻辑变量12类对称形式的快速检测算法（图4）。与其他方法相比（表7），该方法有效避免或-符合展开系数和与-异或展开系数及与-或-非展开系数之间的转换，同时解决了图方法中的完备性问题。算法用C语言实现并用MCNC91 benchmarks（表6）进行测试。 提出或-符合代数系统中12类对称变量的检测算法。与其他方法相比，该算法在适用的检测变量数、检测类型、检测过程的复杂度方面最优。
对称变量；图；或-符合代数系统；布尔函数

[1]Acharya, J., Jafarpour, A., Orlitsky, A., 2011. Expected query complexity of symmetric Boolean functions. Proc. 49th Annual Allerton Conf. on Communication, Control, and Computing, p.26-29.

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

[3]Cheng, J., Chen, X., Faraj, K.M., et al., 2003. Expansion of logical function in the OR-coincidence system and the transform between it and maxterm expansion. IEE Proc.-Comput. Dig. Tech., 150(6):397-402.

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

[5]Heinrich-Litan, L., Molitor, P., 2000. Least upper bounds for the size of OBDDs using symmetry properties. IEEE Trans. Comput., 49(4):360-368.

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

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

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

[9]Kowshik, H., Kumar, P.R., 2013. Optimal computation of symmetric Boolean functions in collocated networks. IEEE J. Sel. Area Commun., 31(4):639-654.

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

[11]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(5):553-557.

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

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

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

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

[16]Reed, I., 1954. A class of multiple-error-correcting code and the decoding scheme. IRE Trans Inform. Theory, 4(4):38-49.

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

[18]Shpilka, A., Tal, A., 2011. On the minimal Fourier degree of symmetric Boolean functions. Proc. IEEE 26th Annual Conf. on Computational Complexity, p.200-209.

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

[20]Zhao, M., Lou, J., Chen, X., 2006. Denotation and application for d_j-map of symmetric function. J. Zhejiang Univ. (Sci. Ed.), 33(1):62-65 (in Chinese).