環(huán)q+uFq+u2Fq+…+uk-1Fq上線性碼關(guān)于齊次度量的完備性

陳曉玲,　李　平

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

環(huán)q+uFq+u2Fq+…+uk-1Fq上線性碼關(guān)于齊次度量的完備性

陳曉玲,李平

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

摘要:文章約定R=Fq+uFq+u2Fq+…+uk-1Fq,其中uk=0,q為某一素?cái)?shù)冪,研究環(huán)R上的線性碼關(guān)于齊次度量的完備性,得到了環(huán)R上的線性碼的球形填充界,并且利用這些界去檢驗(yàn)線性碼的完備性,討論了環(huán)R上2種特殊情況下關(guān)于齊次度量的完備線性碼的存在性。

關(guān)鍵詞:齊次距離;齊次重量;完備碼

0引言

線性碼的完備性是編碼理論的重要問(wèn)題之一,20世紀(jì)70年代已確定了有限域中的完備碼的參數(shù)[1-2]。近年來(lái),有限鏈環(huán)上的線性碼引起編碼愛(ài)好者的極大興趣。文獻(xiàn)[3]給出了一些高效的二元碼,將其看成環(huán)Z4上線性碼的Gray像,并將Lee重量引入環(huán)Z4。文獻(xiàn)[4]首次將齊次距離的概念引入整數(shù)剩余類環(huán)中。整數(shù)剩余類環(huán)上的齊次距離是有限域上Hamming重量和剩余類環(huán)Z4上Lee重量的推廣,有著許多重要的應(yīng)用[5],從而引起人們關(guān)注整數(shù)剩余類環(huán)上關(guān)于齊次距離的完備碼的研究。文獻(xiàn)[6]研究了Z4上的線性碼關(guān)于齊次距離的完備碼的存在性,文獻(xiàn)[7]將文獻(xiàn)[6]的結(jié)果推廣到環(huán)Z2l上。至此,環(huán)Z4和環(huán)Z2l上關(guān)于齊次距離的完備碼的存在性問(wèn)題已經(jīng)部分解決。多項(xiàng)式剩余類環(huán)R=Fq+uFq+u2Fq+…+uk-1Fq上線性碼由于具有良好性質(zhì)被廣泛研究[8-11],得到環(huán)R上線性碼齊次距離的許多界[10-11],但關(guān)于其上的線性碼的完備性的討論卻很少。本文研究環(huán)R上關(guān)于齊次度量的完備碼的存在性,利用計(jì)算球內(nèi)的碼字的個(gè)數(shù)的方法,找到環(huán)R上線性碼的完備性的條件,說(shuō)明了2種特殊情況下線性碼是不完備的。

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

設(shè)R=Fq+uFq+u2Fq+…+uk-1Fq,其中uk=0,Fq是q元域,q為某素?cái)?shù)的方冪。環(huán)R是以〈u〉為極大理想的有限鏈環(huán)。對(duì)任意的r∈R,都可以唯一表示為:

其中ri∈Fq,0≤i≤k-1。

環(huán)R上長(zhǎng)為n碼C是Rn的一個(gè)非空子集,當(dāng)C是Rn的R-子模時(shí),則稱C為一個(gè)線性碼。當(dāng)線性碼C有ql個(gè)碼字時(shí),稱C為[n,l]碼。下面給出環(huán)R上齊次重量函數(shù)的定義。

定義1環(huán)R上的齊次重量Wth(x)定義為:

定義2對(duì)于任意的u,v∈C,2個(gè)碼字的齊次距離dh(u,v)為:

設(shè)C是一個(gè)線性碼,碼C的齊次距離(也是齊次重量)d(C)定義為C中非零碼字的齊次重量的最小值,即

為了更好地分析環(huán)R上線性碼的性質(zhì)。下面,給出環(huán)R上線性碼的結(jié)構(gòu)[9]。

引理1有限鏈環(huán)R上的任意線性碼C的生成矩陣經(jīng)過(guò)置換可以寫(xiě)成下面的形式:

其中,Ikj為ki階單位矩陣;ti為正整數(shù),0≤t≤k,并且t0+t1+…+tk-1=n;Aij為定義在Fq上的矩陣。稱C為{t0,t1,…,tk-1}型的線性碼。

2環(huán)R上線性碼的完備性

定義3對(duì)于任意的x,y∈C, 當(dāng)x≠y時(shí),若線性碼C滿足:

(1)

