较大码重最优冲突回避码的具体构造

黄必昌

（百色学院数学与统计学院,广西 百色 533000）

为了便于阅读，采用的符号与文献[1]一致.

设Zn表示模n的剩余类环，Z∗n表示Zn{0}.对于k阶子集A⊆Zn，定义A的差集为多重集合

Δ(A)={x-y(modn)：x，y∈A，x≠y}.

设C是Zn一些k阶子集A⊆Zn的集合，若其满足以下条件

Δ(A1)∩Δ(A2)=∅，∀A1，A2∈C,A1≠A2.

则C 称作长度为n重量为k的冲突回避码（Conflict-avoiding Code 简记CAC），称A∈C 为码字.一般情况下，用符号CAC(n,k)表示所有长度为n重量为k的冲突回避码.

记｜C｜为码C的码字个数，设

M(n，k)=max {｜C｜∈CAC(n,k)}.

若｜C｜=M(n,k)，则称码C ∈CAC(n,k)为最优码.

冲突回避码作为协议序列被应用于无反馈多分址信道（冲突信道）[2-3].对于冲突回避码C∈CAC(n,k)，最优冲突回避码能保证最多的用户有效可靠地传输信息.码字的重量k（汉明码重量）表示用户在每个时段的n个时槽里发送k个数据包[4].

设是A⊆Zn一个码字，若可以写成A={0,g,2g,…,(k-1)g},g∈Z∗n的形式，则称A为等差（equidifference）码字.g称为A的生成元.易知，Δ(A)={±g,± 2g,…,±(k-1)g}.若码C ∈CAC(n,k)中的每个码字都是等差码字，则称为C 等差码.类似的，符号CACe(n,k)表示所有长度为n重量为k的等差码.用符号Γ(C)表示等差码C 所有码字生成元的集合.等差码是一类差集不同元素的个数比较少的码字，相应的会得到较多的码字，所以在构造最优码时经常考虑它.

目前，当k=3 时的最优冲突回避码构造证明已经基本解决[5-10].当k=3,4,5,6 的最优冲突回避码具体构造有些结果[4,11].对码重k>7 的最优冲突回避码具体构造取得的结果很少[1].本文利用欧拉函数和同余数在整数环的特性给出一种构造等差码新的构造方法，得到k=8,9,10,11,12时最优冲突回避码构造的具体构造，码长由n=(k-1)p推广为码长n=(k-1)pr，其中r为为任意的正整数.改进文献[1]的结果.

1 已有的相关构造

设奇素数p=2em+1，θ∈Z∗p是Z∗p的生成元，设H2e0={θ2es:s=0,1,…,m-1}是Z∗p的m阶乘法子群，则有陪集，且称Hi2e为2e阶分圆类.若jt∈Hi2e,0≤i≤2e-1.则称{j0,j1,…,j2e-1}一个为2e阶分圆类代表系.那么，以下是一些已有的构造.

引理1[4]设e≥1 和s>1 都是整数，p=2em+1 是素数且使得每一个(i-es,i-(e-1)s,…,i+(e-1)s),1≤i≤s-1 和(±s,± 2s,…,±es)都各自形成一个2e阶分圆类代表系.那么存在一个码C∈CACe(sp,k=es+1)包含m个码字，且满足ZspΔ(C)=pZsp.

引理2[11]若m>s，则引理1构造的码C∈CACe(sp,k=es+1)是最优的.

引理3[4]设k≥3,L1,L2和s都是正整数，且s|L1，gcd(l,L2)=1,l=2,3,…,(k-1).设C1∈CACe(L1,k)包含m1个码字A1,A2,…,Am1使得

设C2∈CACe(sL2,k)包含m2个码字.设码C是由

生成.则C∈CACe(L1L2,k)且包含m1L1+m2个码字.

当前，利用引理1和引理2来具体构造一些最优冲突回避码.再利用引理3复合构造出一系列的冲突回避码C∈CACe((k-1)pi,k)[1,4].但是，实际情况下，引理3很难得到最优C∈CACe((k-1)pi,k).本文首次利用欧拉函数和同余数的特性，对Z∗pr进行划分，得到类似于引理2的一般构造，并给出具体构造码重k=8,9,10,11,12时最优冲突回避码的一系列新结果.

2 新的构造方法及其证明

设n为一个正整数，称G={a|(a,n)=1,a∈Z*n}是Z∗n简约剩余系，显然，G={a|(a,n)=1,a∈Z*n}是一个乘法群.且|G|=Φ(n)，其中Φ(n)是欧拉函数.设p=2m+1 是奇素数，r为正整数，Gj={a|(a,n)=1,a∈},1≤j≤r.乘法子群，则|Gj|=Φ(pj).设θj∈Gj,j=1,2,…,r.是Gj的一个生成元，H2j0={θ2s:s=0,1,…,m-1},1≤j≤r是Gj={a|(a,n)=1,a∈}的m阶乘法子群，则Gj有陪集分解：Gj=Hj20∪Hj21,其中Hj21=θj1Hj20,称陪集Hj2i为2阶分圆类.若di∈H2ji,0≤i≤1.则称{d0,d1}为Gj的一个2阶分圆类代表系.下面得到如下构造.

