四元域上一類厄米特互補(bǔ)對(duì)偶常循環(huán)碼

孫世林,劉 麗

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

0 引 言

常循環(huán)碼是一類重要的線性碼,在糾錯(cuò)碼理論中占有重要的地位[1-2]。常循環(huán)碼可以通過(guò)移位寄存器進(jìn)行有效編碼,是工程應(yīng)用中優(yōu)先選擇的對(duì)象。

線性碼C若滿足C∩C⊥={0}則稱C為線性互補(bǔ)對(duì)偶碼(linear codes with complementary duals,LCD)。文獻(xiàn)[3]首次引入有限域上LCD碼,證明了LCD碼是漸近好碼;文獻(xiàn)[4]證明了二元LCD碼可以用于密碼邊道攻擊,這引起了學(xué)者們對(duì)構(gòu)造LCD碼的極大興趣;文獻(xiàn)[5]構(gòu)造了有限域上幾類LCD循環(huán)碼并分析了它們的參數(shù);文獻(xiàn)[6]分析了可逆BCH碼的參數(shù);文獻(xiàn)[7]分析了有限域上可逆負(fù)循環(huán)BCH碼的幾類參數(shù)。

但是很少有學(xué)者研究厄米特LCD碼。文獻(xiàn)[8]研究了基于歐幾里得和厄米特LCD碼的準(zhǔn)循環(huán)LCD碼的性質(zhì),證明了這些碼是漸近好碼;文獻(xiàn)[9]利用生成矩陣給出了厄米特LCD碼的一個(gè)充要條件。

最近,文獻(xiàn)[10]利用維數(shù)比較小的線性碼、自正交碼和廣義的RS碼構(gòu)造出幾類新的歐幾里得和厄米特LCD MDS碼;文獻(xiàn)[11]構(gòu)造出幾類厄米特LCD循環(huán)碼并分析了它們的參數(shù)。

本文目的是構(gòu)造四元厄米特LCD常循環(huán)碼,并分析它們的參數(shù),確定這些碼的維數(shù),給出它們最小距離的下界。本文提出的厄米特線性互補(bǔ)對(duì)偶碼不是常循環(huán)BCH碼。

1 預(yù)備知識(shí)

C⊥H={(b0,b1,…,bn-1)∈GF(4)n：

定義1[9-11]設(shè)C為GF(4)上一個(gè)長(zhǎng)為n的線性碼，且C⊥H為C的厄米特對(duì)偶碼，若C?C⊥H=GF(4)n或C∩C⊥H={0}，則稱碼C為厄米特LCD碼。

引理1[2,12]假定gcd(3,n)=1,設(shè)C=〈g(x)〉為GF(4)上長(zhǎng)為n的ω-常循環(huán)碼。若g(x)的根為{β1+3i|0≤i≤δ-2},則C的最小距離d≥δ。

設(shè)mi(x)表示GF(4)上βi的極小多項(xiàng)式。用imod 3n表示在集合{0,1,2,…,3n-1}中與imod 3n同余的唯一整數(shù)。記

mi(x)=mi mod 3n(x),

對(duì)于整數(shù)δ≥2,定義:

g(n,δ,1)(x)=lcm(m1(x),m4(x),…,

m1+3(δ-2)(x))

(1)

其中,lcm表示多項(xiàng)式的最小公倍數(shù)。設(shè)C(n,δ,1)表示生成多項(xiàng)式為g(n,δ,1)(x)且長(zhǎng)為n的ω-常循環(huán)碼,由引理1,碼C(n,δ,1)的最小距離至少為δ。

設(shè)Z3n={0,1,2,…,3n-1}。?s∈Z3n,4模3n含s的分圓陪集定義為:

Cs={s,4s,42s,…,4ds-1s}mod 3n?Z3n,

其中,ds為滿足s4ds≡smod 3n的最小正整數(shù),且Cs中有ds個(gè)元素。

設(shè)T={1+3i|0≤i≤n-1}?3n,Cs中最小整數(shù)稱為Cs的陪集首。對(duì)于?s∈Z3n,顯然有T∩Cs=Cs或{0}。

設(shè)Γ(n,4)為T∩Cs=Cs所有陪集首的集合。?s,t∈Γ(n,4),s≠t,有Cs∩Ct={0}且

(2)

βs在GF(4)上的極小多項(xiàng)式ms(x)可表示為:

2 四元厄米特LCD常循環(huán)碼的結(jié)構(gòu)

(3)

定理1 設(shè)C為GF(4)上長(zhǎng)為n的ω-常循環(huán)碼,且生成多項(xiàng)式為:

g(x)=e1(x)a1e2(x)a2…eu(x)auf1(x)b1×

其中,ai,bj,cj∈{0,1},則C為四元厄米特LCD碼當(dāng)且僅當(dāng)bj=cj,j=1,2,…,v。因此,長(zhǎng)為n的四元厄米特LCD常循環(huán)碼總數(shù)為2u+v。

證明由引理1和引理2可得。

定理1指出長(zhǎng)為n的四元厄米特LCD常循環(huán)碼的個(gè)數(shù)由(3)式?jīng)Q定,指明四元厄米特LCD常循環(huán)碼定義集的結(jié)構(gòu)特點(diǎn),它應(yīng)具有以下類型:

