黃德為

(合肥工業(yè)大學(xué)應(yīng)用數(shù)學(xué)系，合肥230009)

?

環(huán)F2+vF2上碼的覆蓋半徑

黃德為

(合肥工業(yè)大學(xué)應(yīng)用數(shù)學(xué)系，合肥230009)

[摘要]通過(guò)研究環(huán)F2+vF2上線性碼的結(jié)構(gòu)特征，根據(jù)Gray映射，定義了兩個(gè)二元碼，從而證明了環(huán)F2+vF2上線性碼關(guān)于李距離的覆蓋半徑等于兩個(gè)二元碼的覆蓋半徑之和，并得到環(huán)F2+vF2上對(duì)偶碼的覆蓋半徑的一些結(jié)論，給出了覆蓋半徑的幾個(gè)上下界.

[關(guān)鍵詞]Gray映射； 笛卡爾積； 覆蓋半徑； 二元碼； 李距離

1引言

一個(gè)碼C關(guān)于漢明距離的覆蓋半徑是指C所在向量空間中每個(gè)向量與碼C的Hamming距離的最大值.從1980年開(kāi)始，研究學(xué)者們對(duì)碼的覆蓋半徑產(chǎn)生了很大的興趣.它不僅關(guān)系到數(shù)據(jù)壓縮、傳輸，一次寫(xiě)入內(nèi)存等實(shí)際問(wèn)題，在編碼理論研究中也具有十分重要的意義.覆蓋半徑是一個(gè)幾何參數(shù)，在最小距離譯碼中標(biāo)志著碼的最大糾錯(cuò)能力.近年來(lái)仍有不少文章研究碼的覆蓋半徑[1-4].在1989年，Nechaev研究發(fā)現(xiàn)Kerdock碼可以看成環(huán)Z4上的循環(huán)碼.1994年后，環(huán)Z4上糾錯(cuò)碼理論的研究便成為糾錯(cuò)碼理論研究的熱點(diǎn)問(wèn)題之一.幾個(gè)四元素的整數(shù)剩余類環(huán)上碼的覆蓋半徑的研究也相繼出現(xiàn).文獻(xiàn)[5]研究了Z4碼和其Gray映射后的二元非線性碼的覆蓋半徑，給出了一些上下界.文獻(xiàn)[6]研究了環(huán)F2+uF2上碼的覆蓋半徑. 但是關(guān)于環(huán)F2+vF2上碼的覆蓋半徑的研究很少.

環(huán)F2+vF2上碼的研究一直是一個(gè)熱點(diǎn)問(wèn)題.本文約定

U=F2+vF2={0,1,v,1+v}，

其中v2=v.文獻(xiàn)[7]討論了環(huán)U上線性碼和循環(huán)碼的結(jié)構(gòu)和性質(zhì)，并指出了循環(huán)碼與二元碼之間的關(guān)系.文獻(xiàn)[8]定義了U上碼字的李重量分布的概念，給出了該環(huán)上線性碼與對(duì)偶碼之間各種重量分布的Mac Williams恒等式.文獻(xiàn)[9]討論了U上的二次剩余碼.文獻(xiàn)[10]給出了一個(gè)從U上循環(huán)碼構(gòu)造量子糾錯(cuò)碼的新方法.本文定義了環(huán)U上碼關(guān)于李距離的覆蓋半徑，利用Gray映射，定義了兩個(gè)二元碼，研究了U上碼的覆蓋半徑與二元碼覆蓋半徑的關(guān)系.

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

環(huán)U=F2+vF2={0,1,v,1+v}，其中v2=v.U也可以看成商環(huán)F2[v]/(v2+v).環(huán)U中每個(gè)元素都是冪等元，具有兩個(gè)極大理想和<1+v>.U上長(zhǎng)為n的線性碼C是Un的一個(gè)U-子模. 定義U中元素0,1,v,1+v的李重量(Lee weight)分別為0，2，1，1.Un中向量x的李重量wtL(x)為其各分量的李重量的有理和.很自然的定義Un中兩向量x和y的李距離dL(x,y)為x-y的李重量.C的最小李距離dL(C)定義為C中任意兩個(gè)不同碼字的李距離的最小值.

