最大距离可分码的上界

最大距离可分码的上界 第17卷第3期 2011年6月 上海大学(自然科学版) JOURNALOFSHANGHAIUNIVERSITY(NATURALSCIENCE) Vol_17No.3 Jun.2011 doi:10.3969/j.issn.1007-2861.2011.03.015 最大距离可分码的上界 杨建生,张运英,王德秀 (1.上海大学理学院,上海200444;2.上海市亭新中学,上海201505) 摘要:Mq()表示g元(,q,d)最大距离可分 (iTlaximHmdistanceseparable,MDs)码的最大码长,其中g,为参数 讨论()的性质,得到()的新的上界. 关键词:最大距离可分码;汉明距离;码的等价性;重量分割 中图分类号:0157.4文献标志码:A文章编 号:1007-2861(2011)03-0289-04 UpperBoundsofMaximumDistanceSeparableCodes YANGJian-sheng,ZHANGYun—ying,WANGDe—xiu (1.CollegeofSciences,ShanghaiUniversity,Shanghai200444,China; 2.ShanghaiTinxinMiddleSchool,Shanghai201505,China) Abstract:LetMq()bethemaximumlengthofq-ary(n,q,d)maximumdistance separable(MDS) codeswithparametersqandk.PropertiesofMq(k)arestudied,andsomenewu pperboundsofMq(k) areobtained. Keywords:maximumdistanceseparable(MDS)codes;Hammingdistance;codesequivalence;weight distribution 设g,,k为整数,且凡?k,A={0,1,2,…,q一 1}(模q)为加法群.(,q,d)表示A上含有q个码 字且最小汉明距离为d的码.如果d=n—k+1,则 称其为A上最大距离可分码,即MDS码.MDS码是 组合数学研究的重要内容,Macwilliams等…认为: MDS码是编码理论中最令人着迷的一章内容. MDS码一般分为线性和非线性.由于线性MDS 码具有良好的代数结构与几何结构,因此,可以借助 线性代数与有限几何的方法进行研究,其中特别引 人注目的是”编码理论中的主猜想”的研究. 1符号说明及MDS码的基本结果 设A为域,m.(k)表示A上的线性MDS码(n, q,—k+1)的最大码长,即m()=max{nI存在A 上(n,g,n—k+1)MDS码},则关于m(k)的”编码 理论主猜想”为 = :…为偶 由于此猜想在编码理论与有限几何的研究中具 有重要意义,因此,关于m.(k)的研究十分丰富. 收稿日期:2009—12-09 基金项目:上海市重点学科建设资助项目($30104) 通信作者:杨建生(1963,),男,副教授,博士,研究方向为编码理论,图 论.E-mail:yjsyjs@staff.shu.edu.all 上海大学(自然科学版)第17卷 对于非线性MDS码,由于其缺乏良好的代数与 几何结构,因此,很难找到系统的方法进行研究.从 组合学角度考虑,非线性码的研究价值在于其应该 具有比线性码更好的纠错能力.因此,对于非线性 MDS码,研究人员提出了类似线性MDS码的问题, 即在参数k确定的前提下,(/7,,q,n—k+1)MDS码 的最大码长(k)具有什么性质?然而令人遗憾的 是,研究M.(后)的难度远大于研究m.().迄今为 止,关于()的研究十分零散,并且主要采用 有限几何的方法,其中有关Mq(k)的研究结果可概 括为定理1和定理2. 定理1(1)设?3,q>2,如果存在(q+ k一1,q,q)MDS码,则4整除q; (2)设k>3,q>2,如果存在(q+k一1,q,q) MDS码,则36整除q. 定理2H(1)对于(n,q,d)MDS码,如果36 不整除q,且k/>4,则n?q+一3; (2)如果q>2,且q;2(rood4),则(g+1,q, q一1)MDS码不存在. 由于MDS码缩短后仍为MDS码,因此,有如下 引理: 弓I理1M.(k)?.(k一1)+1. 本研究利用MDS码的分割重量计数子 (partitionweightenumerator,PWE)和组合学方法研 究M(k),得到了.(k)一些新的上界.特别地,得 到了M(q一1)?g+1(q为奇数),(q一1)?g+2 (q4(mod6)),M.(q一2)?q+1(q;4(rood6)), (k)?g+k一3(q=36(mod180),且kI>6). 为了讨论方便,下面引入一些符号和基本结果. (1)对于任意一个=(otl,o/2,…,o/)?A”,定 义oz的支撑集为Supp()={iI?0,1?i?n},其 集为Supp()={I=0,1??n}.如果ot?A”, 则ot的汉明重量为w(ot)=lSupp(ot)1.如果oz,? ,则ot,/3的汉明距离为d(ot,)=(一卢)= lSupp(ot一)I. (2)设C和D为A上2个长度为n的码,如果 C与D等价,则C和D具有相同的汉明距离.如果 c.?A,贝0D=c.+C={c0+l?C}与c等价,因 此,总可以假设码C包含零码字0=(0,0,…,0). (3)对于上的(n,q,d)MDS码,其重量计数 子?为 J—d, E():(q—1)(1?(一1)j(_)g一1,(1) 式中,w?d.由文献[9]可知,式(1)不仅对线性的 MDS码成立,对含有零码字的一般MDS码也成立. 文献[10]引入了MDS码的分割重量计数子 (PWE).设N={1,2,…,n}.若?,/v:,…,为? p 的子集,且n=0(i?),N=N,则称?., ?2,…,?.为?的一个P分割,记为F(N,N2,…, ?.),简写为厂.对于?A,若w.=NnSupp(),则 称()=(w.,w,…,w)为关于分割F(N., ?2,…,)的分割重量.给定A上长度为n的码C, 则码C关于分割,1的分割重量计数子定义为 (,w2,…,)=l{c?CI(c)=(,,…,) 关于分割重量计数子,有如下定理成立. 定理3ll..如果(n,q,d)MDS码C含有零码 字,_厂(?,,…,)为{1,2,…,n}的P分割,则 E,,,…,=Ec 兰二,c2, 式中,=?w,E()=l{c?CI(c)=}l,=,l l?l(i=1,2,…,P). 文献[10]在定理3的证明中假设A为域,但其 证明与4是否为域无关,也与MDS码是否为线性码 无关,只用到该MDS码含有零码字这个条件.因此, 该定理对所有包含零码字的MDS码都成立. 2MDS码新的上界 本节中,设A=A{0}.若c为(n,q,d)MDS 码,对(0,b)?A,定义C={c=(?l,2,…,口)? CI口1=口,n2=b,且(c)=d}. 定理4设q为奇数,则M(q一1)?q+1. 证明采用反证法. 假设c为一个包含零码字的(q+2,q,4)(q 为奇数)MDS码.考虑分割F=N.U,其中N= {1,2}.由定理3,得 E,(2,2)=E(4) q+2 4 由于,lA1=(q一1),因此,存在(?,b)?A,使得 ICo, b l?等等=号. 不失一般性,可以假设0=1,b=1. 第3期杨建生,等:最大距离可分码的上界29l 4(i=1,2,…,),由此得l~1Supp(a)l2t+2?那 lClIll=, 1d:.j}+1,l:g一2. = 兰4) (g.+一k3-4)(g一). : 兰4)4) q一1一q一1 不失一般性,可假设口=1,b=1.下面证明lC. l= . 魁 令={?ClIlIj?S—upp(),i=1, %1,J2,”“,Jk-3的个数为(g+j}k一-34),且c中的任意元素 都包含在(二)个这样的集合里,则存在, … 3I4,… ?’ 假设Ot,卢?B3_4.….— l,且?卢.若i?Supp(O/)n Supp(卢)(??g+一2),习么{1,2,…,k一1,i}c Supp(一卢),贝0d(,)?(q+k一2)一后=q一2?B3_4_I.一1,且OL?卢. 若i?Supp(OL)n Supp(f1)(k?i?q+k一2),男Ij么{1,2,3,…,k一1, i}cSupp(o/)nSupp().由w()=w()=k+1, 知d(,卢)?k<d,矛盾.故Supp(o/)nSupp(卢)= {1,2,…,k一1}.令1,2,…,?B3-4_...?,且两两 不相等,有Supp(o/)f-)Supp()={1,2,3,…,k一 1}(i).又因为w()=k+1(1,2,…,t),所以 lU. Supp(OL)l=2t+k一1,得至02t+k一1?q+k一 2,即,?.又因为g为偶数,所以,?,与 l,.4j一.l>矛盾. 因此,当f=k或f=q一2时,有 k>16). 证明如果k=6,由定理5知Mq(6)?q+3 (g---36(mod180)).结合引理1,有.()?g+k一 3(q=36(mod180),且k>16). 参考文献: [2] [3] [4] [5] k1,[6](一)!’lJ 则?专必须为整数.所以当 k>14,如果q为偶数,且(一1)!不整除(q+k一4)… (q+1)q(q一2),贝0M.(k)?g+k一3,Mq(q一2)? q+k一3. 通过定理5,可以得到如下推论. 推论1M.(q一2)?g+1(q一4(mod6)). 推论2Mq(q一2)?q+3(q6或26(mod 30)). 推论3M.(q一2)?q+5(q8或36(mod 42)). 推论4M(q一1)?g+2(q---4(mod6)). 证明由引理1,知.(k)?Mq(k一1)+1.结 合推论1,有.(q一1)?Mq(g一2)+1=q+2(q 4(mod6)). 推论5.(k)?g+k一3(q---36(rnod180),且 [7] [8] [9] [10] MACWILLIAMSFJ,SLOANENJA.Thetheoryoferror— correctingcodes[M].Amsterdam:North—Holland PublishingCo,1977:317—329. HIRSCHFELDJWP.ThemainconjectureforMDS codes,lecturenotesincomputerscience[c]? Proceedingsofthe5thIMAConferenceonCryptography andCoding.1995:44—52. ALDERSONTL.OnMDScodesandBruen.Silverman codes[D].Ontario:UniversityofWesternOntario, 2002. ALDERSONTL.ExtendingMDScodes[J].Annalsof Combinatorics,2005,9:125—135. ALDERSONTL,BRUENAA.CodesfromcubicCHIVES andtheirextensions[J].TheElectronicJournalof Combinatorics,2008,15(1):R42. BRUCKRH,RYSERHJ.Thenonexistenceofcertain finiteprojectiveplanes[J].CanadaJMath,1949(1): 88-93. BRUENAA,SILVERMANR.Onthenonexistenceof certainMDScodesandprojectiveplanes[J].MathZ, 175. 1983.183:171— SILVERMANR.Ametrizationforpower—setswith applicationstocombinatorialanalysis[J].CanadJ Math,1960,12:58—176. TOLHUIZENLMGM.Onmaximumdistanceseparable codesoveralphabetsofarbitrarysize[c]?Proceedings ofthe1994IEEEInternationalSymposiumonInformation Theory.1994:431. EL—KHAMYM,MCELIECERJ.Thepartitionweight enumeratorofMDScodesanditsapplications[c]? Proceedingsofthe2005InternationalSymposiumon InformationTheory.2005:926-930. (编辑:孟庆勋) 4一 一3一 g一