最优常维码界的一个注记

廖群英, 朱 娟

(1. 伊犁师范学院 数学与统计学院, 新疆 伊宁 835000; 2. 四川师范大学 数学与软件科学学院, 四川 成都 610066)

1 引言及主要结果

设q为素数的方幂,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]在研究随机网络编码时引进了算子信道的概念.他们同时也定义了常维码,并说明了此类码可以用来纠正或检验信息在算子信道传输中出现的错误.

子空间A与B之间的维数距离定义如下

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元子集,其最小维数距离D定义为

对任意正整数k≤n,记P(W,k)为W的全部k维子空间的集合.对任意m,0≤m≤n以及q≥2,

表示q元二项式系数,即高斯二项式系数[2].熟知,

一个q元(n,M,2δ,k)或(n,M,2δ,k)q常维码定义为P(W,k)的一个M元子集,其最小维数距离为δ.由(1)式,维码中任意2个码字之间的维数距离必为偶数并且1≤δ≤k.一个(n,M,≥2δ,k)q常维码即为P(W,k)的一个最小维数距离至少为2δ的M元子集.任意给定n,k,δ以及q,记Aq[n,2δ,k]表示参数为(n,M,≥2δ,k)q的常维码所含码字个数M的最大值.如果M=Aq[n,2δ,k],则称常维码(n,M,≥2δ,k)q为最优常维码.常维码的一个主要研究问题即是确定Aq[n,2δ,k],并且找出相应的最优常维码.

不存在满足汉明界的最优完全常维码[3-4].在2003年,文献[5]给出了线性认证码的一个上界,等价于给出了常维码的一个界.

命题1.1[5](Wang-Xing-Safavi-Naini界) 对任意最优常维码Aq[n,2δ,k],

随后,文献[6]在2009年证明了Steiner结构即为达到Wang-Xing-Safavi-Naini界的最优常维码,并且证明了常维码达到Wang-Xing-Safavi-Naini界当且仅当其为某类Steiner结构.事实上,早在2002年,M. Schwartz等[3]构造了Steiner结构并证明了如下命题:

命题1.2对任意正整数k和l,

最近,T. Etzion等[7]将文献[2,7-8]中的主要结果推广到k不能整除n的情形.

命题1.3[7]设n≡r(modk),则对任意素数方幂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)码.本文进一步讨论最优常维码的上界问题.通过改进文献[7]中常维码的构造方法,给出了某些特殊类型常维码的界.进而证明了不存在同时达到Wang-Xing-Safavi- Naini界和最大距离可分界的最优常维码.事实上,本文证明了如下主要结果:

定理1.4设n≡r(modk),0≤r≤k-1,则对任意素数方幂q,均有

以及

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

推论1.5对任意正整数n和k,

定理1.6对任意正整数n和k,

定理1.7不存在最优常维码Aq[n,d≥2σ,k],同时达到Wang-Xing-Safavi-Naini界和最大距离可分界,即

2 主要结果的证明

为证明主要结果,需要如下引理.

引理2.1[7]设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)

现在考虑常维码

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

的最小维数距离δ.

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

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

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

再由维数距离(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∈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.

再由γ的假设易知:1、γ、…、γk-1是Fq-线性无关的,因此上式表明

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)

现在来考察子空间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线性无关的,并且β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)式以及常维码的维数距离(1)式,可知δ=1并且

故

(II) 设M定义同(I).对∀i=0,1,…,t-1以及j=0,1,…,qm-2,令

以及

因此

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

现在考察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,并且

因此

由此给出文献[7]中定理11,即本文中命题1.3的另一个证明.

定理1.6的证明对于k|n,由命题1.3可以得到

(13)

现在假设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的假设矛盾.

所以达到Wang-Xing-Safavi-Naini界的最优常维码不存在,从而定理1.7成立.

致谢四川师范大学科研基金重点培育项目(13ZDL06)对本文给予了资助，谨致谢意.

[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.