4上偶長度的LCD負(fù)循環(huán)碼

廖文敬， 開曉山

(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院，合肥230601)

1 引 言

上世紀(jì)九十年代，Hammons等[1]發(fā)現(xiàn)某些高效二元非線性碼是環(huán)4上線性碼的二元象，有限環(huán)上編碼理論獲得重要突破，這使得有限環(huán)上糾錯碼理論成為編碼理論研究的一個主要方向之一.Wolfmann在文獻(xiàn)[2]中研究了4上奇長度的負(fù)循環(huán)碼及其二元象的性質(zhì).此后，有限環(huán)上常循環(huán)碼受到學(xué)者們廣泛地關(guān)注.Blackford在文獻(xiàn)[3]中確定了偶長度的負(fù)循環(huán)碼的結(jié)構(gòu).文獻(xiàn)[4]得到了伽羅瓦環(huán)GR(2a，m)上負(fù)循環(huán)碼及其自對偶碼的生成多項式.文獻(xiàn)[5]分析了一般有限環(huán)上常循環(huán)碼的研究方法.文獻(xiàn)[6]對pm上長度為n的常循環(huán)碼的周期分布進(jìn)行了深入研究，其中g(shù)cd(n，p)=1.文獻(xiàn)[7-8]利用有限環(huán)上常循環(huán)碼構(gòu)造了參數(shù)較好的量子糾錯碼.

Massey在文獻(xiàn)[9]中引入了有限域上LCD碼，證明了LCD碼是漸近好碼.文獻(xiàn)[10]證明了二元LCD碼可以用于抗側(cè)信道攻擊，這引起了學(xué)者們對構(gòu)造LCD碼的極大興趣.文獻(xiàn)[11]研究了有限鏈環(huán)上LCD碼的存在性.文獻(xiàn)[12]給出了有限鏈環(huán)上LCD循環(huán)碼的性質(zhì).最近，文獻(xiàn)[13]證明了有限Frobenius環(huán)上不存在非自由LCD碼，并且構(gòu)造了4上最優(yōu)LCD循環(huán)碼.

2 預(yù)備知識

設(shè)f(x)是4上次數(shù)為m的首一多項式且f(0)=1或3，定義f(x)的互反多項式為

f*(x)=f(0)-1xmf(1/x).

如果f(x)=f*(x)，則稱f(x)為4上自互反多項式.設(shè)f(x)是4上次數(shù)為m的首一基本不可約多項式且deg(f(x))=m，則GR(4，m)=4[x]/〈f(x)〉為4的m次擴(kuò)環(huán)，由伽羅華環(huán)相關(guān)理論，在GR(4，m)上存在一個(2m-1)次本原單位根ζ使得f(ζ)=0.令Γ={0，1，ζ，…，ζ2m-2}，則任意r∈GR(4，m)可以表示成r=a+2b，其中a，b∈Γ.下面引理給出了集合Γ中元素和的性質(zhì).

對于奇數(shù)n，設(shè)β是4擴(kuò)環(huán)中的n次本原單位根，f(x)是4上首一基本不可約多項式，若f(βi)=0，則稱f(x)為βi在4上的極小多項式，記為mi(x).

定義x與y的內(nèi)積為x·y=x0y0+x1y1+…+xN-1yN-1∈4.若x·y=0，則稱x與y正交.設(shè)C是4上長為N的線性碼，定義C的對偶碼為若C∩C⊥={0}，則稱C為4上線性互補(bǔ)對偶(LCD)碼.若對任意碼字(c0，c1，…，cN-1)∈C，都有(-cN-1，c1，…，cN-2)∈C，則稱C為4上長為N的負(fù)循環(huán)碼.視碼字c=(c0，c1，…，cN-1)與多項式c(x)=c0+c1x+…+cN-1xN-1相同，則4上長為N的負(fù)循環(huán)碼是商環(huán)4[x]/〈xN+1〉的理想.4上長為N的負(fù)循環(huán)碼C與下面兩個二元線性碼存在密切聯(lián)系：

設(shè)N=2kn，其中k是正整數(shù)，n是正奇數(shù).記R=4[x]/〈xN+1〉，則4上長為N的負(fù)循環(huán)碼是環(huán)R的理想.根據(jù)Hensel引理[13]，xn-1在4[x]中可以唯一分解成首一基本不可約多項式的乘積