稱碼C是一個(gè)t-糾錯(cuò)碼,若進(jìn)一步滿足:

(2)

則稱碼C是一個(gè)t-完備線性碼。

(3)

定理2設(shè)C是一個(gè)有ql個(gè)碼字的t-糾錯(cuò)碼,則有:

(4)

定理2中的(4)式稱為碼C的球形填充界。結(jié)合定義3和定理1,不難得到,一個(gè)t-糾錯(cuò)的[n,l]碼C是完備碼當(dāng)且僅當(dāng)定理2中的(4)式取等號(hào)。當(dāng)t取定之后,(4)式的值取決于不等式組(5)式的解。

(5)

記(5)式的解集為:

下面給出t取部分具體值時(shí)的球形填充界,然后利用這些界去檢驗(yàn)完備線性碼的存在性。

推論1設(shè)C是環(huán)R上的一個(gè)t-糾錯(cuò)的[n,l]碼,則

1）符合喘證診斷標(biāo)準(zhǔn)，目前處于穩(wěn)定期；2）年齡在30～80歲之間，性別不限；3）患者知情同意，可按研究要求堅(jiān)持檢查和治療及隨訪。

(1) 當(dāng)t=(q-1)qk-2時(shí),有

(2) 當(dāng)t=qk-1,q≠2時(shí),有

當(dāng)q=2時(shí),有

所以有1+n(qk-1)≤qkn-l。

當(dāng)q=2時(shí),則(5)式的解集為St={(0,0),(1,0),(0,1),(2,0)},代入定理2中的(4)式得:

化簡(jiǎn)得:

為給出推論1中的齊次重量t-糾錯(cuò)完備碼的存在性,先給出引理2。

引理2設(shè)n、k為某正整數(shù),存在正整數(shù)m使得n=2m-1,l=n-m,當(dāng)且僅當(dāng)k=1,關(guān)于l的方程(6)式有正整數(shù)解。

(6)

證明當(dāng)k=1時(shí),(6)式變?yōu)閚+1=2n-l,易證n+1=2n-l,從中推出l=n-lb(n+1),所以(6)式有正整數(shù)解當(dāng)且僅當(dāng)存在正整數(shù)m，使得n=2m-1,l=n-m。

下面證明當(dāng)k≥2時(shí),(6)式無(wú)整數(shù)解。

假設(shè)(6)式有解l0,令m=kn-l0,移項(xiàng)得:

(7)

設(shè)a=(22k-1-2k+1+2)≠0,b=(-22k-1-3×2k-3),c=1-2m,所以可將(7)式看成一個(gè)關(guān)于n的一元二次方程,其判別式為:

易得Δ>0,所以方程有2個(gè)不相等的根,如果二次方程有一個(gè)正整數(shù)根為r1,如果另外一個(gè)根也是整數(shù),則這個(gè)方程就有2個(gè)整數(shù)根,但由韋達(dá)定理知,兩根之和為:

其中,t是正整數(shù)。又因?yàn)椋?/p>

設(shè)x=2k,因此有:

定理3環(huán)R上t-糾錯(cuò)的完備線性碼是不存在的,其中,t=(q-1)qk-2或者t=qk-1。

證明由推論1,若存在(q-1)qk-2-糾錯(cuò)的完備線性碼,則存在[n,l]碼使得1+n(qk-q)=qkn-l成立,方程兩邊同時(shí)模q得1≡0(modq),這與q為素?cái)?shù)的方冪矛盾,故不存在(q-1)qk-2-糾錯(cuò)的完備線性碼。

當(dāng)t=qk-1時(shí),分2類討論。第1類,q=2,由推論1得,若存在qk-1-糾錯(cuò)的完備線性碼,則存在[n,l]碼使得:

(8)

但引理2證明了(8)式有解當(dāng)且僅當(dāng)k=1且存在正整數(shù)m，使得n=2m-1,l=n-m。此時(shí)多項(xiàng)式剩余類環(huán)退化為二元域F2,且二元漢明碼恰好是1-糾錯(cuò)完備碼。當(dāng)k≥2時(shí),均不存在完備碼。

第2類,q≠2,由推論1得,若存在qk-1-糾錯(cuò)的完備線性碼,則存在[n,l]碼使得1+n(qk-1)=qkn-l，方程兩邊同時(shí)模q得n≡1(modq),所以,可設(shè)n=qmb+1,(b,q)=1,代回原方程化簡(jiǎn)得:

