您好,欢迎来到年旅网。
搜索
您的当前位置:首页自对偶码的构造

自对偶码的构造

来源:年旅网
2017年12月 Dec.2017 应用敞 计笄数学学报 Communication on Applied Mathematics and Computation 第31卷第4期 、,o1.3l No.4 DOI 10.3969/j.issn.1006—6330.2017.04.004 自对偶码的构造 童宏玺, 祝丽涛 (上海大学理学院,上海200444) 摘要 自对偶码是一类非常重要的线性码,构造这类码的方法非常多,文中将给出一种新的 构造方法.通过这种构造方法,可以得到许多参数很好的自对偶码. 关键词 自对偶码;自对偶基;代数几何码;迹映射;线性码 2010数学分类号 11T71;94B05;14G50 中图分类号0236.2 文献标志码 A 文章编号 1006—6330(2017)04.0462.09 Construction of self-dual codes TONG Hongxi,ZHU Litao (College of Sciences,Shanghai University,Shanghai 200444,China) Abstract Self-dual codes are an important class of linear codes.There are many constructions of self-dual codes.In this paper.we give a new construction of self- dual codes.It turns out that many new good self-dual codes with large code length are obtained from the construction. Key words self-dual code;self-dual base;algebraic geometry code;trace map; linear code 2010 Mathematics Subject Classification llT71;94B05;14G50 Chinese Library Classification O236.2 0 引 言 C 是码长为扎,维数为 ,汉明距离为d的一个线性码,记为 k,c习 C上={c I C・Cl=0,Vc1∈c}, (1) 式中, “・”为点积, 上称为 的对偶码.若C上=C,则称 为自对偶码.存在长度 为77,的自对偶码,则显然有2 I佗. 自对偶码是一类非常重要的线性码【1】.它的构造非常重要,并已经得到了一些好的构 造方法.Gulliver ̄Harada[ ]和Zhang[。]通过循环矩阵来研究自对偶码的构造.Huffman[41 收稿日期2015—03—16; 修订日期2015.06.12 基金项目国家自然科学基金资助项目(11201288) 通信作者童宏玺,研究方向为代数编码.E mail:tonghxQshu.edu.cn 第4期 童宏玺,等:自对偶码的构造 利用自对偶码的自同构给出了构造自对偶码的方法,许多学者[5-n】已经用这种方法构造 出了许多好的自对偶码.代数几何码是一类非常重要的线性码,很多好的线性码都是代 数几何码,例如,在文献[13]中,Voss和Hcholdt得到了一族有Tsf ̄man—Vl ̄dut—Zink界 的代数几何码,文献[14】中也给出了许多好的代数几何码,如Hermitian码. 本文共分为三个部分.第一部分给出了有关代数几何码和自对偶码的一些结论,可 参考文献【14】和[1 5].第二部分将给出自对偶码的构造方法,并由此得到一些参数非常好 的自对偶码.第三部分将对本文作一个总结. 1 预备知识 首先,给出本文用到的一些相关概念和结论[14-15】. Fqm表示 的m次扩域.n表示从 m到Fq的迹映射,设{e ,…,e )是Fqm在Fq 上的一组基,如果对任意的 ,J:1,…,m,均有 ,= 那么就称{e ,…,e )为 m在 上的一组自对偶基. 引理1[15J 在 上存在自对偶基当且仅当q为偶数或q,m都为奇数. 由引理1,当q为2的方幂时,F9m在 上存在一组自对偶基. 下面介绍代数几何码的一些相关概念和结论【14]. F/Fq是亏格为g的代数函数域,P1,…, 是F/Fq中次数为1的互不相同的位, D:/'1+…+ ,G是 的一个除子,满足 supp G n supp D= 定义1【14】关于除子D和G的代数几何码CL(D,G)定义为 CL(D,G):={( (P1),…, ( ))IX∈ (G)) 定理1[14]CL(D,G)是一个[礼,k,d]码,其中参数 k=dimG—dim(G—D),d≥钆一deg G. . 定理2【 ]设叩为一Well微分, ( )=一1且犯(1)=1,i=1,…,rt,则 CL(D,G)上=CL(D,G),H=:D—G十(叩). 推论1[14】假设卵为一Weil微分,且(叼)=2G—D,町 (D):l,其中i=1,…,礼, 则CL ,G)是自对偶码. 在构造代数几何码时,代数函数域的选择非常重要,下面介绍一些代数函数域. 应脬棼 乒多计并数学学报 第31卷 ,定理3设q为素数P的方幂且满足q=P ,函数域F=Fq ( , ), ,Y满足Ys+ : 其中s=P 且s I q,t f(q+1),且当P=2,m』2h或当P为奇数且m Jh时,有以下结论 (a)F/ 。的亏格是g=(8—1)( 一1)/2. (b)极点 ∈ 。(。) 成立. 有唯一的扩张 ∈PF,x(y)的极除子是 )o。=sQ。。( )。。=tQ。。) (c)令r≥0,则 8—1,si+tj≤r. 构成了空间L(rQ。o)在 。上的一组基,其中0≤i,0≤J≤ (d)对于所有的 ∈ 。,下面两种情况中有一种成立: (i)方程Y。+Y=a 在 。中有8个不相同的根; (ii)方程Y。+Y= 在 。中无根. 在(i)中,对于每个满足 + =OL 的 ,存在唯一的P0卢∈PF满足 , 』 且 (Pn,卢)= ,因此P0在F/Fq (。)中有s个不同的扩张且每个次数为1. 在(ii)中,F中所有P0的扩张次数都大于1. ,证明只要证明定理中的函数域是有理函数域 。(X)的简单阿贝尔 扩张[14]即可. 考虑方程 +T=0在F0。中的根情况. 设 是 +T=0的一个非零根,则 _。:一1 2(s一1):1 当P=2时,m I 2h,则 (s一1)I(q 一1). 当P为奇数时,m I h,则 2(8—1)l(q。一1). 由此,方程T。+T:0的所有根都在Fq 中,且有t I(q+1),gcd(t,P)=1,所以定理 中的函数域是有理函数域 。( )的简单阿贝尔p一扩张,定理得证. 事实上,若s=q且t:q+1,则F/ 就是Hermitian域. 定义2[14】若亏格为g的代数函数域F/ 的有理位个数 N=q+1+2gq /。, 则称函数域 为极大函数域. 例如,Hermitian函数域是极大函数域. 命题1【 】极大函数域的子域仍是极大函数域. 第4期 童宏玺,等:自对偶码的构造 465 定理4令g为素数P的方幂,q=P ,函数域F= 。(X, ), ,Y满足Y。+Y= , 其中s=P 且s I g,t l(q+1),且当P:2,m l h或当P为奇数时,h=Im,f为奇数. F/F0。是Hermitian函数域的子域,且F/Fq。是极大函数域.特别地,当t=q+1时, F/ 。的有理位个数N=q2s+1, 证明显然,F/F日。满足定理3的条件.考虑Fq 上的Hermitian函数H=Fq。(Xl,Y1), 其中 }+Y1: { .令h=lm,P为奇数,f为奇数,则 l I= m 一 所以Y。+Y=X ,F H且F是极大函数域. 显然,当t=q+1时,N=q2s十1. m 2 一种新的构造自对偶码的方法 m 设函数域F/F0。满足定理4的条件. 一 定义3 r∈Z,定义 + + :=CL(D,rQ。。), 式中,D:= ∑ 口。+ =a ,p是F/Fq 中所有次数为1的位(除了Qoo)的和. 当r>g。+2gq+(2g一2)时, dim =dim(rQ。。)一dim(rQ ̄一D) =r+1一g一(r~q +1一g一2gq) =q2+2gq. 命题2当t:q+1且0≤r≤q。+2gq+(2g一2)时, 2s+(s一1)q一2一r. 的自对偶码为 = 证明令 对于所有的 ,p≤D,Z是一素元,且它的主除子为(z):D—q2sQo。.由于dZ= d(xq。一 )=一dx,dZ的除子( )=(如)=(29—2)Q。o=((s一1)q一2)Qoo,所以 =cn(n,rQ。。) ( ( ,D—rQoo+(dZ)一( )) CL(D,(q28+(8—1)q一2一r)Q。。) ===cTq2s+(8—1)q一2一r. 应用j蟮? 计笄教学学报 令t=q+1,集合 为Qo。的极点数, =: ≥0 I存在元素 ∈Fit(名)oo=6Qo。). 第31卷 对于r≥0,令 (r):={6∈ I b≤r). 命题3设t--q+1且0≤r≤q2+2gq+(2g一2)=s口 +(s一1)口一2则有以下结论: ,(a) 的维数为 dim : II(r)I, 0≤r≤sq。,  【sq 一Ix(1)l, sq ≤r≤sq +2g一2,式中,l:q2s+fs一1)g一2一r. 对于2g~1<r<sq ,则 dim =r+1一g (b) 的最小距离d满足d≥q28一r. 若0≤r<sq 且?’和sq。一r都是Qo。的极点数,则 证明由 (r)的定义, IX(r)l=dim(rQo。)且当r≥2g一1:(s一1)9—1时, f (r)l=r+1一g. 根据定理3,可得 )={6≤r I b:is+ (口+1),其中i≥0,J≤s一1), 因此 f ( )I:I{( ,歹)∈N×N;i>0,0<J≤s一1,is+ (q+1)≤r)}. (a)对于0≤r≤sq , dimC ̄=dimL(rQ。。)=J-r(r)1. 对于sq ≤?’≤sq +(s一1)q一2,可得 z:=sq。+(s一1)q一2一r’ 因而有0≤f≤(s—1)q一2<s口2,所以 dimC ̄=sq 一dimCz=sq。一I-r(r)1. 第4期 童宏玺,等。自对偶码的构造 467 显然,当2I9—1<r<sq。时, dim =r+1~g (b)d≥sq。一r显然成立.设0≤r<sq ,且r和sq 一r都是Q。。的极点数.下面 证明d=sq。一r. 情形1 r=(s一1)q2.在Fq。中选取i个不同的元素O/l,…,O/t,其中i=(s一1)譬. 元素 有r(:si)个次数为1的不同零点P0, ,其中 :=II( — )∈ (rQ。。) =1 2所对应的码字eVD(Z)的重量为sq 一r,其中eVD(Z)∈ ,因此,d=sq。一r. 情形2 r<(8—1)q。.令r=is+J(q+1),其中i≥0且0≤J≤8—1,因此, i≤q2一譬一1.固定F口中的非零元素7,考虑集合 A={ ∈ z I + ≠ ) 则I A l=q 一(q+1)≥i.在A中选取互不相同的元素OQ,…,OLi,元素Z1有不同的零 位 ,口(≤D),其中 =Ⅱ 一 ) =1 在Fq。中选取J个不同的元素 ,… 使得 88u+p : 考虑集合 因为当 =l,…,J和 =1,…,i时, + = ≠ , 所以Z2含有J(q+1)个零点PQ, (≤D),且它们都是Z1中的不同零点.因此,Z有r个 不同的零点 ,口(≤D),其中, Z:=ZIZ2∈L((is+J(q+1))Qo。): (rQo。) Z所对应的码字eVD(Z)的重量为s口。一r,其中eVD(Z)∈ 468 虚雕棼?雩 计笄数学学报 第3l卷 情形3(8—1)q。< ≤sq .设f是一极点数,其中f=sq。~r,0<f<q ≤(8—1)q . 由情形2可知,在F中存在一个元素 ,使得 的主除子(Z)=D 一2Qoo,其中0≤D ≤ D,degD =f.F中的元素 (: g。一 )的除子(乱):D一(sq2)Qo。,因此 (z--lu)=(D~D )一(sq。一1)Q。。=( —D )一rQ。。 码字eVD(Z)的重量为sq。一7’,其中eVD(Z)∈ . 记f=is+J(q+1)({≥0,0≤J≤s一1),向量乱2:=(Q‘ )( ,鲫 T∈( 。) q。构 成 的生成矩阵,其中 T::.[( , )E Fq。×Fq。I 。+ =OL + } 推论2假设0≤r<sq +2g一2,令f1,f2…,f 为Qoo的极位数,且0:f1<f2< …<Ik≤r,则k×(sq )阶矩阵 是 的生成矩阵,其中 的行向量为 f1j…,U 由命题2可得:若 是自对偶码,则r=譬+ 一1,因此g必为2的方幂. 令q=2,s=2,t=3,由定理3(a),亏格g=(8—1)(t一1)/2=1,由定理4,有理 位个数N=q+1+2gq ̄=9,码长佗=N一1=8,由命题3(b),d≥q2s—r=4,所 以 是F4上的[8,4,d≥4]自对偶码.同理可得下列自对偶码. 令g=4,s=2,t=5,则 7是F16上的[32,16,d≥15]自对偶码. 令q=4,8=4,t=5,则 7是Fi6上的【64,32,d≥27】自对偶码. 令q=8,s=2,t=9,则 7是F64上的[128,64,d≥61】自对偶码. 令q=8,s=8,t=9,则C283是F64上的f512,256,d≥229】自对偶码. 这些较大有限域上的自对偶码的参数都非常好,但有时希望得到小有限域上好的自 对偶码. 设q是2的方幂,令 表示从Fqm到Fq的迹映射,{e1,…,e )是Fqm在Fq上 的一组自对偶基.对于任意的OL E m,在Fq中有 ,…,a 使得 =∑ t. i:1 定义 :Fqm一 , 0=∑ t一( 一,Q ) i--1 设 是 m上的【n,k,明码,定义 (c):={砂(c):( (c1),…, (cn))lVc∈ ) “ 定理5设c是 m上的 ,n/2,d】自对偶码,则 (c)是Fq上的[佗m, ,d,≥d】自 对偶码. 第4期 童宏玺,等:自对偶码的构造 469 证明显然, ( )是 上的[nm,k ,dI≥卅码, :l。gq =l。gq(口 )号= mn 对任意的Ol:(Oll,…,Q )∈C, =( 1,…, )∈C ( ) ( )=∑n( t )=rn(∑ t )= (0)=0, i=1 t=1 因此砂( )是 上的[nm, ,d ≥d]自对偶码. 设{e ,e2)是F16在F4上的一组自对偶基. ̄(C17)是F4上[64,32,d ≥15]自对偶 码.砂( 7)是F4上[128,64,d ≥2 7]自对偶码.类似地,{e ,e ,e§,e 】.是F16在 上一 组自对偶基,可以得到F2上【128,64,d ≥15】自对偶码和F2上[256,128,d ≥27]自对偶 码.可以从 7和 83中得到 上的[256,128,dI≥61】自对偶码和F8上的[1 024,512, ≥ 229].将它们与文献[16】中的线性码进行比较,可知:这些自对偶码都有非常好的参数. 3 结束语 在本文中,我们给出了构造自对偶码的新方法.从F2。 上的一些最大函数域中,可以 得到F2。 上的一些代数几何自对偶码.设m<h且m J h,{el,…,e 2h)是F2。 在 m上 的一组自对偶基,以及由从F2。 到F2m(m≥1)的迹映射n就可以得到F2m(m≥1)上 一些参数比较好的自对偶码. 参考文献 [1]Rains E,Sloane N J A.Self-dual codes[M]//Pless V,Huffman W.Handbook of Coding Theory, Amsterdam/The Netherlands:Elsevier,1998. [2】Gulliver T A,Harada M.Classiifcation of extremal double circulant self-dual codes of lengths 64 to 72【J].Designs,Codes and Cryptography,1998,13:257-269. [3】Zhang S Y.On the nonexistence of extremal self-dual codes[J】.Discrete Applied Mathematics, 1999,91:277-286. 【4]Huffman W C.Decomposing and shortening codes using automorphisms[J】.IEEE Trans In一 ,0册 Theory,1986,32(6):833-836. [5J Betsumiya K,Georgiou S,Gulliver T A,Harada M,Koukouvinos C.On self-dual codes over some prime fields[J】.Discrete Math,2003,262:37-58. [6】Bouyuklieva S.On the automorphism group of a doubly—even(72,36,16)code[J].IEEE Trans Inform Theory,2004,50(3):54 547. [7]Bouyuklieva S.On the automorphisms of order 2 with fixed points for the extremal self-dual codes of length 24 m[J1.Designs,Codes and Cryptography,2002,25:5-13. 【8】Bouyuklieva S,Russeva R,Yankov N.On the structure of binary self-dual codes having an automorphism of order a square of an odd prime【J1.IEEE Trans Inform Theory,2005,51(10): 3678—3686. 【9]Dontcheva R A.On the doub ̄一even self-dual codes of length 96[J].IEEE Trans Inform Theory,2002,48(2):55 ̄561. [10】Dontcheva R A,va43 Zanten A J,Dodunekov S M.Binary self-dual codes with automorphisms of composite order[J].IEEE Trans Inform Theory,2004,5o(2):311-318. 【11]Harada M,Munemasa A.There exists no self-dual[24;12;10]code over F5[J]I Designs,Codes and Cryptography,2009,52:125-127. [12】Yorgova R A.On binary self-dual codes with automorphisms[J】.IEEE Trans Inform Theory, 2008,54(7):3345—3351. 【13】Voss C,H0holdt T.An explicit construction of a sequence of codes attaining the Tsfasman. Vl ̄dut・Zink bound:the first step[J].IEEE Trans Inform Theory,1997,43(1):128—135 【14]Stichtenoth H.Algebraic Function Fields and Codes【M】_Berlin:Springer—Verlag,1993. [15】Lidl R,Niederraiter H.Finite Fields[M].Cambridge:Cambridge University Press,1997. [16】Grassl M.Codes Tables:Bounds on the Parameters of Various Types of Codes[EB/OL]. f2015—01—29].http://www.codetables.de. 

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- oldu.cn 版权所有 浙ICP备2024123271号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务