黃必昌

（百色學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院,廣西 百色 533000）

為了便于閱讀，采用的符號與文獻[1]一致.

設(shè)Zn表示模n的剩余類環(huán)，Z?n表示Zn{0}.對于k階子集A?Zn，定義A的差集為多重集合

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

設(shè)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的碼字個數(shù)，設(shè)

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

若｜C｜=M(n,k)，則稱碼C ∈CAC(n,k)為最優(yōu)碼.

沖突回避碼作為協(xié)議序列被應(yīng)用于無反饋多分址信道（沖突信道）[2-3].對于沖突回避碼C∈CAC(n,k)，最優(yōu)沖突回避碼能保證最多的用戶有效可靠地傳輸信息.碼字的重量k（漢明碼重量）表示用戶在每個時段的n個時槽里發(fā)送k個數(shù)據(jù)包[4].

設(shè)是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 所有碼字生成元的集合.等差碼是一類差集不同元素的個數(shù)比較少的碼字，相應(yīng)的會得到較多的碼字，所以在構(gòu)造最優(yōu)碼時經(jīng)?？紤]它.

目前，當(dāng)k=3 時的最優(yōu)沖突回避碼構(gòu)造證明已經(jīng)基本解決[5-10].當(dāng)k=3,4,5,6 的最優(yōu)沖突回避碼具體構(gòu)造有些結(jié)果[4,11].對碼重k>7 的最優(yōu)沖突回避碼具體構(gòu)造取得的結(jié)果很少[1].本文利用歐拉函數(shù)和同余數(shù)在整數(shù)環(huán)的特性給出一種構(gòu)造等差碼新的構(gòu)造方法，得到k=8,9,10,11,12時最優(yōu)沖突回避碼構(gòu)造的具體構(gòu)造，碼長由n=(k-1)p推廣為碼長n=(k-1)pr，其中r為為任意的正整數(shù).改進文獻[1]的結(jié)果.

1 已有的相關(guān)構(gòu)造

設(shè)奇素數(shù)p=2em+1，θ∈Z?p是Z?p的生成元，設(shè)H2e0={θ2es:s=0,1,…,m-1}是Z?p的m階乘法子群，則有陪集，且稱Hi2e為2e階分圓類.若jt∈Hi2e,0≤i≤2e-1.則稱{j0,j1,…,j2e-1}一個為2e階分圓類代表系.那么，以下是一些已有的構(gòu)造.

