4上偶長度的LCD負循環碼

廖文敬， 開曉山

(合肥工業大學 數學學院，合肥230601)

1 引 言

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

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

2 預備知識

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

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

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

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

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

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

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

(1)

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

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

因此，C是LCD碼當且僅當

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碼當且僅當li=0或2k+1(1≤i≤s)，λj=kj=0或2k+1(1≤j≤t).由此得到下面定理.

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

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

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

引理2設f(x)是xn-1在4[x]中的首一因子，則對任意正整數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負循環碼是自由可逆碼.

證設C是4上長為N的LCD負循環碼，則存在xn-1的自互反因子f(x)∈4[x]使得C=〈f(x)2k+1〉.容易驗證，C是可逆碼.設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.根據文獻[16]中推論3.12知，C是自由碼.

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

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

當m是奇數時，3不是2m-1的因子，考慮兩種情況：

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

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) 假設D含有重量為4的碼字

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

其中1≤l1

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

因此

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

定理3當m是偶數時，C的極小Lee距離為3；當m是奇數時，C的極小Lee距離至少為6.

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

(i) 當m是偶數時，令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.因此，當m是偶數時，dL(C)=3.

(ii) 當m是奇數時，假設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約化，并變形為

結合(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)式運用引理1，再兩邊平方并模2約化，得到

(12)

(13)

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

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

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

例設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.

設C=〈g(x)4〉是4上長為62的LCD負循環碼，其中

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

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

5 結 論

致謝作者非常感謝相關文獻對本文的啟發以及審稿專家提出的寶貴意見.