变元可分离布尔函数与其补函数的零化子的最低次数  

Minimum Degree of Annihilators of Decomposable Boolean Functions and Their Complements

作　　者：陈华瑾[1] 戚文峰[1] 

机构地区：[1]信息工程大学网络空间安全学院,河南郑州450002

出　　处：《信息工程大学学报》2012年第6期670-675,共6页Journal of Information Engineering University

摘　　要：在仿射等价的意义下,变元可分离布尔函数f可以表示为变元互不相同的两个布尔函数g和h的和。文章研究了这类函数与其补函数的零化子的最低次数关系,结论表明,通过计算g和h的代数免疫度,可以确定f及其补函数的零化子的最低次数的大小关系并得到f的代数免疫度的上界。由于g和h的变元个数小于f的变元个数,上述结论使得计算f的代数免疫度的复杂度大大降低。最后,针对一类特殊的非变元可分离布尔函数讨论了该函数与其补函数的零化子的最低次数关系。A Boolean function f is called decomposable if it is affinely equivalent to the sum of two subfunctions g and h that depend on two disjoint subsets of coordinates. It is shown in this paper that by calculating the algebraic immunity of g and h, the magnitude of annihilators＇ minimum degrees of f and its complement can be determined. The upper bound of the algebraic immunity of f can also be found out. Since the number of variables in g and h is less than that in f, the complexity of cal- culating the algebraic immunity off can be significantly reduced. Finally, for a special kind of Bool- ean functions which are not decomposable, the relation between the minimum degree of annihilators of Boolean functions and their complements is discussed.

关 键 词：代数免疫 布尔函数 补函数 零化子 代数次数 

分 类 号：TN918.1[电子电信—通信与信息系统]