(9)

(1) 當(dāng)k≤m時(shí),(9)式右邊提出qk因子得:

因?yàn)?[(qm-qm-k)b+1]與q互素,且qkqmb+k-l是q的方冪,因此有:

又因?yàn)閝m≥qm-k,所以有:

矛盾。

(2) 當(dāng)k>m時(shí),(9)式右邊提出qm因子得:

(9)式成立當(dāng)且僅當(dāng):

也就是滿足(qk-1)b=1-qk-m,由此推出1-qk-m≥0,qk-m≤1,即k=m,矛盾。

故此t-完備線性碼是不存在的。

證畢。

3結(jié)束語(yǔ)

本文介紹了環(huán)R上線性碼的性質(zhì)和結(jié)構(gòu),研究了環(huán)R上的關(guān)于齊次度量的完備線性碼的存在性問(wèn)題,證明出了環(huán)R上2種特殊情況下完備線性碼是不存在的,推廣了文獻(xiàn)[7]的結(jié)果。

[參考文獻(xiàn)]

[1]Tietavainen A. On the nonexistence of perfect codes over finite fields[J].SIAM Journal on Applied Mathematics,1973,24(1):88-96.

[2]MacWilliams F J,Sloane N J A.The theory of error correcting codes[M].Amsterdam:North-Holland Pub Co,1997:32-54.

[3]Hammons A R,Jr,Kumar P V,Calderbank A R,et al.TheZ4-linearity of Kerdock,Preparata, Goethals, and related codes[J]. IEEE Transaction on Information Theory,1994,40(2):301-319.

[4]Constantinescu I, Heise W. A metric for codes over residue class rings of integers [J].Problemy Peredachi Informatii, 1997,33(3):22-28.

[5]Greferath M, Schmidt S E. Finite-ring combinatorics and MacWilliams’ equivalence theorem [J]. J Combin Theory, Ser A, 2000,92(1):17-28.

[6]Ozen M, Siap V. On the existence of perfect linear codes overZ4with respect to homogenous weight[J]. Applied Mathematicaal Sciences,2012,6(41):2005-2011.

[7]Siap I,Ozen M,SiapV.On the existence of perfect linear codes overZ2lwith respect to homogenous metric[J].Arabain Journal for Science and Engineering, 2013,38(8):2189-2192.

[8]李平,朱士信.論環(huán)FP+uFP+…uk-1FP上的循環(huán)碼 [J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版, 2006,29 (6):794-797.

[9]朱士信,李巖,鄧林.環(huán)Fq+uFq+u2Fq+…+uk-1Fq上的一類常循環(huán)碼 MDS碼[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2013,43(3):494-497.

[10]劉曉娟,朱士信.環(huán)FPm+uFPm+u2FPm+…+uk-1FPm上的長(zhǎng)為Ps的(1+λu)常循環(huán)碼的距離分布[J]. 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2012,42(11):931-935.

[11]朱士信,黃素娟.環(huán)FPm+uFPm+u2FPm+…+uk-1FPm上(1+u)常循環(huán)碼的距離分布[J]. 電子與信息學(xué)報(bào),2013,35(11):931-935.

(責(zé)任編輯張淑艷)

On the existence of perfect linear codes overFq+uFq+u2Fq+…+uk-1Fqwith respect to homogeneous metric

CHEN Xiao-ling,LI Ping

(School of Mathematics, Hefei University of Technology, Hefei 230009, China)

Abstract:In this paper, R denotes the ring Fq+uFq+u2Fq+…+uk-1Fq, where uk=0 and q is a power of a prime. The existence of perfect linear codes over Fq+uFq+u2Fq+…+uk-1Fq with respect to homogeneous metric is studied, and the sphere bounds of linear codes over R are obtained. The existence of perfect linear codes over R with respect to homogeneous metric under two kinds of special circumstances is discussed by using the bounds.

Key words:homogeneous distance; homogeneous weight; perfect code

收稿日期：2015-02-09

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61370089)

作者簡(jiǎn)介：陳曉玲(1991-),女,安徽合肥人,合肥工業(yè)大學(xué)碩士生;

doi:10.3969/j.issn.1003-5060.2016.05.026

中圖分類號(hào):TN911.22

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1003-5060(2016)05-0712-04

李平(1971-),男,安徽無(wú)為人,博士,合肥工業(yè)大學(xué)副教授,碩士生導(dǎo)師.