環(huán)Fq+uFq+u2Fq+…+uk-1Fq上線性碼的覆蓋半徑

鐘家偉,　李　平

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

?

環(huán)Fq+uFq+u2Fq+…+uk-1Fq上線性碼的覆蓋半徑

鐘家偉,李平

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

摘要:文章研究了有限鏈環(huán)R=Fq+uFq+u2Fq+…+uk-1Fq上長為n的線性碼關(guān)于齊次距離的覆蓋半徑,其中uk=0,q為某一素?cái)?shù)冪。構(gòu)造了環(huán)R上的廣義Gray映射,得到了R上線性碼關(guān)于覆蓋半徑的相關(guān)性質(zhì),并研究了環(huán)R上線性碼覆蓋半徑的上下界。

關(guān)鍵詞:線性碼;齊次距離;齊次重量;Gray映射;覆蓋半徑

0引言

有限鏈環(huán)上的齊次重量是有限域上的Hamming重量和剩余類環(huán)Z4上Lee重量的推廣,對有限鏈環(huán)上碼的結(jié)構(gòu)和相關(guān)度量的研究有著重要意義。文獻(xiàn)[1]最先將齊次重量的概念引入編碼理論研究中;文獻(xiàn)[2]研究了有限環(huán)上齊次重量的存在性與唯一性,得到了有限環(huán)上齊次重量的一種計(jì)算公式；文獻(xiàn)[3]利用生成特征標(biāo)研究了Frobenius環(huán)上齊次重量的另一種計(jì)算公式；文獻(xiàn)[4]在文獻(xiàn)[2]的基礎(chǔ)上得到Galois環(huán)上的齊次重量的表達(dá)形式,并構(gòu)造出有限環(huán)上的代數(shù)幾何碼,同時還研究了環(huán)上齊次重量的上下界。

近年來,有限鏈環(huán)R=Fq[u]/(uk)引起編碼愛好者極大的興趣。有限鏈環(huán)上線性碼的齊次重量對揭示有限鏈環(huán)上線性碼的結(jié)構(gòu)和相關(guān)性質(zhì)有著非常重要的作用。同時,有限鏈環(huán)上線性碼的齊次重量對構(gòu)造有限鏈環(huán)上的最優(yōu)碼也起著重要作用。目前,已有許多文獻(xiàn)研究了環(huán)上線性碼的齊次重量的相關(guān)性質(zhì)，如文獻(xiàn)[5-8]。文獻(xiàn)[9]研究了Z4上Lee距離和歐幾里德距離的覆蓋半徑；文獻(xiàn)[10]研究了環(huán)F2+uF2上Lee距離的覆蓋半徑;文獻(xiàn)[11]研究了Zpm上Lee距離的覆蓋半徑。 本文在文獻(xiàn)[10-11]的基礎(chǔ)上構(gòu)造了環(huán)R上的保距廣義Gray映射,由此得到R上關(guān)于齊次距離覆蓋半徑的上下界及其相關(guān)性質(zhì)。

1R上的廣義Gray映射

設(shè)Fq為某一個q元域,取Fq中的向量v=(1,1,1,…，1),w=(0,1,2,…，q-1)。令

(1)

即

其中，k∈N*；δi,j表示Kronecker符號；i=0,1,…,k-1；?表示Fq上的張量積運(yùn)算。

由文獻(xiàn)[12]可知(u)為R的唯一極大理想,對于R中任意元素x可唯一表示為:

其中，xi∈Fq。

定義1對于R上任意元素x=x0+ux1+u2x2+…+uk-1xk-1,若存在φ使得:

環(huán)R上長為n的線性碼是Rn的R-子模。設(shè)C為Fq上長為n的線性碼,wh(x)表示C上的碼字x=(x0,x1，…，xn-1)的Hamming重量。dh表示線性碼C上的Hamming距離,則易知dh為線性C上非零碼字的極小Hamming重量,即

定義2設(shè)C為環(huán)R上的線性碼,w(C)表示C的齊次重量,顯然w(C)是R上的重量函數(shù),即對于任意的r∈R,w:R→N,且

對任意的x=(x0,x1…xn-1)∈C,其齊次重量為:

對于線性碼C,其齊次距離d(C)為[8]:

證明對任意的r=r0+ur1+…+uk-1rk-1∈R,則有：

(1) 當(dāng)r=0時,φ(0)=(0,0,0,…,0),顯然

(2) 當(dāng)r∈(uk-1){0}時,有

由定義2可知w(r)=wh(φ(r))。