其中fi(x)(1≤i≤s)是4[x]中首一基本不可約自互反多項式，hj(x)與是4[x]中首一不可約互反多項式對.文獻(xiàn)[3，15]中給出4上負(fù)循環(huán)碼的結(jié)構(gòu).設(shè)C是4上長為N的負(fù)循環(huán)碼，則C的生成多項式可以表示為

(1)

其中0≤li，kj，λj≤2k+1，1≤i≤s，1≤j≤t.而且，C⊥的生成多項式為

根據(jù)定義，C是4上長為N的LCD碼當(dāng)且僅當(dāng)C∩C⊥={0}.在R中

因此，C是LCD碼當(dāng)且僅當(dāng)

max{li，2k+1-li}=max{kj，2k+1-λj}=max{λj，2k+1-kj}=2k+1，

其中1≤i≤s，1≤j≤t.從而，C是4上長為N的LCD碼當(dāng)且僅當(dāng)li=0或2k+1(1≤i≤s)，λj=kj=0或2k+1(1≤j≤t).由此得到下面定理.

定理1設(shè)g(x)是定義如式(1)，則4上長為N生成多項式為g(x)的負(fù)循環(huán)碼是LCD碼當(dāng)且僅當(dāng)li=0或2k+1(1≤i≤s)，λj=kj=0或2k+1(1≤j≤t).

由定理1可以得到如下推論.

推論1設(shè)C是4上長為N生成多項式為g(x)的LCD負(fù)循環(huán)碼，則存在xn-1的自互反因子f(x)∈4[x]使得g(x)=f(x)2k+1.

引理2設(shè)f(x)是xn-1在4[x]中的首一因子，則對任意正整數(shù)l，在R中有

〈g(x)2k+1〉=〈g(x)2k+1+l〉.

u(x)g(x)2k+1+l=[1-v(x)h(x)2k+1]g(x)2k+1=g(x)2k+1-v(x)(xn-1)2k+1=g(x)2k+1.

因此

〈g(x)2k+1〉=〈g(x)2k+1+l〉.

定理24上長為N的LCD負(fù)循環(huán)碼是自由可逆碼.

證設(shè)C是4上長為N的LCD負(fù)循環(huán)碼，則存在xn-1的自互反因子f(x)∈4[x]使得C=〈f(x)2k+1〉.容易驗證，C是可逆碼.設(shè)h(x)=(xn-1)/g(x)，注意在R中，〈g(x)2kh(x)2k〉=〈2〉，故

C∩〈2〉=〈g(x)2k+1h(x)2k〉=〈2g(x)2k〉.

由引理2得

2C=〈g(x)2k+1+2kh(x)2k〉=〈g(x)2k+1h(x)2k〉=〈2g(x)2k〉，

故C∩〈2〉=2C.根據(jù)文獻(xiàn)[16]中推論3.12知，C是自由碼.

引理3當(dāng)m≥4是偶數(shù)時，Res(C)和Tor(C)的極小漢明距離是3；當(dāng)m≥4是奇數(shù)時，Res(C)和Tor(C)的極小漢明距離至少是5.

證由文獻(xiàn)[16]中定理4.2，Res(C)的極小漢明距離等于

當(dāng)m是奇數(shù)時，3不是2m-1的因子，考慮兩種情況：

(i) 假設(shè)D中含有重量為3的碼字c(x)，由于D是二元循環(huán)碼，不失一般性，可設(shè)

c(x)=1+xl1+xl2，

其中1≤l1

c(x)+c*(x)=xl2-l1+xl1∈D.

若l2≠2l1，則c(x)+c*(x)的漢明重量為2.若l2=2l1，則c(x)=1+xl1+x2l1. 因此

(ii) 假設(shè)D含有重量為4的碼字

e(x)=1+xl1+xl2+xl3，

其中1≤l1

e(x)+e*(x)=xl1+xl2+xl3-l2+xl3-l1∈D.

因此

綜上所述，當(dāng)m是奇數(shù)時，Res(C)的極小漢明距離至少是5.

