有限鏈環上線性碼和循環碼的結構

石立葉, 邱雙月， 劉麗英

(邯鄲學院 數理學院, 河北 邯鄲 056005)

?

石立葉*, 邱雙月， 劉麗英

(邯鄲學院 數理學院, 河北 邯鄲 056005)

設R是有限鏈環,R上長度為n的線性碼C等同于模Rn的子模,循環碼等同于R[x]/(xn-1)的理想.定義C[γi]={x|x∈C,γix=0},那么C[γi]是Rn的子模,且C[γi]/C[γi-1]是自由模.進一步當C是循環碼時,C[γi]/C[γi-1]同構于K[x]/(xn-1)的某個理想.由此出發,給出了有限鏈環上線性碼的結構和循環碼的結構,證明并拓廣了Norton的有關結論.

有限鏈環; 線性碼; 循環碼

1994年,Kumar等人在文獻[1]中指出,一些重要的二進制非線性碼,如Preparata碼,Kedock碼,Goethals-Delsarte碼等可以看做環Z4上的線性碼在Gray映射下對應的像.因此,環上碼的研究成為編碼理論工作者研究的一個熱點.環Z4上的線性碼和循環碼已被廣泛研究并得到了豐富的結果[2-6].Galderbank和Sloane給出了Zpk環上循環碼的結構[5].Blackford 和 Ray-Chaudhuri在文獻[6]將這一結果推廣到Galois環上.Norton和Salagean給出了有限鏈環上線性碼和循環碼的結構[7].Douyherty和劉宏偉應用冪等元研究有限鏈環的理想,從而得到有限鏈環上的循環碼的構造[8].本文進一步研究了有限鏈環上的線性碼和循環碼的性質,并給出了它們的結構.

1 有限鏈環上的線性碼

定義1[1]一個含單位元1的有限交換環稱為有限鏈環,如果1≠0并且它的全部理想能按照包含關系排成一條鏈.

通過定義發現有限鏈環R的所有理想都是主理想,因為若R的理想I不是主理想,則I至少有兩個生成元,不妨設I=〈a1,a2,…,as〉,則〈a1〉?〈a2〉,〈a2〉?〈a1〉,與R是有限鏈環矛盾.這也表示,有限鏈環極大理想是唯一的.

設R是有限鏈環,Γ是其極大理想,則Γ是主理想.設γ為Γ的生成元,即Γ=〈γ〉.那么,可得下鏈

R=〈γ0〉?〈γ1〉?…?〈γi〉?…

因為R有限,上鏈不會無限不終止,即存在自然數i,使得〈γi〉=0.設υ是使得〈γυ〉=0的最小的自然數,那么υ就叫做γ的冪零指數.

由上面敘述可以得到有限鏈環的極大理想的3個重要性質:首先,γ是冪零的,設其冪零指數為υ,則R的所有理想為γiR=〈γi〉,0≤i≤υ,且滿足鏈R=〈γ0〉?〈γ1〉?…?〈γυ〉=0;此外,極大理想Γ中所有元都是零因子,并且包含了環R的全部零因子;最后,集合RγR中任何元素是單位,R/γR是有限域,不妨設為K.因此,有限鏈環R存在如下唯一分解:

引理1[7]任意r∈R{0},存在唯一整數i,0≤i≤υ,使得r=uγi,其中u是單位,且u在modγυ-i下是唯一的.

引理2[7]若1≤i

引理3 任取x∈R,若γmx=0,γm-1x≠0,那么Rx?R/γmR?γυ-mR.

證明做映射φ:R→Rx,φ(r)=rx.下證Kerφ=γmR.顯然γmR?Kerφ;任取y∈Kerφ,即yx=0.設y=γαy1,y1是單位,則yx=γαy1x=0,得γαx=0,故α≥m,即y∈γmR.得證.

符號同上,考慮有限鏈環R上的線性碼C.因為有限鏈環R上一個長度為n的線性碼C是R-模Rn的一個子模,反之也成立,所以,只要研究Rn的子模即可.

設M是Rn的一個R-子模,定義M[γi]={x|x∈M,且γix=0}.易證M[γi]是Rn的子模,且滿足下鏈

