廖群英, 朱 娟

(1. 伊犁師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院, 新疆 伊寧 835000; 2. 四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院, 四川 成都 610066)

1 引言及主要結(jié)果

設(shè)q為素數(shù)的方冪,Fq為q元有限域,W為Fq上的n維向量空間,P(W)為W的所有子空間的集合.對任意的A,B∈P(W),記

A+B={a+b|a∈A,b∈B},

同時包含A和B的最小子空間.近年來,R. Koetter等[1]在研究隨機(jī)網(wǎng)絡(luò)編碼時引進(jìn)了算子信道的概念.他們同時也定義了常維碼,并說明了此類碼可以用來糾正或檢驗信息在算子信道傳輸中出現(xiàn)的錯誤.

子空間A與B之間的維數(shù)距離定義如下

d(A,B)=dim(A+B)-dim(A∩B)=

dim(A)+dim(B)-2dim(A∩B).

(1)

由此定義了空間P(W)上的一個度量[1].一個q元(n,M,D)或者(n,M,D)q碼C即為P(W)中一個M元子集,其最小維數(shù)距離D定義為

對任意正整數(shù)k≤n,記P(W,k)為W的全部k維子空間的集合.對任意m,0≤m≤n以及q≥2,

表示q元二項式系數(shù),即高斯二項式系數(shù)[2].熟知,

一個q元(n,M,2δ,k)或(n,M,2δ,k)q常維碼定義為P(W,k)的一個M元子集,其最小維數(shù)距離為δ.由(1)式,維碼中任意2個碼字之間的維數(shù)距離必為偶數(shù)并且1≤δ≤k.一個(n,M,≥2δ,k)q常維碼即為P(W,k)的一個最小維數(shù)距離至少為2δ的M元子集.任意給定n,k,δ以及q,記Aq[n,2δ,k]表示參數(shù)為(n,M,≥2δ,k)q的常維碼所含碼字個數(shù)M的最大值.如果M=Aq[n,2δ,k],則稱常維碼(n,M,≥2δ,k)q為最優(yōu)常維碼.常維碼的一個主要研究問題即是確定Aq[n,2δ,k],并且找出相應(yīng)的最優(yōu)常維碼.

不存在滿足漢明界的最優(yōu)完全常維碼[3-4].在2003年,文獻(xiàn)[5]給出了線性認(rèn)證碼的一個上界,等價于給出了常維碼的一個界.

命題1.1[5](Wang-Xing-Safavi-Naini界) 對任意最優(yōu)常維碼Aq[n,2δ,k],

隨后,文獻(xiàn)[6]在2009年證明了Steiner結(jié)構(gòu)即為達(dá)到Wang-Xing-Safavi-Naini界的最優(yōu)常維碼,并且證明了常維碼達(dá)到Wang-Xing-Safavi-Naini界當(dāng)且僅當(dāng)其為某類Steiner結(jié)構(gòu).事實上,早在2002年,M. Schwartz等[3]構(gòu)造了Steiner結(jié)構(gòu)并證明了如下命題:

命題1.2對任意正整數(shù)k和l,

最近,T. Etzion等[7]將文獻(xiàn)[2,7-8]中的主要結(jié)果推廣到k不能整除n的情形.

命題1.3[7]設(shè)n≡r(modk),則對任意素數(shù)方冪q,均有

T. Etzion等[7]同時也將常維碼的概念推廣到C?P(W)的一般子集的情形,即:稱子集C是P(W)中的(n,M,d)碼,如果|C|=M并且對所有的U,V∈C,d(U,V)≥d,其中

d(U,V)=dimU+dimV-2dim(U∩V).