定理3當(dāng)m是偶數(shù)時，C的極小Lee距離為3；當(dāng)m是奇數(shù)時，C的極小Lee距離至少為6.

證用dL(C)，dH(C)分別表示碼C的極小Lee距離和極小漢明距離.由Lee距離的定義，dL(C)≥dH(C).注意到C與Tor(C)的極小漢明距離相同.由引理3，當(dāng)m是偶數(shù)時，dL(C)≥3；當(dāng)m是奇數(shù)時，dL(C)≥5.下面分兩種情況討論dL(C).

(i) 當(dāng)m是偶數(shù)時，令l=n/3，則

ζ3l-1=(ζl-1)(ζ2l+ζl+1)=0，

因為ζl-1≠0，所以，ζ2l+ζl+1=0.從而，g(x)整除x2l+xl+1.由此推出

c(x)=(x2l+xl+1)4

是C的碼字.在R中，xN=x6l=-1，于是

c(x)=(x2l+xl+1)4=(x4l+2x3l+3x2l+2xl+1)2

=x8l+2x6l+3x4l+2x2l+1=3x4l+x2l+3.

因c(x)的Lee重量為3，故dL(C)≤3.因此，當(dāng)m是偶數(shù)時，dL(C)=3.

(ii) 當(dāng)m是奇數(shù)時，假設(shè)C含有Lee重量為5的碼字c(x)，則c(x)一定具有形式

±(xl1+xl2+xl3-xl4-xl5)

或±(xl1+xl2+xl3+xl4-xl5)，其中0≤l1，l2，l3，l4，l5≤n-1且它們彼此不相等.分兩種情況討論：

① 若c(x)=±(xl1+xl2+xl3-xl4-xl5)，則

ζl1+ζl2+ζl3=ζl4+ζl5，

(2)

ζ-l1+ζ-l2+ζ-l3=ζ-l4+ζ-l5.

(3)

令ζl1+ζl2+ζl3=ζl4+ζl5=a+2b，其中a，b∈Γ.由引理1可以得到

(ζl1ζl2)1/2+(ζl2ζl3)1/2+(ζl1ζl3)1/2=(ζl4ζl5)1/2.

(4)

將(4)式兩邊平方再模2約化，得到

(5)

類似地，由(3)式可以得到

(6)

(6)式可變形為

(7)

將(2)式模2約化后代入(7)式，得到

(8)

將(3)式模2約化，并變形為

結(jié)合(5)式得到

(9)

② 若c(x)=±(xl1+xl2+xl3+xl4-xl5)，則有

ζl1+ζl2+ζl3+ζl4=ζl5，ζ-l1+ζ-l2+ζ-l3+ζ-l4=ζ-l5.

由此推出

ζa+ζb+ζc+ζd=1，

(10)

ζ-a+ζ-b+ζ-c+ζ-d=1，

(11)

其中a=l1-l5，b=l2-l5，c=l3-l5，d=l4-l5.對(10)式運(yùn)用引理1，再兩邊平方并模2約化，得到

(12)

(13)

f(x)=x4+x3+λx+λ=(x+1)(x3+λ)=0.

根據(jù)文獻(xiàn)[14]中引理9.5，x3+λ=0在F2m最多只有一個根.因此，方程f(x)=0在F2m中最多只有兩個根，矛盾.

綜合①和②，當(dāng)m是奇數(shù)時，C中沒有Lee重量為5的碼字.所以，dL(C)≥6.

例設(shè)m=5，n=31，N=62.在4[x]中，

g(x)=m1(x)m-1(x)=(x5+2x4+x3+3)(x5+3x2+2x+3)

=x10+2x9+x8+3x7+x5+3x3+x2+2x+1.

設(shè)C=〈g(x)4〉是4上長為62的LCD負(fù)循環(huán)碼，其中

g(x)4=x40+2x36+2x34+x32+x28+2x22+3x20+2x18+x12+2x6+2x4+1.

根據(jù)定理3可知，C的Lee距離至少為6.利用MAGAMA程序算出C的Lee距離為6.因此，C是4上參數(shù)(62，284，6)的線性碼.

5 結(jié) 論

致謝作者非常感謝相關(guān)文獻(xiàn)對本文的啟發(fā)以及審稿專家提出的寶貴意見.