一類長度為2m的負循環(huán)碼的重量分布

黃 山

(安徽警官職業(yè)學(xué)院，安徽 合肥 230031)

0 引言

有限域上循環(huán)碼是線性碼的一個子類，具有高效的編譯碼算法，因此被廣泛應(yīng)用于消費電子、數(shù)據(jù)傳輸技術(shù)等領(lǐng)域.有限域上負循環(huán)碼是循環(huán)碼的發(fā)展與推廣，它不僅具有豐富的代數(shù)結(jié)構(gòu)，而且具有高效的編譯碼算法，因此被廣泛應(yīng)用于最優(yōu)碼、自對偶碼以及量子碼的構(gòu)造等領(lǐng)域.Berlekamp[1]首次研究了有限域上的負循環(huán)碼.Blackford[2]利用有限域上的負循環(huán)碼構(gòu)造了自對偶碼.Danev等[3]利用有限域上的負循環(huán)碼構(gòu)造了一類最小距離為5的最優(yōu)碼.Kai等[4-5]將有限域上的負循環(huán)碼應(yīng)用于量子碼的構(gòu)造，得到了極大距離可分量子碼.因此，研究有限域上的負循環(huán)碼是十分具有價值的工作.

有限域上負循環(huán)碼的代數(shù)結(jié)構(gòu)已得到深入的研究.Bakshi等[6]確定了有限域上長度為2m的自對偶負循環(huán)碼的代數(shù)結(jié)構(gòu).Dinh[7]確定了有限域上長度為2ps的負循環(huán)碼的代數(shù)結(jié)構(gòu).Bakshi等[8]確定了有限域上長度為2pn的負循環(huán)自對偶碼和負循環(huán)自正交碼的代數(shù)結(jié)構(gòu).Sharma等[9]確定了有限域上長度為2mpn的負循環(huán)自對偶碼和自正交碼的代數(shù)結(jié)構(gòu).最近，Wu等[10]確定了有限域上負循環(huán)碼的代數(shù)結(jié)構(gòu)，并將其應(yīng)用于線性互補對偶碼的構(gòu)造.

確定有限域上負循環(huán)碼的最小距離通常是困難的.2008年，Dinh[11]確定了有限域Fpa上長度為ps的負循環(huán)碼的最小距離.最近，Dinh等[12-14]先后確定了有限域Fpm上長度為3ps、4ps和5ps的負循環(huán)碼的最小距離.目前，關(guān)于負循環(huán)碼參數(shù)的研究工作相對較少，因此，確定負循環(huán)碼的參數(shù)是一個有趣且具有挑戰(zhàn)性的問題.本文通過分圓陪集理論，確定了有限域Fq長度為2m的負循環(huán)碼的參數(shù)，其中q是一個奇素數(shù)冪.

1 預(yù)備知識

定義1設(shè)C是Fq上長度為n的線性碼，如果對任意的(c0,c1,…,cn-1)∈C，恒有(-cn-1,c0,c1,…,cn-2)∈C，則稱C為Fq上長度為n的負循環(huán)碼.

下面介紹負循環(huán)碼的代數(shù)結(jié)構(gòu).設(shè)R=Fq[x]/(xn+1)表示多項式環(huán)Fq[x]關(guān)于理想(xn-1)的商環(huán).定義

(c0,c1,…,cn-1)c0+c1x+…+cn-1xn-1，

且φ(C)={φ(c)|c∈C}.本文中，視C與φ(C)為同一概念.因此，有限域Fq上長度為n的線性碼C是負循環(huán)碼當(dāng)且僅當(dāng)C是商環(huán)R的理想.眾所周知，商環(huán)R的每個理想都是主理想.設(shè)C=g(x)R=(g(x))是Fq上長度為n的負循環(huán)碼，其中g(shù)(x)∈Fq[x]是一個首一多項式且整除xn+1.多項式g(x)稱為負循環(huán)碼C的生成多項式，h(x)=(xn+1)/g(x)稱為負循環(huán)碼C的校驗多項式.在此基礎(chǔ)上，給出不可約負循環(huán)碼的定義.

定義2設(shè)C是Fq上長度為n校驗多項式為h(x)的負循環(huán)碼，當(dāng)h(x)在Fq上不可約時，則稱C為不可約負循環(huán)碼.

定義3設(shè)n與q互素，對任意i∈Z2n，q-模2n含i分圓陪集定義為

Ci={iqj(mod 2n)|0≤j≤li-1}，

其中：li是使得iqli≡i(mod 2n)的最小正整數(shù).