(3) 當(dāng)r∈R(uk-1),令

綜上可得,設(shè)x=(x0,x1,…,xn-1)為R上長為n的碼字,則

證畢。

引理2設(shè)C為Fq上長為n的線性碼,φ(C)是C的廣義Gray映射,則

證明對于任意的x∈C,由引理1可知x≠0當(dāng)且僅當(dāng)φ(x)≠0,x∈C,當(dāng)且僅當(dāng)φ(x)∈φ(C),因此d(x)滿足:

證畢。

2碼的覆蓋半徑

給出環(huán)R上線性碼關(guān)于齊次距離覆蓋半徑的概念,研究R上線性碼關(guān)于齊次距離覆蓋半徑上下界的相關(guān)性質(zhì)。

定義3設(shè)C為環(huán)R上的線性碼,r表示C上齊次距離的覆蓋半徑,

由上述定義可知,對于任意u∈Rn,令

定理1設(shè)r(C)為環(huán)R上的線性碼C關(guān)于齊次距離的覆蓋半徑,則有r(C)=rh(φ(C))成立,其中rh(φ(C))是定義在Fq上關(guān)于Hamming距離的覆蓋半徑。

證明由r(C)的定義以及引理2可得:

r(C)=max{d(u,C)|?u∈Rn}=

max{dh(φ(u),φ(C))|?u∈Rn}=

rh(φ(C))。

證畢。

為了更進(jìn)一步得到R上線性碼覆蓋半徑的性質(zhì),研究其上下界的情況。

定理2假設(shè)C是環(huán)R上長為n的線性碼,則有：

由引理1知φ為保距同構(gòu)映射,因此有|φ(C)|=|C|成立,定理得證。

定義4設(shè)C是環(huán)R上長為n的線性碼,則對任意的x∈Rn,x+c={x+c|?c∈C}稱作x關(guān)于加法子群C的陪集,每個陪集中的最小重量稱做該陪集的重量,記為wh(x+c)[10]。

在研究中,發(fā)現(xiàn)陪集首對于研究線性碼覆蓋半徑起著非常重要的作用。

定理3設(shè)C是環(huán)R上長為n的線性碼,則C上的線性碼關(guān)于齊次距離的覆蓋半徑r(C)等于C的全體陪集的陪集首齊次重量的最大值。

證明當(dāng)x跑遍Rn時,-x也跑遍Rn,于是

證畢。

由于R上線性碼有著良好的性質(zhì),顯然R上線性碼的直和以及直積也是R上的線性碼。構(gòu)造R上線性碼直和、直積以及線性組合的碼,對其上覆蓋半徑進(jìn)行了相關(guān)的研究。

定義5設(shè)C1、C2是R上長為n的線性碼,記C1與C2的直和為:

C1與C2的直積為:

引理3設(shè)C1、C2是R上長為n的線性碼[13],則

r(C1*C2)≥max{n1r(C1),n2r(C2)}。

引理4令C1、C2為R上長為n的線性碼, G1、G2分別為C1、C2的生成矩陣,若線性碼C的生成矩陣為[14]：

則r(C)≥r(C1)+r(C2)。其中，A為R上的矩陣。

引理3、引理4可由文獻(xiàn)[13-14]直接得到,在此不再證明。以上結(jié)論還可以推廣至R上有限個線性碼的直和、直積以及線性組合碼覆蓋半徑的性質(zhì),結(jié)果依然成立。

設(shè)C1、C2也是R上的線性碼,C1?C2，則可得到C1覆蓋半徑的一個下界。

定理4設(shè)C1、C2是R上的線性碼,C2的極小重量記為d(C2)。若C1?C2,則有:

證明令ν是C2C1中極小重量的碼字,則ν是C1的陪集首,故w(ν)≥d(C2),所以

證畢。

定義C的對偶碼C⊥為:

其中，x·y是x與y的直積。若C?C⊥,則稱C自正交,若C=C⊥則稱C是自對偶。

引理5令ν是C的陪集首,若μ是ν的子集,且μ、ν為非零碼字，則μ也是C的陪集首[14]。

在定理5中得到了R上線性碼的對偶碼的覆蓋半徑的一個上界。

定理5對于環(huán)R上線性碼C,記

則有：

其中，Ai(C⊥)表示C⊥中齊次重量為i的碼字的數(shù)目。