S={s∈T:g(βS)=0},

類似于文獻(xiàn)[11]中定理4,可以得到下面定理。

定理2 設(shè)C是GF(4)上長(zhǎng)為n的ω-常循環(huán)碼,其生成多項(xiàng)式為g(x),則C為厄米特LCD碼,當(dāng)且僅當(dāng)下面條件之一成立。

(1) 對(duì)于C的定義集S,S=-2S,其中,-2S={-2s:s∈S}。

(2) 對(duì)于每個(gè)g(x)的根β,β-2也是g(x)的一個(gè)根。

定理3 長(zhǎng)為n的四元ω-常循環(huán)碼都是厄米特LCD碼充要條件為-1是2 mod 3n的奇冪。

證明一方面,設(shè)-1≡22t+1(mod 3n),t≥0。因?yàn)閷?duì)于每個(gè)a∈T有-a≡a·22t+1(mod 3n)且-2a≡a·22t+2≡a·4t+1(mod 3n),所以-2a∈Ca,即fj(x)不在(3)式中出現(xiàn)。由定理1可知,在GF(4)上每個(gè)長(zhǎng)為n的ω-常循環(huán)碼是厄米特LCD碼。

另一方面,設(shè)β為3n次本原單位根,m1(x)表示GF(4)上β的極小多項(xiàng)式。設(shè)C為GF(4)上長(zhǎng)為n且生成多項(xiàng)式為m1(x)的ω-常循環(huán)碼,若C是厄米特LCD碼,則-2∈C1且-2≡4t(mod 3n),其中,1≤t≤m-1,3n是奇數(shù)，因此,-1≡22t-1(mod 3n)。

3 長(zhǎng)為(4m-1)/3的四元厄米特LCD碼

由定理3,設(shè)n=(22t+1+1)/3,易證m=2t+1。由引理3,1是4模22t+1+1的分圓陪集的陪集首。

下面通過(guò)常循環(huán)BCH碼構(gòu)造長(zhǎng)為n=(4m-1)/3的四元厄米特LCD碼且分析其參數(shù)。設(shè)

g(x)=lcm(g(n,δ,1),m3n-2[1+3(δ-2)](x),

m3n-2[1+3(δ-3)](x),…,m3n-8(x),m3n-2(x))

(4)

其中

g(n,δ,1)=lcm(m1(x),m4(x),…,

m1+3(δ-3)(x),m1+3(δ-2)(x))。

下面的引理是關(guān)于4模3n的分圓陪集的性質(zhì)。

引理5[11]設(shè)n=(4m-1)/3,i表示4模3n的分圓陪集Ci的陪集首,則有:

(1) |Cn-2i|=|Ci|。

(2)Cn-2i=Cn-2j當(dāng)且僅當(dāng)Ci=Cj。

(3)Cn-8i=Cn-2i。

設(shè)C為GF(4)上長(zhǎng)為n且生成多項(xiàng)式為g(x)的ω-常循環(huán)碼,C的定義集可以表示成:

記

顯然

-2(1+3a)≡3n-2(1+3a)mod 3n,

-2[3n-2(1+3a)]≡4(1+3a)mod 3n。

因此,S=-2S。由定理2,C是GF(4)上厄米特LCD碼。

(2) 當(dāng)m為奇數(shù)時(shí),有

|J+(δ)∩J-(δ)|=

(3) 當(dāng)m為偶數(shù)時(shí),有

|J+(δ)∩J-(δ)|=0。

同理,有

a∈J+(δ)∩J—(δ),

則存在i、j,0≤i,j≤δ-2,使得:

a∈C1+3i=C3n-2(1+3j),

故有:

1+3i≡-2(1+3j)4lmod(4m-1),

即

1+3i+(1+3j)22l+1≡0 mod(4m-1)

(5)

設(shè)1+3i,1+3j的2-adic展開分別為:

1+3i=im2m+im-12m-1+…+i12+i0,

1+3j=jm2m+jm-12m-1+…+j12+j0,

0≤ik,jk≤1,0≤k≤m,(i0,i1)≠(0,0),

(j0,j1)≠(0,0)。