由定義3，容易驗證，β1+2i在Fq上的極小多項式為

M1+2i(x)=∏j∈C1+2i(x-βj)，

其中：C1+2i表示q-模2n含1+2i分圓陪集.設(shè)Δ={1+2i|0≤i≤n-1}，由定義3，存在Z2n的子集Γ使得Δ=∪i∈ΓCi且Ci∩Cj=?對任意i≠j.由此推出，xn+1在Fq上的不可約分解為xn+1=∏i∈ΓMi(x).進而，不可約負循環(huán)碼具有如下的代數(shù)結(jié)構(gòu).

性質(zhì)1設(shè)xn+1=∏i∈ΓMi(x)，其中Γ和Mi(x)定義如上.設(shè)C是Fq上長度為n的負循環(huán)碼，則存在i∈Γ，使得Mi(x)是碼C的校驗多項式.

2 長度為2m的不可約負循環(huán)碼

下面研究Fq上長度為2m(m≥3)的不可約負循環(huán)碼.為此，首先研究q-模2m+1含奇數(shù)的分圓陪集的性質(zhì).設(shè)q=1+2ab或q=-1+2ab，其中a≥2且b為奇數(shù).設(shè)Δ={1+2i|0≤i≤2m-1}，則有如下性質(zhì).

引理1(1)當(dāng)q=1+2ab且m≤a-1時，則

(2)當(dāng)q=-1+2ab且m≤a-1時，則

其中：0≤i≤2m-1-1.

(3)當(dāng)q=±1+2ab且m≥a時，則q-模2m+1含所有奇數(shù)的分圓陪集，

證明(1)當(dāng)q=1+2ab且m≤a-1時，2m+1整除q-1，所以C1+2i={1+2i}.顯然，C1+2i(0≤i≤2m-1)各不相同，因此，

(3)對任意正整數(shù)e，利用數(shù)學(xué)歸納法可以證明，(±1+2ab)2e=1+2a+ebe，其中be為奇數(shù).由此推出，

q2m-a=(±1+2ab)2m-a≡1+2m(mod 2m+1)

且

q2m-a+1=(±1+2ab)2m-a+1≡1(mod 2m+1).

因此，ord2m+1(q)=2m+1-a.于是，對每個1+2i，

C1+2i={(1+2i)ql|0≤l≤2m+1-a-1}.

下面證明C1+2i(0≤i≤2a-1-1)各不相同.假設(shè)存在0≤i,j≤2a-1-1且i≠j使得C1+2i=C1+2j，即存在l使得

1+2i≡(1+2j)ql(mod 2m+1).

(1)

由此推出，

1+2i≡(1+2j)ql≡

(1+2j)εl(mod 2a)，

(2)

其中，

當(dāng)εl=1時，由式(2)推出，i≡j(mod 2a-1)，這與0≤i

2a≡(1+2j)(ql+1)(mod 2m+1).

因為m≥a，所以

2a≡(1+2j)(-1+2a)(mod 2a+1)，

即2j(2a-1)≡1(mod 2a+1)，矛盾.綜上所述，結(jié)論成立.

設(shè)β是2m+1-次本原單位根，則β1+2i的極小多項式為

設(shè)NC(1+2i)是Fq上長度為2m校驗多項式為M1+2i(x)的不可約負循環(huán)碼.

定理1設(shè)q=1+2ab，其中a≥2且b為奇數(shù).

(1)如果m≤a-1，則NC(1+2i)的參數(shù)為[2m,1,2m].

(2)如果m≥a，則NC(1+2i)的參數(shù)為[2m,2m+1-a,2a-1]且重量為j的碼字個數(shù)

Aj=

證明(1)當(dāng)m≤a-1時，由引理1，M1+2i(x)=x-β1+2i.注意到

x2m+1=x2m-(β1+2i)2m=

(2)當(dāng)m≥a時，由引理1，

設(shè)γ=(β1+2i)2m+1-a，則ord(γ)=2a，所以γ∈Fq,即β1+2i是多項式x2m+1-a-γ的零點.因此，M1+2i(x)=x2m+1-a-γ.注意到

x2m+1=(x2m+1-a)2a-1-γ2a-1=

下面確定NC(1+2i)的重量分布.設(shè)c(x)∈NC(1+2i)是非零的碼字，則存在f(x)∈Fq[x]且deg(f(x))≤2m+1-a-1，使得

c(x)=

由此推出，wt(c(x))=2a-1·wt(f(x)).因此，NC(1+2i)的每個非零碼字的重量均被2a-1整除.特別地，wt(c(x))=2a-1l當(dāng)且僅當(dāng)wt(f(x))=l.因此，

