基于谱系数的反对称变量检测算法
|
摘要
为简化布尔函数6类反对称变量的检测过程,提出了基于谱系数的检测算法.从逻辑变量反对称的定义出发,在分析反对称逻辑变量Rademacher-Walsh(RW)变换谱系数特性的基础上,提出了基于RW变换检测CN(xi|xj)、CE(xi|xj)、CS(xi|xj)、CS(xi|xj)、CS(xj|xi)、CS(xj|xi)6类反对称逻辑变量的算法.应用结果表明,该方法具有易操作和计算机编程简单等优点.
We propose a new symmetry detection algorithm based on the spectral technique in order to simplify the process of detecting 6types of antisymmetric variables in the Boolean function.According to the antisymmetry definition of the logical variables,a new antisymmetric detection algorithm used for identifying six types of antisymmetric logical variables including CN(xi|xj),CE(xi|xj),CS(xi|xj),CS(xi|xj),CS(xj|xi)and CS(xj|xi)is proposed,which resolves the lack of the effective methods for identifying antisymmetric variables.The application results show that this method is convenient for the operation and suitable for computer programming.
We propose a new symmetry detection algorithm based on the spectral technique in order to simplify the process of detecting 6types of antisymmetric variables in the Boolean function.According to the antisymmetry definition of the logical variables,a new antisymmetric detection algorithm used for identifying six types of antisymmetric logical variables including CN(xi|xj),CE(xi|xj),CS(xi|xj),CS(xi|xj),CS(xj|xi)and CS(xj|xi)is proposed,which resolves the lack of the effective methods for identifying antisymmetric variables.The application results show that this method is convenient for the operation and suitable for computer programming.
引文
[1]陈偕雄,沈继忠.近代数字理论[M].杭州:浙江大学出版社,2001.CHEN Xiexiong,SHEN Jizhong.Modern Digital Theory[M].Hangzhou:Zhejiang University Press,2001.
[2]HEINRICH-LITAN L,MOLITOR P.Least upper bounds for the size of OBDDs using symmetry properties[J].IEEE Transations On Computers,2000,49(4):360-368.
[3]RAHAMAN H,DAS D,BHATTACHARYA B.Mapping symmetric functions to hierarchical modules for path-delay fault testability[C]//Proceeding of the12th Asian Test Symposium.Xian:IEEE,2003:284-289.
[4]PENG Jie,WU Quanshui,KAN Haibin.On symmetric boolean functions with high algebraic immunity on even number of variables[J].IEEE Transations on Information Theory,2011,57(10):7205-7220.
[5]SHPILKA A,TAL A.On the minimal fourier degree of symmetric boolean functions[C]//The 26th Annual IEEE Conference on Computational Complexity.San Jose:IEEE,2011:200-209.
[6]CHOWDURY M,HASAN G,TALUKDER K.A composition technique of multiple switching functions based on BDD[C]//Computer and Information Technology 13th International Conference.Dhaka:IEEE,2010:337-342.
[7]ACHARYA J,JAFARPOUR A,ORLITSKY A.Expected query complexity of symmetric boolean functions[C]//Communication,Control and Computing49th Annual Allerton Conference.Urbana:IEEE,2011:26-29.
[8]MUKHOPADHYAY A.Detection of total or partial symmetry of a switching function with the use of decomposition charts[J].IEEE Transations on Electronic Computers,1963,12(5):553-557.
[9]HURST S L.Detection of symmetries in combinatorial functions by spectral means[J].Electronic Circuits and Systems,1977,1(5):173-180.
[10]BOGDAN J,S KANNURAO.Skew symmetry detection using the walsh spectral coefficients[C]//IEEE International Symposium on Circuits and Systems.Geneva:IEEE,2000:321-324.
[11]RICE J E,MUZIO J C.Anti symmetries in the realization of Boolean functions[C]//IEEE International Symposium on Circuits and Systems.Scottsdale:IEEE,2002,4(4):69-72.
[12]厉晓华,杭国强.逻辑函数对称变量检测算法[J].电路与系统学报,2013,18(2):31-35.LI Xiaohua,HANG Guoqiang.The algorithm for identifying symmetric variable of logical function[J].Journal of Circuits and Systems,2013,18(2):31-35.
[2]HEINRICH-LITAN L,MOLITOR P.Least upper bounds for the size of OBDDs using symmetry properties[J].IEEE Transations On Computers,2000,49(4):360-368.
[3]RAHAMAN H,DAS D,BHATTACHARYA B.Mapping symmetric functions to hierarchical modules for path-delay fault testability[C]//Proceeding of the12th Asian Test Symposium.Xian:IEEE,2003:284-289.
[4]PENG Jie,WU Quanshui,KAN Haibin.On symmetric boolean functions with high algebraic immunity on even number of variables[J].IEEE Transations on Information Theory,2011,57(10):7205-7220.
[5]SHPILKA A,TAL A.On the minimal fourier degree of symmetric boolean functions[C]//The 26th Annual IEEE Conference on Computational Complexity.San Jose:IEEE,2011:200-209.
[6]CHOWDURY M,HASAN G,TALUKDER K.A composition technique of multiple switching functions based on BDD[C]//Computer and Information Technology 13th International Conference.Dhaka:IEEE,2010:337-342.
[7]ACHARYA J,JAFARPOUR A,ORLITSKY A.Expected query complexity of symmetric boolean functions[C]//Communication,Control and Computing49th Annual Allerton Conference.Urbana:IEEE,2011:26-29.
[8]MUKHOPADHYAY A.Detection of total or partial symmetry of a switching function with the use of decomposition charts[J].IEEE Transations on Electronic Computers,1963,12(5):553-557.
[9]HURST S L.Detection of symmetries in combinatorial functions by spectral means[J].Electronic Circuits and Systems,1977,1(5):173-180.
[10]BOGDAN J,S KANNURAO.Skew symmetry detection using the walsh spectral coefficients[C]//IEEE International Symposium on Circuits and Systems.Geneva:IEEE,2000:321-324.
[11]RICE J E,MUZIO J C.Anti symmetries in the realization of Boolean functions[C]//IEEE International Symposium on Circuits and Systems.Scottsdale:IEEE,2002,4(4):69-72.
[12]厉晓华,杭国强.逻辑函数对称变量检测算法[J].电路与系统学报,2013,18(2):31-35.LI Xiaohua,HANG Guoqiang.The algorithm for identifying symmetric variable of logical function[J].Journal of Circuits and Systems,2013,18(2):31-35.