M=M[γυ]?M[γυ-1]?…?M[γ0]=0.

M[γi]/M[γi-1]是R/γR-模,即K-模.因為主理想環上無扭的有限生成模一定是自由模,又K是域,且M[γi]/M[γi-1]是無扭模,所以,M[γi]/M[γi-1]是自由模,也可看做數域K上的線性空間.設其秩或其維數為tυ-i,1≤i≤υ,令k0=t0,ki=ti-ti-1,1≤i≤υ-1.

為了書寫方便,記Mi=M[γi]/M[γi-1].那么,Mi具有如下性質:

定理1符號同上，則

(1)Mi中的元都可表示為γυ-iu的形式,其中u是單位或0；

(2)Mi?(γυ-iR)tυ-i；

(3)ti≤ti+1,即ki≥0.

證明(1)任取a∈Mi,若a=0,取u=0.若a≠0,由引理1,a=uγj,0≤j≤υ,其中u是單位.又由Mi的定義知,γia=0,γi-1a≠0,故γi+ju=0,γi+j-1u≠0,所以.j=υ-i.

(2)若Mi=Mi-1,命題顯然成立.

若Mi≠Mi-1,因為Mi是自由模,且秩為tυ-i,不妨設u1,u2,…utυ-i是一組基,即Mi?Ru1?Ru2?…?Rutυ-i.又γiuj=0,γi-1uj≠0,0≤j≤tυ-i.應用引理3,Ruj?R/γiR?γυ-iR,命題得證.

(3)γMi?Mi-1,所以,Mi的一組基的γ倍是Mi-1基的一部分.所以, dimMi≤dimMi-1,即tυ-i≤tυ-i+1,所以,ki≥0,0≤i≤υ.

以此類推,最終得到M[γ]的基為:

推論1dimMi=tυ-i=k0+k1+…+kυ-i.

這就意味著碼C中所有碼字可表示為(v0v1…vυ-i)G,其中每個向量vi的長度為ki,向量中的元都屬于γiR.由此,給出碼的類型的定義.

定義2[9]向量(k0,k1,…,kυ-1)叫做碼C的類型,ki叫做維數.

由前面討論,那么對于有限鏈環Zpα上的非零的類型為(k0,k1,…,kυ-1)的線性碼C來說,C所包含的碼字個數為1k0pk1(p2)k2…(pυ-1)kυ-1.

定義3[9]有限鏈環R上線性碼C的對偶碼定義為C⊥={ω∈Rn|(u,ω)=0,?u∈C},其中(u,ω)表示通常的內積.

關于對偶碼的類型有如下結論:

定理3[9]設C是R上類型為(k0,k1,…,kυ-1)的線性碼,則C⊥的類型為(kυ,kυ-1,…,k1),kυ=n-k0-k1-…-kυ-1.

2 有限鏈環上的循環碼

R上的線性碼C叫做循環碼,是指若c=(c0,c1,…,cn-1)∈C,則C的循環移位(cn-1,c0,c1,…,cn-2)∈C.

假設K的特征不能整除n.考慮R上的多項式環R[x]模xn-1的剩余類環R[x]/(xn-1).在同構映射φ:Rn→R[x]/(xn-1),(c0,c1,…,cn-1)|→c0+c1x+…+cn-1xn-1下,環R上的循環碼C等同于R[x]/(xn-1)的理想.

和線性碼的討論類似,記Ci=C[γi]/C[γi-1].易證C[γi]是Rn的理想,由環同態定理可知Ci是Rn/C[γi-1]的理想.

任取a+C[γi-1]∈Ci,由定理1和引理1,存在唯一的a1,使得a=γυ-ia1,其中a1是單位或0.因此,定義映射ψ:Ci→K[x]/(xn-1),ψ(a+C[γi-1])=a1.因此a1≡a(modγυ-i),且有下述結論.

引理4上述映射是單同態.

證明任取u=a+C[γi-1],v=b+C[γi-1]∈Ci,設ψ(u)=a1,ψ(v)=b1.