設(shè)x=(x1,x2,…,xn),y=(y1,y2,…,yn)為Un的兩個(gè)元素，定義x和y在Un上的歐氏內(nèi)積

x·y=x1·y1+x2·y2+…+xn·yn.

定義碼C的對(duì)偶碼

C⊥={x|x·y=0, ?y∈C}.

如果C=C⊥，則稱碼C是自對(duì)偶碼.

3主要結(jié)果

引理1.2[7]設(shè)C是U上線性碼，那么有φ(C)=C1?C2，|C|=|C1|·|C2|而且φ(C)是線性碼.

證?(r1,r2,…,rn,q1,q2,…qn)∈φ(C),設(shè)ci=ri+v(ri+qi),i=1,2,…n.由φ是保距映射,有c=(c1,c2,…,cn)∈C.由C1,C2的定義,我們知道

(r1,r2,…,rn)∈C1,

(q1,q2,…,qn)∈C2,

因此 (r1,r2,…rn,q1,q2,…,qn)∈C1?C2.所以φ(C)?C1?C2.另一方面,對(duì)任意

(r1,r2,…rn,q1,q2,…,qn)∈C1?C2,

其中(r1,r2,…,rn)∈C1, (q1,q2,…,qn)∈C2,存在

a=(a1,a2,…,an),b=(b1,b2,…bn)∈C

使得

ai=ri+vmi,bi=qi+(1+v)ni,

其中mi,ni∈F2且1≤i≤n.因?yàn)镃是線性的有

c=(1+v)a+vb=r+v(r+q)∈C.

這表明

φ(c)=(r1,r2,…,rn,q1,q2,…qn),

所以C1?C2∈φ(C).因此φ(C)=C1?C2.第二個(gè)結(jié)果易證.

引理1.3[7]設(shè)C是U上長(zhǎng)為n線性碼,C⊥是C的對(duì)偶碼,則

定義1.4規(guī)定Un中任一向量y與碼C的李距離

dL(y,C)=min{dL(y,x)|?x∈C}

而規(guī)定碼C關(guān)于李距離的覆蓋半徑

RL(C)=max{dL(y,C)|?y∈n}.

命題1.5U上碼C關(guān)于李距離的覆蓋半徑RL(C)=R(φ(C)).

證?x∈Un,y∈C,由引理1.1知dL(x,y)=d(φ(x),φ(y))，所以

dL(x,C)=d(φ(x),φ(C))，

在(n,k)線性碼中，二個(gè)碼字x,y之間對(duì)應(yīng)碼元位上符號(hào)取值不同的個(gè)數(shù)，稱為碼字x,y之間的漢明距離，用d(x,y)表示.(n,k)線性分組碼的一個(gè)碼字對(duì)應(yīng)于n維線性空間中的一點(diǎn)，碼字間的距離即為空間中兩對(duì)應(yīng)點(diǎn)的距離，因此，碼字間的距離滿足一般距離公理，當(dāng)然滿足三角不等式

d(x,y)+d(y,z)≥d(x,z).

因?yàn)閐L(x,y)=d(φ(x),φ(y)),所以易證對(duì)任意x,y,z∈n，一定有性質(zhì)

dL(x,y)≤dL(x,z)+dL(z,y).

由這個(gè)性質(zhì)可獲得下面的結(jié)論.

定理1.6設(shè)C是U上碼,C的最小李距離記成dL(C).C1,C2的最小漢明距離分別記成d(C1),d(C2),則

若C是線性的,則

?x,y∈C且x≠y,則

dL(x,y)≤dL(x,y+e)+dL(y+e,y).

從而

dL(x,y+e))≥dL(x,y)-dL(y+e,y)=dL(x,y)-wtL(e)

所以由定義1.4可知

若C是線性碼,由引理1.1知,dL(C)=d(φ(C)).再由引理1.2知

d(φ(C))=d(C1?C2)=min{d(C1),d(C2)}.

后半部分得證.

定理1.7設(shè)C是U上線性碼，則

RL(C)=R(C1)+R(C2)，

而且

證由定義1.4及命題1.5知

對(duì)某個(gè)y,不妨設(shè)y=y1|y2(y1,y2長(zhǎng)度相同),再由引理2可得

d(y,φ(C))=min{d(y,x),?x∈φ(C)}=min{d(y1,c1)+d(y2,c2),?c1∈C1,c2∈C2}