特別地,如果存在k,使碼C=(n,M,d)包含于P(W,k),則稱C為(n,M,d,k)碼.本文進(jìn)一步討論最優(yōu)常維碼的上界問題.通過改進(jìn)文獻(xiàn)[7]中常維碼的構(gòu)造方法,給出了某些特殊類型常維碼的界.進(jìn)而證明了不存在同時達(dá)到Wang-Xing-Safavi- Naini界和最大距離可分界的最優(yōu)常維碼.事實上,本文證明了如下主要結(jié)果:

定理1.4設(shè)n≡r(modk),0≤r≤k-1,則對任意素數(shù)方冪q,均有

以及

由命題1.1以及定理1.4,易得:

推論1.5對任意正整數(shù)n和k,

定理1.6對任意正整數(shù)n和k,

定理1.7不存在最優(yōu)常維碼Aq[n,d≥2σ,k],同時達(dá)到Wang-Xing-Safavi-Naini界和最大距離可分界,即

2 主要結(jié)果的證明

為證明主要結(jié)果,需要如下引理.

引理2.1[7]設(shè)n≡r(modk),0

(I) 對?i∈{0,1,…,t-1}以及j∈{0,1,…,qm-2},令

M=〈(0,β0),(0,β1),…,(0,βk-1)〉=

(2)

Ui=〈(αi,0),(αiγ,0),…,(αiγk-1,0)〉=

以及

Vi,j=〈(αiγ0,βj),(αiγ1,βj),…,(αiγk-1,βj)〉=

易知

dimFqM=dimFqUi=dimFqVi,j=k,

0≤i≤t-1, 0≤j≤qm-2.

(5)

現(xiàn)在考慮常維碼

C=M∪(∪iUi)∪(∪i,jVi,j)=[n,δ,k]q(6)

的最小維數(shù)距離δ.

由(2)～(5)式以及α、β、γ的假設(shè),易知

M∩Ui=M∩Vi,j={0},

0≤i≤t-1, 0≤j≤qm-2.

再由維數(shù)距離(1)式,dimFqM∩Ui=dimFqM∩Vi,j=0.于是由(5)式可得

d(M,Ui)=d(M,Vi,j)=2k-0=2k,

0≤i≤t-1, 0≤j≤qm-2.

(7)

Ui1∩Ui2={0}, 0≤i1≠i2≤t-1.

由(1)和(5)式

d(Ui1,Ui2)=2k-0=2k,

0≤i1≠i2≤t-1.

(8)

因此,對?i∈{0,1,…,t-1}以及j∈{0,1,…,qm-2},令A(yù)∈Ui∩Vi,j,則存在a0,a1,…,ak-1∈Fq以及b0,b1,…,bk-1∈Fq,使得

即

b0βj+b1βj+…+bk-1βj=0,

并且

a0αiγ0+…+ak-1αiγk-1=b0αiγ0+…+bk-1αiγk-1.

再由γ的假設(shè)易知:1、γ、…、γk-1是Fq-線性無關(guān)的,因此上式表明

b0+b1+…+bk-1=0,

并且

al=bl, 0≤l≤k-1,

即

于是

dimFq(Ui∩Vi,j)=k-1,

i=0,1,…,t-1,j=0,1,…,qm-2.

故由(1)和(5)式可得

d(Ui,Vi,j)=2k-2(k-1)=2,

i=0,1,…,t-1,j=0,1,…,qm-2.

(9)

現(xiàn)在來考察子空間Vi,j1∩Vi,j2,0≤i≤t-1,0≤j1≠j2≤qm-2.對?A∈Vi,j1∩Vi,j2,?al,bl∈Fq,0≤l≤k-1,使得

這表明

并且

由于α、αγ、…、αγk-1是Fq線性無關(guān)的,并且βj1≠βj2(ji≠j2).于是

從而

故

dimFq(Vi,j1∩Vi,j2)=k-1,

0≤i≤t-1, 0≤j1≠j2≤qm-2.

因此由(1)和(5)式可得

d(Vi,j1,Vi,j2)=2k-2(k-1)=2,

0≤i≤t-1, 0≤j1≠j2≤qm-2.

(10)