情況1當(dāng)1≤l≤(m-3)/2時(shí),0<1+3i+(1+3j)22l+1<4m-1,則

1+3i+(1+3j)22l+1≡0 mod(4m-1)

不成立。

情況2 當(dāng)l=(m-1)/2時(shí),可證明1+3i+(1+3j)22l+1≡Δmod(4m-1),其中

Δ=jm-122m-1+…+j12m+1+(j0+im)2m+

im-12m-1+…+i12+(i0+jm)。

注意0<Δ<6n,由(5)式得Δ=3n。因此,jm-1=…=j1=j0+im=im-1=…=i1=i0+jm=1,則im=u,jm=v,i0=1-v,j0=1-u,其中,u,v=0,1。因此,1+3i=(u+1)2m-v-1,1+3j=(v+1)2m-u-1。

情況3 當(dāng)(m+1)/2≤l≤m-1時(shí),有

m+2≤2l+1≤2m-1。

令2l+1=m+ε,2≤ε≤m-1,則1+3i+(1+3j)22l+1≡Δmod(4m-1),其中

Δ=jm-ε-122m-1+…+j12m+ε+1+j02m+ε+

im2m+…+iε+12ε+1+(iε+jm)2ε+…+

(i1+jm-ε+1)2+(i0+jm-ε)。

Δ的2-adic展開中2m+1的系數(shù)為0。因此,0<Δ<3n。這種情況下(5)式是不成立的。

情況2中,i=iuv且j=juv。集合L為：

1+3iuv=(u+1)2m-v-1,

注意情況1～情況3包含全部使C1+3i=C3n-2(1+3j)的可能數(shù)對(duì)(1+3i,1+3j),0≤i,j≤δ-2,其中,2≤δ≤(2m+1-1)/3+2。于是有:

(6)

由引理4,1+3iuv為陪集首,由引理5,C3n-2(1+3a)≠C3n-2(1+3b)當(dāng)且僅當(dāng)C1+3a≠C1+3b。因此(6)式中并沒(méi)有交集,則有:

|J+(δ)∩J—(δ)|=|L|m。

因?yàn)閡,v=0,1,所以1+3iuv、1+3juv都分別可能等于2m-1、2m-2、2m+1-1、2m+1-2這4種情況。因?yàn)?m-2、2m+1-1、2m+1-2不具有1+3i的形式,所以舍去。于是,1+3iuv=2m-1,1+3juv=2m-1。

當(dāng)1+3iuv<2m-1時(shí),即1+3(δ-2)<2m-1,|L|=0。于是有:

|L|=

當(dāng)m為偶數(shù)時(shí)可用同樣的方法證明。

證明由定義1,C的生成多項(xiàng)式g(x)的次數(shù)等于|J+(δ)|+|J-(δ)|-|J+(δ)∩J-(δ)|,維數(shù)k=(4m-1)/3-deg(g(x)),則由定理4可得。

例1 設(shè)m=3,δ=5,C是GF(4)上長(zhǎng)為21的ω-常循環(huán)碼,其生成多項(xiàng)式為:

g(x)=m1(x)m7(x)m10(x)m61(x)m43(x)=

x15+x14+ωx13+x12+x11+x9+ωx8+ωx7+

ω2x6+ω2x4+ω2x3+ωx2+ω2x+ω2,

則C是GF(4)上參數(shù)為[21,6,12]的厄米特LCD碼。

例2 設(shè)m=3,δ=2,C是GF(4)上長(zhǎng)為21的ω-常循環(huán)碼,其生成多項(xiàng)式為:

g(x)=m1(x)m61(x)=x6+ω2x5+x4+

ω2x2+x+ω2,

則C是GF(4)上參數(shù)為[21,15,5]的厄米特LCD碼。

例3 設(shè)m=4,δ=4,C是GF(4)上長(zhǎng)為85的ω-常循環(huán)碼,其生成多項(xiàng)式為:

g(x)=m1(x)m7(x)m253(x)m241(x)=

x16+x15+ωx14+x12+ωx11+ωx9+

ω2x8+x7+x5+ωx4+x2+ωx+ω,

則C是GF(4)上參數(shù)為[85,69,5]的厄米特LCD碼。

4 結(jié) 論

本文構(gòu)造了四元厄米特互補(bǔ)對(duì)偶常循環(huán)碼,并分析它們的參數(shù)。確定長(zhǎng)度為n=(4m-1)/3的厄米特LCD常循環(huán)碼的維數(shù),給出了它們最小距離的下界。本文僅分析了長(zhǎng)度為n=(4m-1)/3的四元厄米特互補(bǔ)對(duì)偶常循環(huán)碼的參數(shù),其他長(zhǎng)度也有待進(jìn)一步探討。