=min{d(y1,c1),?c1∈C1}+min{d(y2,c2),?c2∈C2}=d(y1,C1)+d(y2,C2).

由引理1.3知

再用上面類似的證明過(guò)程可得定理后半部分結(jié)論.

引理1.4[12]記K是一個(gè)二元碼(線性的或非線性的),s(K)表示K的對(duì)偶碼或K的形式定義的對(duì)偶碼的距離分布中不同的非零距離的數(shù)目,則R(K)≤s(K)，這個(gè)結(jié)論也稱為Delsarte界.

證由定理1.7知RL(C)=R(C1)+R(C2),再由Delsarte界知推論成立.

定理1.9設(shè)C是U上長(zhǎng)為n的線性碼,且C1,C2分別為[n,k1],[n,k2]線性碼,則RL(C)≤2n-k1-k2.

R(C1)≤n-k1,R(C2)≤n-k2.

由定理1.7知

RL(C)=R(C1)+R(C2)≤2n-k1-k2.

4結(jié)論

本文研究了環(huán)U上線性碼和對(duì)偶碼關(guān)于李距離的覆蓋半徑，給出了覆蓋半徑的幾個(gè)上下界.這些內(nèi)容的研究對(duì)進(jìn)一步豐富環(huán)U上糾錯(cuò)碼理論及構(gòu)造一些性能較好的碼都有一定的指導(dǎo)意義.也可在本文的基礎(chǔ)上，研究一些其它有限環(huán)上碼的覆蓋半徑.

[參考文獻(xiàn)]

[1]Masaaki H, Michio O, Kenichiro T. On the covering radius of ternary extremal self-dual codes[J]. Designs, Codes and Crytography, 2004, 33(2): 149-158.

[2]Gerzson K, Patric R.J. O. Further results on the covering radius of small codes[J]. Discrete Mathematics, 2007, 307(26): 69-77.

[3]Gerzson K. The covering radius of extreme binary 2-surjective codes[J]. Designs, Codes and Crytography, 2008, 46(2): 191-198.

[4]姜宇鵬,鄧映蒲,潘彥斌. 二維格的覆蓋半徑[J]. 系統(tǒng)科學(xué)與數(shù)學(xué), 2012, 32(7): 908-914.

[5]Aoki T, Gaborit P, Harada M,et al. On the covering radius of Z4-codes and their lattices[J]. IEEE Trans Inform Theory, 1999,45(6): 2162-2168.

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

[7]Zhu Shi-xin, Wang Yu, Shi Min-jia. Some results on cyclic codes over F2+vF2[J], IEEE Trans Inform Theory, 2010, 56: 1680-1684.

[8]施敏加,朱士信,李平. 環(huán)F2+vF2上線性碼的MacWilliams恒等式[J]. 計(jì)算機(jī)應(yīng)用研究,2008, 25(4): 1134-1136.

[9]張濤,朱士信. 環(huán)F2+vF2上的二次剩余碼[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2011, 34(8): 1268-1271.

[10]Qian Jian-fa. Quantum codes from cyclic codes overF2+vF2[J]. Journal of Information and Computational Science, 2013, 10(6): 1715-1722.

[11]Dougherty S T, Gaborit P,. Harada M and Sole P. Type IV self-codes over rings[J]. IEEE Trans Inform Theory, 1999, 45(7): 2345-2360.

[12]Delsarte P. Four fundamental parameters of a code and their combinatorial significance[J]. Inform Contr, 1973,23(2): 407-438.

Covering Radius of Codes over Ring F2+vF2

HUANGDe-wei

(Dept. of Appl. Math. , Hefei University of Technology, Hefei 230009, China)

Abstract:Through the study of the structure of codes over ring F2+vF2, two binary codes was defined. By means of the Gray map, one conclusion on the covering radius of codes over ring F2+vF2for the Lee distance was obtained. We study the covering radius of dual codes over ring F2+vF2. Several upper and lower bounds on the covering radius were given.

Key words:Gray map; Cartesian product; covering radius; binary code; Lee distance

[收稿日期]2014-04-06

[中圖分類號(hào)]O212.7

[文獻(xiàn)標(biāo)識(shí)碼]C

[文章編號(hào)]1672-1454(2015)02-0093-04