因此由(5)～(10)式以及常維碼的維數(shù)距離(1)式,可知δ=1并且

故

(II) 設(shè)M定義同(I).對?i=0,1,…,t-1以及j=0,1,…,qm-2,令

以及

因此

0≤i≤t-1, 0≤j≤qm-2.

現(xiàn)在考察Fq上的常維碼

類似于(I)中證明可得

0≤i,i1≠i2≤t-1,j=0,1,…,qm-2,

以及對?i1,i2∈{0,1,…,t-1},j1,j2∈{0,1,…,qm-2},其中,(i1-i2,j1-j2)≠(0,0),均有

于是由(1)式可知

(11)

即

并且

這表明

al=bl(0≤l≤t-1),

并且

注意到β為Fqm中的本原元素,故

a0=…=at-1=at+1=…=ak-1=0,

i≡j+t(modqm-1), 0≤t≤k-1.

從而存在i=0,1,…,t-1;j=0,1,…,qm-2,滿足

即

(12)

于是由(11)和(12)式,C*為Fq上的[n,2(k-1),k]q常維碼,并且

因此

這就完成了定理1.4的證明.

=〈(αi,0),(αi+1γ,0),…,(αi+k-1γk-1,0)〉=

以及

類似于定理1.4的(I)中的證明,可知C′是Fq上的常維碼[n,2k,k]q,并且

因此

由此給出文獻(xiàn)[7]中定理11,即本文中命題1.3的另一個證明.

定理1.6的證明對于k|n,由命題1.3可以得到

(13)

現(xiàn)在假設(shè)n≡r(modk)(0≤r≤k-1).注意到

如果q=k=2且r=1,則

且

(15)

故由命題1.1～1.3以及(13)～(15)式可知定理1.6成立.

定理1.7的證明否則,采用反證法.由命題1.1可知

即

因此

注意到d≤k,從而

這與q≥2的假設(shè)矛盾.

所以達(dá)到Wang-Xing-Safavi-Naini界的最優(yōu)常維碼不存在,從而定理1.7成立.

致謝四川師范大學(xué)科研基金重點(diǎn)培育項目(13ZDL06)對本文給予了資助，謹(jǐn)致謝意.

[1] Koetter R, Kschischang F R. Coding for errors and erasures in random network coding[C]//Proc 2007 IEEE Int Sympos on Information Theory (ISIT’2007). Nice,2007:791-795.

[2] MacWilliams F J, SloaneN J A. The Theory of Error-Correcting Codes[M]. Amsterdam:North-Holland,1981.

[3] Schwartz M, Etzion T. Codes and anticodes in the Grassman graph[J]. J Combin Theory,2002,A97(1):27-42.

[4] Etzion T. Perfect byte-correcting codes[J]. IEEE Trans Inform Theory,1998,44:3140-3146.

[5] Wang H X, Xing C P, Safavi-Naini R. Linear authentication codes: bounds and constructions[J]. IEEE Trans Inform Theory,2003,49(4):866-872.

[6] Xiao S, Fu F W. Johnson type bounds on constant dimension codes[J]. Des Codes Cryptogr,2009,50:163-172.

[7] Etzion T, Vardy A. Error-correcting codes in projective space[J]. IEEE Trans Inform Theory,2011,57(2):1165-1173.

[8] Bu T. Partitions of a vector space[J]. Discrete Math,1980,31:79-83.

[9] Ho T, Koetter R, Médad M, et al. The benefits of coding over routing in a randomized setting[C]//Proceedings of the IEEE International Symposium on Information Theory. Yokohama,2003:442.

[10] Ho T, Koetter R, Médad M, et al. A random linear network coding approach to multicast[J]. IEEE Trans Inform Theory,2006,52:4413-4430.

[11] Tonchev V D. Codes and designs[C]//Pless V C, Huffman W C. Handbook of Coding Theory. Amsterdam:North-Holland,1998.