證明令C是[n,k,d]線性碼,D是由C以及C的陪集C+{ν}所生成的(n,k+1)碼,其中ν是陪集首。由于C?D，則D⊥?C⊥,因此D⊥最多有S(C⊥)個不同的齊次重量,由于碼字來自C或者C+{aν},其中a≠0,a∈R,aν在DC中有極小齊次重量。因此給出了C的齊次重量分布,當(dāng)DC中所有碼字的極小齊次重量至少為S(C⊥)時,D⊥的齊次重量分布就唯一決定了。由Macwilliams恒等式可知,當(dāng)w(ν)≥S(C⊥)時,D的齊次重量分布是唯一決定的。由定理3可知,一個陪集首能達(dá)到的最大齊次重量是S(C⊥),因此r(C)≤S(C⊥)。證畢。

3結(jié)束語

本文構(gòu)造環(huán)上的廣義Gray映射,推廣了文獻(xiàn)[10-11]的結(jié)果。研究環(huán)R上的線性碼關(guān)于齊次距離的覆蓋半徑與域Fq上的線性碼關(guān)于漢明距離的覆蓋半徑之間的關(guān)系,得到了R上覆蓋半徑上下界。進(jìn)一步,還研究了R上線性碼的直和、直積以及線性組合碼的覆蓋半徑。最后,得到了R上自對偶碼的覆蓋半徑上下界的相關(guān)性質(zhì)。

[參考文獻(xiàn)]

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

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

[3]Honold T. Characterization of finite Frobenius ring [J].Arch Math (Basel),2001,76(6):406-415.

[4]Voloch J F,Walker J L.Homogeneous weights and exponential sums [J].Finite Fields Appl,2003,9(3):310-321.

[5]Byrne E, Greferath M, Honold T. Ring geometries, two-weight codes, and strongly regular graphs [J]. Des Codes, Crypt, 2008(48):1-16.

[6]Greferath M, O’Sullivan M E. On bounds for codes over Frobenius rings under homogeneous weights [J]. Discrete Mathematics, 2004, 289:11-24.

[7]Greferath M, McGuire G, O’Sullivan M E.On plotlin-optimal codes over finite Frobenius ring [J]. Journal of Algebra and Its Applications, 2006(5):799-815.

[8]Greferath M,Schmidts S E. Gray isometries for finite chain rings and a nonlinear ternary (36,312,15)ode [J]. IEEE Trans Inform Theory, 1999, 45(7):2522-2524.

[9]Aoki T, Gaborit T, Harada M, Ozeki M and Sole P. On the covering radius of Z4codes and their lattices[J]. IEEE Trans Inform Theory, 1999,45(6):2162-2168.

[10]李平,朱士信,余海峰.環(huán)F2+uF2上碼的覆蓋半徑[J].中國科學(xué)技術(shù)大學(xué)學(xué)報(bào),2008,38(2):145-148.

[11]Manish. K. Gupta C. Durairajan. On the covering radius of some modular codes[J]. eprint arXiv: 1206-3038.

[12]Heise W, Honold T,Nechaev A. Weighted modules and representations of codes[J]. Probl Peredachi Inf，1999,35(3):18-39.

[13]Assmus E F,Pless V. On the covering radius of extremal self-dual codes[J]. IEEE Trans Inform Theory, 1983(29): 359-363.

[14]Cohen G D, Karpovsky M G, Mattson H F,et al.Covering radius-Survey and recent results[J]. IEEE Trans Inform Theory, 1985(31): 328-343.

(責(zé)任編輯馬國鋒)

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

Covering radius of linear codes over ringFq+uFq+u2Fq+…+uk-1Fq

ZHONG Jia-wei,LI Ping

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

Abstract:In this paper, the covering radius of linear codes over R=Fspan+uFspan+u2Fspan+…+uspanFspanwith length n about homogeneous distance is studied, where uspan=0, q is a power of prime. Some properties of linear codes over R about homogeneous distance are obtained by generalized Gray map. The upper and lower bounds of covering radius of linear codes over R about homogeneous distance are also studied.

Key words:linear code; homogeneous distance; homogeneous weight; Gray map; covering radius

中圖分類號:TN911.22

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

文章編號：1003-5060(2015)03-0424-04

doi:10.3969/j.issn.1003-5060.2015.03.027

作者簡介：鐘家偉(1990-),男,安徽六安人,合肥工業(yè)大學(xué)碩士生;

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61370089);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(J2014HGXJ0073)和合肥工業(yè)大學(xué)博士學(xué)位人員專項(xiàng)基金資助項(xiàng)目(JZ2014HGBZ0029)

收稿日期：2014-01-15；修回日期：2014-04-10