引理1[4]設(shè)e≥1 和s>1 都是整數(shù)，p=2em+1 是素數(shù)且使得每一個(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構(gòu)造的碼C∈CACe(sp,k=es+1)是最優(yōu)的.

引理3[4]設(shè)k≥3,L1,L2和s都是正整數(shù)，且s|L1，gcd(l,L2)=1,l=2,3,…,(k-1).設(shè)C1∈CACe(L1,k)包含m1個碼字A1,A2,…,Am1使得

設(shè)C2∈CACe(sL2,k)包含m2個碼字.設(shè)碼C是由

生成.則C∈CACe(L1L2,k)且包含m1L1+m2個碼字.

當(dāng)前，利用引理1和引理2來具體構(gòu)造一些最優(yōu)沖突回避碼.再利用引理3復(fù)合構(gòu)造出一系列的沖突回避碼C∈CACe((k-1)pi,k)[1,4].但是，實際情況下，引理3很難得到最優(yōu)C∈CACe((k-1)pi,k).本文首次利用歐拉函數(shù)和同余數(shù)的特性，對Z?pr進行劃分，得到類似于引理2的一般構(gòu)造，并給出具體構(gòu)造碼重k=8,9,10,11,12時最優(yōu)沖突回避碼的一系列新結(jié)果.

2 新的構(gòu)造方法及其證明

設(shè)n為一個正整數(shù)，稱G={a|(a,n)=1,a∈Z*n}是Z?n簡約剩余系，顯然，G={a|(a,n)=1,a∈Z*n}是一個乘法群.且|G|=Φ(n)，其中Φ(n)是歐拉函數(shù).設(shè)p=2m+1 是奇素數(shù)，r為正整數(shù)，Gj={a|(a,n)=1,a∈},1≤j≤r.乘法子群，則|Gj|=Φ(pj).設(shè)θ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階分圓類代表系.下面得到如下構(gòu)造.

定理1設(shè)s,r是正整數(shù)，p是奇素數(shù)且使得每一個(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上設(shè)Γj(C)={1}×(pr-jH2jo),j=1,2,…,r.則C的碼字表示如下：

故

即

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

定理2定理1構(gòu)造的碼C∈CACe(spr,k=s+1)是最優(yōu)的.

證明因為

設(shè)p是奇素數(shù)，元素a∈Z?p稱為模p的二次剩余（quadratic residue）若存在x∈Z?p使得同余式x2≡a(modp)成立（即a∈H20）.否則，稱a模p的二次非剩余（quadratic nonresidue)a∈H21.定義Zp上的勒讓德符號為

關(guān)于勒讓德符號當(dāng)a=-1,2,3,5,7時有如下結(jié)果，為敘述方便記作引理4.

引理4[12]設(shè)p是奇素數(shù)，則

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

下面，用定理1-2和引理4-5來具體構(gòu)造等差碼，由定理2知，結(jié)果是最優(yōu)的.

推論1設(shè)p=2m+1 是素數(shù)使得p≡71,119(mod 120)，r是正整數(shù)，那么存在最優(yōu)沖突回避碼C∈CACe(7pr,8)包含個碼字.

證明根據(jù)定理1-2和引理4-5并結(jié)合勒讓德符號的性質(zhì)，在Gj,j=1,2,…,r中只需證對于每對{a，b}∈{{-7，7}，{-6，1}，{-5，2}，{-4，3}，{-3，4}，{-2，5}，{-1，6}}

即只需證

而當(dāng)p≡71,119(mod 120)以上條件滿足.從而命題得證.

推論2設(shè)p=2m+1 是素數(shù)使得p≡71,191,239,359,431,599(mod 840)，r是正整數(shù)，那么存在最優(yōu)沖突回避碼C∈CACe(8pr,9)包含個碼字.

證明根據(jù)定理1-2和引理4-5并結(jié)合勒讓德符號的性質(zhì)，在Gj,j=1,2,…,r中只需證對于每對{a,b}∈{{-8,8},{-7,1},{-6,2},{-5,3},{-4,4},{-3,5},{-2,6},{-1,7}}

即只需證

而當(dāng)p≡71,191,239,359,431,599(mod 840)以上條件滿足.從而命題得證.

推論3設(shè)p=2m+1 是素數(shù)使得p≡39,71,79,151,191,239(mod 280)，r是正整數(shù)，那么存在最優(yōu)沖突回避碼C∈CACe(9pr,10)包含個碼字.

證明根據(jù)定理1-2和引理4-5并結(jié)合勒讓德符號的性質(zhì)，在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}}

即只需證

而當(dāng)p≡39,71,79,151,191,239(mod 280)以上條件滿足.從而命題得證.

推論4設(shè)p=2m+1 是素數(shù)使得p≡23,55,71,95(mod 168)，r是正整數(shù)，那么存在最優(yōu)沖突回避碼C∈CACe(10pr,11)包含個碼字.

證明根據(jù)定理1-2和引理4-5并結(jié)合勒讓德符號的性質(zhì)，在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}}即只需證

而當(dāng)p≡23,55,71,95(mod 168)以上條件滿足.從而命題得證.

推論5設(shè)p=2m+1 是素數(shù)使得p≡71,191,239,359,431,599(mod 840)，r是正整數(shù)，那么存在最優(yōu)沖突回避碼C∈CACe(11pr,12)包含個碼字.

證明根據(jù)定理1-2和引理4-5并結(jié)合勒讓德符號的性質(zhì)，在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}}即只需證

而當(dāng)p≡71,191,239,359,431,599(mod 840)以上條件滿足.從而命題得證.

3 結(jié)論

利用歐拉函數(shù)和同余數(shù)的特性，對進行劃分，得到最優(yōu)沖突回避碼的一般構(gòu)造，并給出具體構(gòu)造碼重k=8,9,10,11,12時最優(yōu)沖突回避碼的一系列新結(jié)果，同時改進了文獻[1]的成果.