定理2設(shè)q=-1+2ab，其中a≥2且b為奇數(shù).

(1)如果m≤a-1，則NC(1+2i)是參數(shù)為[2m,2,2m-1]的MDS碼，且重量為j的碼字個數(shù)為

(2)如果m≥a，則NC(1+2i)的參數(shù)為[2m,2m+1-a,2a-1].

證明(1)當(dāng)m≤a-1時，由引理1，

M1+2i(x)=(x-β1+2i)(x-β1+2(2m-1-i))=

x2-(β1+2i+β1+2(2m-1-i))x+1.

因為ord(β1+2i)=2m+1>8，所以β1+2i+β1+2(2m-1-i)≠0.容易驗證，NC(1+2i)的對偶碼NC(1+2i)⊥是Fq上由M1+2i(x)生成的參數(shù)為[2m,2m-2]的負循環(huán)碼.

A0=1，A2m-1=2m(q-1)

且

A2m=q2-1-2m(q-1).

(2)當(dāng)m≥a時，由引理1，

設(shè)λ=(β1+2i)2m-a，則ord(λ)=2a+1.注意到q2-1=2a+1(2a-1b-1)b，所以λ∈Fq2且λ+λq∈Fq.由此推出，

(x2m-a-λ)(x2m-a-λq)=

x2m+1-a-(λ+λq)x2m+1-a+λq+1∈Fq[x].

因為β1+2i是(x2m-a-λ)(x2m-a-λq)的零點，所以M1+2i(x)整除(x2m-a-λ)(x2m-a-λq).比較多項式的次數(shù)可得，M1+2i(x)=x2m+1-a-(λ+λq)x2m-a+λq+1.又因為ord(λ)=2a+1，所以λq+1=(λ2a)b=-1且λ+λq≠0，即M1+2i(x)=x2m+1-a-(λ+λq)x2m-a-1.

設(shè)z=x2m-a且

x2m+1=z2a+1=

[z2-(λ+λq)z-1]·

[θ2a-2z2a-2+θ2a-3z2a-3+…+θ1z+θ0].

比較等式兩邊的系數(shù)可得，

解得

i)當(dāng)deg(f(x))≤2m-a-1時，

因此，wt(c(x))=(2a-1)·wt(f(x))≥2a-1.

ii)當(dāng)deg(f(x))≥2m-a時，設(shè)f(x)=f1(x)+x2m-af2(x)，其中deg(f1(x))≤2m-a-1，deg(f2(x))≤2m-a-1，于是，

θ2a-2f2(x)x2m-2m-a.

由此推出，

wt(c(x))=wt(f1(x))+wt(f2(x))+

特別地，當(dāng)f1(x)=0時，

wt(c(x))=(2a-1)·wt(f2(x))≥2a-1.

當(dāng)f1(x)≠0且f2(x)≠0時，注意到λq=λ-1+2ab=-λ-1，所以

由此推出，

(-1)jλ2j+1(λ2+1)[λ2(i-j)-(-1)i-j]=0

?λ2(i-j)-(-1)i-j=0.

當(dāng)i-j為奇數(shù)時，λ2(i-j)=-1，這與ord(λi-j)=2a+1≥8矛盾.當(dāng)i-j為偶數(shù)時，λ2(i-j)=1，即2a|(i-j).又因為1≤i,j≤2a-2，所以i=j.即

由此推出wt(c(x))≥1+1+2a-3=2a-1.綜上所述，NC(1+2i)的最小距離為2a-1.

例1設(shè)n=24，在F9上，xn+1=(x4+ω)(x4+ω3)(x4+ω5)(x4+ω7)，其中ω是F9的本原元.

由定理1，F(xiàn)9上有4個不同的不可約負循環(huán)碼且它們的參數(shù)均為[16,4,4].它們的重量分布為1+32z4+384z8+2048z12+4096z16.

例2設(shè)n=24，在F3上，xn+1=(x8+x4+2)(x8+2x4+2).

由定理2，F(xiàn)3上有2個不同的不可約負循環(huán)碼且它們的參數(shù)均為[16,8,3].經(jīng)Magma驗算，它們的重量分布為1+32z3+384z6+2048z9+4096z12.

3 結(jié)語

本文通過計算q-模2m+1分圓陪集，確定了Fq上長度為2m的不可約負循環(huán)碼的生成多項式.利用生成多項式的結(jié)構(gòu)，確定了Fq長度為2m的不可約負循環(huán)碼的最小距離，并給出了一類不可約負循環(huán)碼的重量分布.