有13-(4,m)型的二元自对偶码(m=2,4,6)

王 荣

(山西财经大学应用数学学院,太原030031)

有13-(4,m)型的二元自对偶码(m=2,4,6)

王 荣

(山西财经大学应用数学学院,太原030031)

论述纠错码中的二元自对偶码,把码字看成二元域GF(2n)上的多项式,并分解因式。根据码长较短的二元自对偶码,构造出长度较长的二元自对偶码,并给出生成矩阵。运用2个码等价的类型,得到在等价下可能的码的分类情况,运行Matlab程序,证明具有13-(4,2)型自同构的二元自对偶码［54,27,10］只有8个等价的自对偶码。应用该方法,得到二元自对偶码［56,28,10］的生成矩阵。运行程序证明在等价情况下,存在16个有13-(4,4)型的自对偶码,而有13-(4,6)型的二元自对偶码［58,29,10］在等价下只有10种码。

二元自对偶码;自同构;生成矩阵;等价;循环矩阵;分类

1 概述

二元自对偶码在信道码中占有非常重要的地位,它是一种纠错码,把每一个信息转化为0和1的序列,然后对这个序列进行编码来防止它们在信道传输时发生错误。

设σ是一个n阶置换,对线性码C的任一个码字u=(u1,u2,…,un),令 uσ=(uσ(1),uσ(2),…,uσ(n))。对GF(2)n上的一个线性码C,Cσ={uσ|u∈C},如果C=Cσ,则称σ是线性码C的一个自同构,C的全体自同构的集合构成n阶对称群Sn的一个子群,称为自同构群。设p是素数,如果σ有c个p循环和f= n-cp个固定点,则称σ是p-(c,f)型的。

线性码的构造和分类是编码理论的基本内容,自对偶码在编码理论中具有重要作用。对码长不超过32的自对偶码,其构造和分类已经得到完全解决［3-4］。但对码长较长的二元自对偶码研究得还很少。文献［5］证明了对二元自对偶码［48,24,10］,有3-(16,0)型的线性码在等价情况只有264种［6］。文献［7］证明了对有7阶自同构的二元极值码［42, 21,8］,在等价情况下只有29种［8］。本文对码长为54,56和58的二元自对偶码有特殊型时进行研究。

2 有13-(4,2)型的二元自对偶码

对长度为54的二元自对偶码进行讨论,得到p-(c,f)的可能取值为:3-(18,0),3-(14,12),3-(12,18),3-(10,24),5-(10,4),7-(7,5),13-(4,2), 17-(3,3),53-(1,1)。现考虑有13-(4,2)型自同构的自对偶码。

2.1 码的生成矩阵

设:

σ=(1,2,…,13)(14,15,…,26)…(40,41,…, 52)(53)(54)

Ωi=(13(i-1)+1,13(i-1)+2,…,13i)

Ω4+f=(52+f),i=1,2,3,4;f=1,2

令Fσ(C)={u∈C|uσ=u},∀u∈C,令¯u是u去掉2个固定点,并用2个0补充所得的码字,Eσ(C)={u∈C|wt(¯u|Ωi)=0(mod2)},(u|Ωi是u在Ωi上的限制),由文献［4］知:C=Fσ(C)⊕Eσ(C)。

对∀u∈Fσ(C),s,l∈Ωi,则有us=ul,(i=1, 2,…,6)。定义映射η:Fσ(C)→F62,(ηu)i=uj,j∈Ωi,i=1,2,…,6。把η(Fσ(C))叫由C导出的收缩线性码。

对∀u∈Eσ(C),令=u|Ωi(看成R的元,i= 1,2,3,4),Eσ(C)*=|u∈Eσ(C)},于是Eσ(C)*是R上的线性码。由Eσ(C)和I1的定义知:Eσ(C)*=。

引理2 具有型p-(c,f)的二元线性码C是自对偶的⇔下列2个条件同时成立［9］。

(1)收缩线性码η(Fσ(C))是一个自对偶码;

(2)Eσ(C)*是关于内积

因此,η(Fσ(C))是一个［6,3］二元自对偶码。由文献［4］知,在等价情况下,该线性码只有一个,其生成矩阵为:

引理3 α(x)=x5+x3+x+1是I1的一个本原元。

证明:e=x+x2+x3+…+x12是I1的一个单位元。由于212-1=32×5×7×13,且

因此α(x)的阶为212-1。证毕。

令β=α(x)65,γ=α(x)63,δ=γ13,则β和γ的阶分别为63和65,βγ的阶为6365=212-1,δ的阶为5。可用βγ来代替上面矩阵中的α(x),得到:

对其进行一系列的矩阵初等变换得:

由于e,δ,δ2,δ3,δ4为(γ5)在(γ)中的陪集代表,δ=1+x4+x10+x12,δ2=1+x7+x8+x11,δ3=1+x2+x5+x6,δ4=1+x+x3+x9。根据引理4的(2),可用(γ5)的一个元素乘Eσ(C)*经变换后的生成矩阵得:

0≤l,t,s≤4,0≤i,j,j3,j4≤62,0≤m≤64。

由于矩阵(1)的2行是正交的,则有:

βi+j3-j-j4和δ-sγm的阶分别是63和65的因子,所以βi+j3-j-j4=δ-sγm=,即βi-j=βj4-j3,γm=δs,故i-j=j4-j3(mod63)。

矩阵的行自身正交,可得:

β=α(x)65=x+x3+x4+x5+x8+x9+x10+x12生成了I1的乘法群的一个阶为63的子群。β的所有幂在表1中列出(βi=xj1+xj2+…+xjr)。

表1 βi=xj1+xj2+…+xjr的幂

经过计算机搜索,只有当i,j3,j,j4满足表2取值时,式(1)～式(3)成立。

因此,i=j4,j=j3。矩阵(1)变成:

0≤l,t,s≤4,i,j如表 2所示。至此得到Eσ(C)*的生成矩阵。Eσ(C)的生成矩阵为:

其中,0表示12×13的零矩阵;U,V和Vi(i=1,2, 3,4)都为12×13循环矩阵,且每个循环矩阵的第一行分别对应于矩阵(5)中的多项式δl,δt,βi,βjδs,βiδs。

表2 i,j3,j,j4的取值

定理1 有13-(4,2)型自同构的二元自对偶码的生成矩阵为:

其中,前3行黑体的0和1分别表示元素全为0和1的1×13行向量。后2行中,U,V和Vi(i=1,2,3, 4)和前2列中的0如前所述,后两列的0代表12×1的列向量。

2.2 码的分类情况

引理4 对2个具有相同型(13-(4,2))的二元自对偶码,如果C′可以通过对C进行下列变换的乘积得到,则C和C′是等价的［9］。

(1)Eσ(C)*中用xt替换x,t∈Z,1≤t≤12;

(2)用xtj乘以Eσ(C)*的第j位,0≤tj≤12,j= 1,2,3,4;

(3)C的前4个循环的置换;

(4)C的后2个固定点的一个置换。

因此,在矩阵(b)中作变换x→x2(［10］),则:

表2中{i,j}取值在M={{1,6},{5,62},{7, 26},{9,45},{11,25},{15,23},{21,42}}。

对(l,t,s,i,j)重复应用6次式(4)中置换,可得:

由于23×9≡9(mod63),运用式(4)可得:

(l,t,s,9,45)→(23l,23t,23s,9,45),交换矩阵的前2列和矩阵的前2行,得到:

由于23×1125(mod 63),2×2142(mod63),运用式(4)和式(6)可得:

令K={1,(1,2)(3,4),(1,3)(2,4),(1,4)(2, 3)},对矩阵的列应用置换(1,2)(3,4),得:

类似的,(1,4)(2,3)所对应的变换是:

K是交错群A4的正规子群,{1,(1,4,3),(1,4, 3)(1,4,3)}是K在A4中的陪集代表［7］。置换(1,4, 3)对应变换:

应用式(4)～式(11)的变换,可把集合{(l,t,s,i, j)|{i,j}∈M,0≤l,t,s≤4,l,t,s不全相等,且l,t,s至多一个为0}分成不相邻的子集,这些子集对应的线性码是不等价的。(l,t,s,i,j)可能的取值如下:

运用Matlab程序［11］,计算得:当(l,t,s,i,j)取前8个元素时,得到的线性码最小距离为10,其余的线性码最小距离均小于10。用Ci表示(l,t,s,i,j)取第i个元素时所生成的线性码,可得到以下结论:

定理2 在等价情况下,有型(13-(4,2))的二元自对偶码［54,27,10］只有8种。C1的生成矩阵如下:

3 有类似型的二元自对偶码

由定理2知,对有13-(4,4)型的二元自对偶码, η(Fσ(C))是一个［8,4］码,根据文献［3］,［8,4］二元自对偶码在等价情况下只有2种C42和A8,C42的生成矩阵为:

有13-(4,4)型的二元自对偶码［56,28,10］,码字的重量不应是4的倍数。因此,该码只能等价于。Eσ(C)的生成矩阵同上。故得到:

定理3 有13-(4,4)型的二元自对偶码［56, 28,10］的生成矩阵为:

U,V和Vi(i=1,2,3,4)同定理1。

对生成矩阵进行类似变形,并运行Matlab程序,无论(l,t,s,i,j)取任何数值,由该生成矩阵得到的码字最小距离都小于10。因此:

定理4 有13-(4,4)型的二元自对偶码［56, 28,10］共有16种,分别为:C30,C31,…,C45。

类似地,对有13(4,6)型的二元自对偶码进行考虑,运行程序,得到:

定理5 有13-(4,6)型的二元自对偶码［58, 29,10］［12］只有10种,分别为:

4 结束语

本文针对线性码中最重要的二元自对偶码进行论述,试图找出其生成矩阵和分类情况。但对长度较长的线性码,要找到这样的线性码非常困难。原因是对长度较长的线性码进行讨论时,总是先将它分成几个长度较短的线性码的直和,但长度小于32的线性码在等价情况下也有多种。因此,限制了长度为54的线性码有一个13-(4,2)型的自同构,得到了它的生成矩阵及分类情况。下一步将研究对其他型的自同构,以用于线性码及解码工作的发展。

［1］ Rains E M.Shadow Bounds for Self-dual Codes［J］.IEEE Transactions on Information Theory,1998,44(1): 134-139.

［2］ Conway J H,ASloane N J.A New Upper Bound on the Minimal Distance ofSelf-dualCodes［J］.IEEE Transactions on Information Theory,1990,36(6): 1319-1333.

［3］ Tsai H P.Existence of Some Extremal Self-dual Codes［J］.IEEE Transactions on Information Theory,1992,38 (6):1829-1833.

［4］ Huffman W C.On the Classification and Enumeration of Self-dual Codes［J］.Finite Fields and Their Appplications, 2005,11(3):451-490.

［5］ Bouyuklieva S,Yankov N,Kim J.Classification of Binary Self-dual［48,24,10］Codes with an Automorphism of Odd Prime Order［J］.Finite Fields and Their Applications,2012, 18(6):1104-1113.

［6］ Huffman W C.Automorphisms of Codes with Application Extremal Doubly——Even Codes of Length 48［J］.IEEE Transactions on Information Theory,1982,28(3):511-521.

［7］ Yorgov V.The Extremal Codes of Length 42 with Automorphism of Order 7［J］.Discrete Mathematics, 1998,190(1):201-213.

［8］ Bouyuklieva S,Yankov N,Russeva R.Classification of the Binary Self-dual［42,21,8］ Codes Having an Automorphism of Order 3［J］.Finite Fields and Their Applications,2007,13(1):605-615.

［9］ Yorgov V Y.Binary Self-dual Codes with an Automorphism of Odd Order［J］.Problems of Inform Transmission, 1983,19(4):11-24.

［10］ 陆正福,李亚东,王国栋.GF(2m)上线性码自同构群的进一步研究［J］.云南大学学报:自然科学版,2011, 23(6):401-404.

［11］ 张 斌,李夕海,苏 娟,等.基于IDL和Visual C++的混合编程［J］.计算机工程,2005,31(4):79-81.

［12］ Jonlard K.New Extremal Self-dual Codes of Length 36, 38 and 58［J］.IEEE Transactions on Information Theory,2001,47(1):386-393.

编辑 顾逸斐

Binary Self-dual Codes with Type of 13-(4,m)(m=2,4,6)

WANG Rong
(School of Applied Mathematics,Shanxi University of Finance and Economics,Taiyuan 030031,China)

The paper discusses the binary self-dual code of error correcting code,looking the code as a polynomial on the field GF(2)nand factorizing it.It constructs the longer length code by the shorter length code and gives the code's generator matrix.Owning to code's equivalence,the possible classification of length 54 binary self-dual codes with an automorphism of order 13 is given.By implementing Matlab procedures,there are eight self-dual codes up to equivalence.By similar method,there are 16 self-dual codes with type of 13-(4,4)and there are 10 self-dual codes with type of 13-(4,6)up to equinalence.Therefore,the generator matrices and classifications of the binary self-dual code with type of 13-(4,2),13-(4,4)and 13-(4,6)are solved completely.

binary self-dual code;automorphism;generator matrix;equivalence;cycling matrix;classification

1000-3428(2014)11-0255-05

A

O157.4

10.3969/j.issn.1000-3428.2014.11.051

教育部人文社会科学研究青年基金资助项目(12YJCZH098);山西省教育科学“十二五”规划2012年度课题基金资助项目(GH-12034)。

王 荣(1980-),女,讲师、博士研究生,主研方向:代数编码。

2014-03-31

2014-05-31E-mail:wangrong101377@126.com

中文引用格式:王 荣.有13-(4,m)型的二元自对偶码(m=2,4,6)［J］.计算机工程,2014,40(11):255-259.

英文引用格式:Wang Rong.Binary Self-dual Codes with Type of 13-(4,m)(m=2,4,6)［J］.Computer Engineering, 2014,40(11):255-259.