由同余性質u≡a1,v≡b1,則u+v≡a1+b1,uv≡a1b1,可得ψ(u+v)=ψ(u)+ψ(v),ψ(uv)=ψ(u)ψ(v).即ψ是同態.

設u≠v.若ψ(u)=ψ(v),即a1≡b1(modγυ-i),那么a≡b(modC[γi-1]),與u≠υ矛盾.

綜上,ψ是單同態.

由引理4可以看出,Ci和K[x]/(xn-1)的某個理想同構,所以,可以根據有限域上循環碼的結構來推導有限鏈環R上循環碼的結構.

引理5有限域K上的一 個[n,k]循環碼C具有生成多項式g(x),degg(x)=n-k.若g(x)首1,則g(x)是唯一的.

定理4Ci可以看做有限域K上的循環碼,且Ci是[n,tυ-i]循環碼,即Ci具有生成多項式γυ-igυ-i(x),γ|/gυ-i(x).且deggυ-i(x)=n-tυ-i.若gυ-i(x)首1,則gυ-i(x)是唯一的.

由Ci中元的性質以及映射ψ的定義知fυ-i(x)=γυ-igυ-i(x),γ|/gυ-i(x),且Ci=γυ-igυ-i(x).

定理5設(p,n)=1,C是R上長為n的循環碼,則存在多項式g0(x),g1(x),…,gυ-1(x),使得C=〈g0(x),γg1(x),…,γυ-1gυ-1(x)〉.且gυ-1(x)|gυ-2(x)|…|g0(x)|xn-1.若gi(x)是首1的,則這些多項式是唯一的.

證明由定理2的證明過程并結合定理4可得C=〈g0(x),γg1(x),…,γυ-1gυ-1(x)〉,且若gi(x)首1,則gi(x)是唯一的.

又γCi?Ci-1,即γυ-i+1gυ-i+1(x)|γ(γυ-igυ-i(x)),得gυ-i+1(x)|gυ-i(x).證畢.

定理5雖然給出有限鏈環上的循環碼的生成多項式的特點,但是怎樣利用xn-1的分解式去構造一個具體的、或是給定類型的循環碼還不行,需引入以下的概念和結論.

定義4[9]一個多項式f稱為無平方因子,若g2|f,則g只能是單位.

引理6[9]若(p,n)=1,那么xn-1在K[x]上無平方因子.也就是說xn-1在K[x]上可分解成兩兩互素的不可約多項式之積.

結合定理5得到下面結論.

定理6設(p,n)=1,C是R上長為n的循環碼,且碼的類型為(k0,k1,…,kυ-1),則存在唯一的首項系數為1且兩兩互素的多項式f0(x),f1(x),…,fυ-1(x),使得gi(x)=fi(x)fi+1(x)…fυ-1(x),0≤i≤υ-1.

證明符號同上,存在唯一的首項系數為1的多項式g0(x),g1(x),…,gυ-1(x),使得C=〈g0(x),γg1(x),…,γυ-1gυ-1(x)〉,deggυ-i(x)=n-tυ-i.

由前面符號記法k0=t0,ki=ti-ti-1,1≤i≤υ-1.得tυ-i=k0+k1+…+kυ-i,所以deggi(x)=n-ti=n-(k0+k1+…+ki)=ki+1+ki+2+…+kυ.定義fυ-1(x)=gυ-1(x),fi=gi/gi+1,0≤i≤υ-2,所以, degfi(x)=ki+1.

下證f0(x),f1(x),…,fυ-1(x)兩兩互素.

若fi(x)與fj(x)不互素i≠j.不妨假設i

定理5和定理6給出了構造有限鏈環上非零循環碼的具體方法:

首先將xn-1分解成兩兩互素的不可約多項式的乘積,不妨設xn-1=h0(x)h1(x)…ht(x),其中h0(x),h1(x),…,ht(x)兩兩互素;

其次,構造多項式f0(x),f1(x),…,fυ-1(x),其中fi(x)是上述不可約多項式，再加上常數1所構成的新的多項式集合中的部分多項式的乘積,且fi(x)兩兩互素.這里degfi(x)=ki+1;

