国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

有限鏈環(huán)上線性碼和循環(huán)碼的結(jié)構(gòu)

2015-03-21 07:10石立葉邱雙月劉麗英
關(guān)鍵詞:鏈環(huán)同態(tài)線性

石立葉, 邱雙月, 劉麗英

(邯鄲學(xué)院 數(shù)理學(xué)院, 河北 邯鄲 056005)

?

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

(邯鄲學(xué)院 數(shù)理學(xué)院, 河北 邯鄲 056005)

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

有限鏈環(huán); 線性碼; 循環(huán)碼

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

1 有限鏈環(huán)上的線性碼

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

通過(guò)定義發(fā)現(xiàn)有限鏈環(huán)R的所有理想都是主理想,因?yàn)槿鬜的理想I不是主理想,則I至少有兩個(gè)生成元,不妨設(shè)I=〈a1,a2,…,as〉,則〈a1〉?〈a2〉,〈a2〉?〈a1〉,與R是有限鏈環(huán)矛盾.這也表示,有限鏈環(huán)極大理想是唯一的.

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

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

因?yàn)镽有限,上鏈不會(huì)無(wú)限不終止,即存在自然數(shù)i,使得〈γi〉=0.設(shè)υ是使得〈γυ〉=0的最小的自然數(shù),那么υ就叫做γ的冪零指數(shù).

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

引理1[7]任意r∈R{0},存在唯一整數(shù)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.設(shè)y=γαy1,y1是單位,則yx=γαy1x=0,得γαx=0,故α≥m,即y∈γmR.得證.

符號(hào)同上,考慮有限鏈環(huán)R上的線性碼C.因?yàn)橛邢捩湱h(huán)R上一個(gè)長(zhǎng)度為n的線性碼C是R-模Rn的一個(gè)子模,反之也成立,所以,只要研究Rn的子模即可.

設(shè)M是Rn的一個(gè)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-模.因?yàn)橹骼硐氕h(huán)上無(wú)扭的有限生成模一定是自由模,又K是域,且M[γi]/M[γi-1]是無(wú)扭模,所以,M[γi]/M[γi-1]是自由模,也可看做數(shù)域K上的線性空間.設(shè)其秩或其維數(shù)為tυ-i,1≤i≤υ,令k0=t0,ki=ti-ti-1,1≤i≤υ-1.

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

定理1符號(hào)同上,則

(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≠M(fèi)i-1,因?yàn)镸i是自由模,且秩為tυ-i,不妨設(shè)u1,u2,…utυ-i是一組基,即Mi?Ru1?Ru2?…?Rutυ-i.又γiuj=0,γi-1uj≠0,0≤j≤tυ-i.應(yīng)用引理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,其中每個(gè)向量vi的長(zhǎng)度為ki,向量中的元都屬于γiR.由此,給出碼的類型的定義.

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

由前面討論,那么對(duì)于有限鏈環(huán)Zpα上的非零的類型為(k0,k1,…,kυ-1)的線性碼C來(lái)說(shuō),C所包含的碼字個(gè)數(shù)為1k0pk1(p2)k2…(pυ-1)kυ-1.

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

關(guān)于對(duì)偶碼的類型有如下結(jié)論:

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

2 有限鏈環(huán)上的循環(huán)碼

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

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

和線性碼的討論類似,記Ci=C[γi]/C[γi-1].易證C[γi]是Rn的理想,由環(huán)同態(tài)定理可知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),且有下述結(jié)論.

引理4上述映射是單同態(tài).

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

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

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

綜上,ψ是單同態(tài).

由引理4可以看出,Ci和K[x]/(xn-1)的某個(gè)理想同構(gòu),所以,可以根據(jù)有限域上循環(huán)碼的結(jié)構(gòu)來(lái)推導(dǎo)有限鏈環(huán)R上循環(huán)碼的結(jié)構(gòu).

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

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

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

定理5設(shè)(p,n)=1,C是R上長(zhǎng)為n的循環(huán)碼,則存在多項(xiàng)式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的,則這些多項(xiàng)式是唯一的.

證明由定理2的證明過(guò)程并結(jié)合定理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雖然給出有限鏈環(huán)上的循環(huán)碼的生成多項(xiàng)式的特點(diǎn),但是怎樣利用xn-1的分解式去構(gòu)造一個(gè)具體的、或是給定類型的循環(huán)碼還不行,需引入以下的概念和結(jié)論.

定義4[9]一個(gè)多項(xiàng)式f稱為無(wú)平方因子,若g2|f,則g只能是單位.

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

結(jié)合定理5得到下面結(jié)論.

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

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

由前面符號(hào)記法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.不妨假設(shè)i

定理5和定理6給出了構(gòu)造有限鏈環(huán)上非零循環(huán)碼的具體方法:

首先將xn-1分解成兩兩互素的不可約多項(xiàng)式的乘積,不妨設(shè)xn-1=h0(x)h1(x)…h(huán)t(x),其中h0(x),h1(x),…,ht(x)兩兩互素;

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

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

上述方法在具體操作過(guò)程還需要考慮一些細(xì)節(jié)問(wèn)題.由循環(huán)碼的構(gòu)造方法易得下面定理7.

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

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

可以這樣去構(gòu)造一個(gè)循環(huán)碼:

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

通過(guò)上述方法,可以夠造出Z4上長(zhǎng)度為7的所有循環(huán)碼.

表1 環(huán)Z4上長(zhǎng)度為7的循環(huán)碼

[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] 李光松,韓文報(bào).有限鏈環(huán)上的循環(huán)碼及其Mattson-Solomn多項(xiàng)式[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào)(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.

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

1000-1190(2015)03-0348-04

O157.4

A

*E-mail: sxxshily@163.com.

猜你喜歡
鏈環(huán)同態(tài)線性
漸近線性Klein-Gordon-Maxwell系統(tǒng)正解的存在性
簡(jiǎn)單拓?fù)鋱D及幾乎交錯(cuò)鏈環(huán)補(bǔ)中的閉曲面
氣動(dòng)葫蘆吊用短環(huán)鏈的鏈環(huán)斷裂原因分析
線性回歸方程的求解與應(yīng)用
關(guān)于半模同態(tài)的分解*
拉回和推出的若干注記
圈-雙交叉多面體鏈環(huán)的Kauffman括號(hào)多項(xiàng)式和束多項(xiàng)式
二階線性微分方程的解法
一種基于LWE的同態(tài)加密方案
HES:一種更小公鑰的同態(tài)加密算法
万载县| 吕梁市| 青川县| 秦皇岛市| 崇州市| 衡阳市| 芜湖市| 泸西县| 聊城市| 高台县| 阿克陶县| 巩留县| 东源县| 化隆| 淄博市| 贵定县| 西吉县| 宣化县| 濉溪县| 南靖县| 汝城县| 武汉市| 神木县| 彭州市| 于都县| 呼伦贝尔市| 蒲江县| 郑州市| 虹口区| 亚东县| 滦南县| 洛川县| 光山县| 抚宁县| 连平县| 时尚| 龙海市| 海南省| 汉中市| 康乐县| 额尔古纳市|