定理1设s,r是正整数，p是奇素数且使得每一个(i-s,i),1≤i≤s-1 和(±s)都各自形成Gj,j=1,2,…,r.的一个2 阶分圆类代表系.那么存在一个码C∈CACe(spr,k=s+1)包含个码字，且满足ZsprΔ(C)=pZspr.

证明在Zs×Zpr上设Γj(C)={1}×(pr-jH2jo),j=1,2,…,r.则C的码字表示如下：

故

即

由s=k-1，pr-1=得，|C|=

定理2定理1构造的码C∈CACe(spr,k=s+1)是最优的.

证明因为

设p是奇素数，元素a∈Z∗p称为模p的二次剩余（quadratic residue）若存在x∈Z∗p使得同余式x2≡a(modp)成立（即a∈H20）.否则，称a模p的二次非剩余（quadratic nonresidue)a∈H21.定义Zp上的勒让德符号为

关于勒让德符号当a=-1,2,3,5,7时有如下结果，为叙述方便记作引理4.

引理4[12]设p是奇素数，则

引理5[13]同余方程x2≡a(modpj),j=1,2,3,…,r，有解的充要条件是

下面，用定理1-2和引理4-5来具体构造等差码，由定理2知，结果是最优的.

推论1设p=2m+1 是素数使得p≡71,119(mod 120)，r是正整数，那么存在最优冲突回避码C∈CACe(7pr,8)包含个码字.

证明根据定理1-2和引理4-5并结合勒让德符号的性质，在Gj,j=1,2,…,r中只需证对于每对{a，b}∈{{-7，7}，{-6，1}，{-5，2}，{-4，3}，{-3，4}，{-2，5}，{-1，6}}

即只需证

而当p≡71,119(mod 120)以上条件满足.从而命题得证.

推论2设p=2m+1 是素数使得p≡71,191,239,359,431,599(mod 840)，r是正整数，那么存在最优冲突回避码C∈CACe(8pr,9)包含个码字.

证明根据定理1-2和引理4-5并结合勒让德符号的性质，在Gj,j=1,2,…,r中只需证对于每对{a,b}∈{{-8,8},{-7,1},{-6,2},{-5,3},{-4,4},{-3,5},{-2,6},{-1,7}}

即只需证

而当p≡71,191,239,359,431,599(mod 840)以上条件满足.从而命题得证.

推论3设p=2m+1 是素数使得p≡39,71,79,151,191,239(mod 280)，r是正整数，那么存在最优冲突回避码C∈CACe(9pr,10)包含个码字.

证明根据定理1-2和引理4-5并结合勒让德符号的性质，在Gj,j=1,2,…,r中只需证对于每对{a,b}∈{{-9,9},{-8,1},{-7,2},{-6,3},{-5,4},{-4,5},{-3,6},{-2,7},{-1,8}}

即只需证

而当p≡39,71,79,151,191,239(mod 280)以上条件满足.从而命题得证.

推论4设p=2m+1 是素数使得p≡23,55,71,95(mod 168)，r是正整数，那么存在最优冲突回避码C∈CACe(10pr,11)包含个码字.

证明根据定理1-2和引理4-5并结合勒让德符号的性质，在Gj,j=1,2,…,r中只需证对于每对{a,b}∈{{-10,10},{-9,1},{-8,2},{-7,3},{-6,4},{-5,5},{-4,6},{-3,7},{-2,8},{-1,9}}即只需证

而当p≡23,55,71,95(mod 168)以上条件满足.从而命题得证.

推论5设p=2m+1 是素数使得p≡71,191,239,359,431,599(mod 840)，r是正整数，那么存在最优冲突回避码C∈CACe(11pr,12)包含个码字.

证明根据定理1-2和引理4-5并结合勒让德符号的性质，在Gj,j=1,2,…,r中只需证对于每对{a,b}∈{{-11,11},{-10,1},{-9,2},{-8,3},{-7,4},{-6,5},{-5,6},{-4,7},{-3,8},{-2,9},{-1,10}}即只需证

而当p≡71,191,239,359,431,599(mod 840)以上条件满足.从而命题得证.

3 结论

利用欧拉函数和同余数的特性，对进行划分，得到最优冲突回避码的一般构造，并给出具体构造码重k=8,9,10,11,12时最优冲突回避码的一系列新结果，同时改进了文献[1]的成果.