最后,依次作多項式gυ-1(x),gυ-2(x),…,g0(x),其中gi(x)=fi(x)fi+1(x)…fυ-1(x),則C=〈g0(x),γg1(x),…,γυ-1gυ-1(x)〉.C的類型是(k0,k1,…,kυ-1).

上述方法在具體操作過程還需要考慮一些細節問題.由循環碼的構造方法易得下面定理7.

定理7[11]R上長度為n的循環碼的個數為(υ+1)r,r是xn-1的分解式中不可約因子的個數.

例1考慮整數剩余類環Z4上長度為7的循環碼.Z4的極大理想是〈[2]〉,[2]的冪零指數υ=2.在F2上x7-1=(x-1)(x3+x+1)(x3+x2+1)=h0(x)h1(x)h2(x),即r=3,所以共有27個循環碼.

可以這樣去構造一個循環碼:

選取f0=h0,f1=h1,由于degfi(x)=ki+1,那么k1=1,k2=3,所以k0=7-1-3=3,即C是一個類型為(3,1)循環碼,生成元是γf1,f1f0.

通過上述方法,可以夠造出Z4上長度為7的所有循環碼.

表1 環Z4上長度為7的循環碼

[1]HammonsAR,KumarPV,CalderbankAR,etal.TheZ4linearity of kerdock,preparata,goethals,and related codes[J].IEEE Trans Inform Theory, 1994, 40(2):301-309.

[2] Pless V,Sole P,Qian Z.Cyclic self-dualZ4-codes[J].Finite Fields Appl, 1997, 3:48-69.

[3] Calderbank A R,Mc G G,Kumar P V,et al.Cyclic codes overZ4,locator polynomials and Newton's identities[J].IEEE Trans Inform Theory, 1996, 42(1):217-226.

[4] Kanwar P,Lopez-Permouth S R.Cyclic codes over the integers modulopm[J].Finite Fields Appl, 1997, 3:334-352.

[5] Calderbank A R,Sloans N J A.Modular andp-adic cyclic codes[J].Designs,Codes and Cryptography, 1995, 6:21-35.

[6] Blackford J T,Ray-Chaudhuri D K.A transform approach to permutation groups of cyclic codes over Galois rings[J].IEEE Trans Inform Theory, 2000, 46(7):2350-2358.

[7] Norton G H, Salagean A.On the structure of linear and cyclic codes over a finite chain rings[J].Applicable Algebra in Engineering,Communication and Computing, 2000, 10:489-506.

[8] Dougherty S T, Liu H W. Cyclic codes over formal power series rings[J]. Acta Mathematica Scientia (English Version), 2011, B31(1):331-343.

[9] Norton G H, Salagean A. On the structure of linear and cyclic codes over a finite chain ring [J].Appl Algebra Eng Comm Comput, 2000, 10:489-506.

[10] Norton G H, Salagean A. On the Hamming distance of linear codes over a finite chain ring [J].IEEE Trans Inform Theory, 2000, 46(3):1060-1067.

[11] 李光松,韓文報.有限鏈環上的循環碼及其Mattson-Solomn多項式[J].高校應用數學學報(A輯), 2004, 19(2):127-133.

The structure of linear codes and cyclic codes over finite chain rings

SHI Liye， QIU Shuangyue， LIU Liying

(Department of Mathematics and Physics， Handan College， Handan， Hebei 056005)

LetRbeafinitechainring，alinearcodeoflengthnoverRisanR-submoduleofRn， and a cyclic code of lengthnisanidealofR[x]/(xn-1).LetC[γi]={x|x∈C，γix=0}，thenitisasubmoduleofRn，andC[γi]/C[γi-1]isafreemodule.Moreover，ifCisacycliccode，thenC[γi]/C[γi-1]isisomorphicwithanidealofK[x]/(xn-1).Startingfromthis，thestructureoflinearcodesandcycliccodesoverfinitechainringswerestudiedinthispaper.Also，someNorton’smainresultswereshowninadifferentwayandwereextended.

finite chain ring; linear code; cyclic code

2014-09-22.

河北省教育科學研究“十二五”規劃課題(1406028).

1000-1190(2015)03-0348-04

O157.4

A

*E-mail: sxxshily@163.com.