APP下载

弹性函数的平方和指标∗

2020-08-06

舰船电子工程 2020年6期

(中国电子科技集团公司第三十研究所 成都 610041)

1 引言

2 准备工作

首先给出相关免疫的概念。

定义1设f(x1,x2,…,xn)是一个n元布尔函数,其中x1,x2,…,xn是均匀分布的独立随机变量,如果f与x1,x2,…,xn中任意的m个变元xi1,xi2, …,xim统计独立,即对任意a1,a2,…,am和a,均有:

则称f是m阶相关免疫函数。

定义2平衡的m阶相关免疫函数称为m-弹性函数。

定义3f的Walsh谱为

这里,ωx=ω1x1+ω2x2+…+ωnxn。

由文献[6]得以下定理。

定理1布尔函数f(x1,x2,…,xn)是m-弹性函数当且仅当对任何a∈F2n,0≤wt(a)≤m,均有F(a)=0。

由文献[1]得以下定理。

定理2设布尔函数f(x1,x2,…,xn)是m-弹性函数,这里 ,n≥3并 且m≤n-3,则F(ω)≡0(mod2m+2)对任何ω∈{0 ,1}n成立。

由文献[2]知道有下列定理。

定理3给定布尔函数f(x1,x2,…,xn),若f是m-弹性函数(1≤m≤n-2),则degf+m≤n-1;若f是m-阶相关免疫函数(1≤m≤n-1),则degf+m≤n。

由文献[7]和文献[8]知道有下列定理。

由Parseval关系有下列定理。

由文献[4]可得下列定理。

定理6设f是0-弹性函数(即平衡函数),则

由文献[5]可得下列定理。

定理7设f(x1,x2,…,xn)是一个m-弹性函数,则

3 主要结果

这里给出并证明主要结果。

定理8设f(x1,x2,…,xn)是一个m-弹性函数,n大于或等于3且0≤m≤n-3,则

结合定理6,定理7和定理8有以下定理。

定理 9设f(x1,x2,…,xn)是一个m-弹性函数,n大于或等于3且0≤m≤n-3,则

还可以将定理9细化。

所以此时有,σf≥2n+2m+4。因此,此下界比原来给出的下界要紧一些。

3)如果f是n-3-弹性函数,则由定理2,F(ω)≡0(mod2n-1)对任何ω∈{0 ,1}n成立。由定理5,要么有4个ω满足|F(ω)|=2n-1,其余ω满足F(ω)=0;要么有1个ω满足|F(ω)|=2n,其余ω满足F(ω)=0 。由定理4,要么σf=23n-2,要 么σf=23n。

当m大于或等于n-2时,平方和指标是确定的,见下列情况。

4)当m等于n-2,n-1时,由定理3可知,f一定是仿射函数,因此一定有σf=23n。

5)考察3≤n≤6的情形。

(1)n=3;如果f是0-弹性函数且非仿射函数,由3)知σf=23n-2=27。如果f是0-弹性函数且是仿射函数。则σf=23n=29。如果f是1-弹性函数或2-弹性函数,由4)知,σf=23n=29。……

登录APP查看全文