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

王 榮

(山西財(cái)經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院,太原030031)

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

王 榮

(山西財(cái)經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院,太原030031)

論述糾錯(cuò)碼中的二元自對偶碼,把碼字看成二元域GF(2n)上的多項(xiàng)式,并分解因式。根據(jù)碼長較短的二元自對偶碼,構(gòu)造出長度較長的二元自對偶碼,并給出生成矩陣。運(yùn)用2個(gè)碼等價(jià)的類型,得到在等價(jià)下可能的碼的分類情況,運(yùn)行Matlab程序,證明具有13-(4,2)型自同構(gòu)的二元自對偶碼［54,27,10］只有8個(gè)等價(jià)的自對偶碼。應(yīng)用該方法,得到二元自對偶碼［56,28,10］的生成矩陣。運(yùn)行程序證明在等價(jià)情況下,存在16個(gè)有13-(4,4)型的自對偶碼,而有13-(4,6)型的二元自對偶碼［58,29,10］在等價(jià)下只有10種碼。

二元自對偶碼;自同構(gòu);生成矩陣;等價(jià);循環(huán)矩陣;分類

1 概述

二元自對偶碼在信道碼中占有非常重要的地位,它是一種糾錯(cuò)碼,把每一個(gè)信息轉(zhuǎn)化為0和1的序列,然后對這個(gè)序列進(jìn)行編碼來防止它們在信道傳輸時(shí)發(fā)生錯(cuò)誤。

設(shè)σ是一個(gè)n階置換,對線性碼C的任一個(gè)碼字u=(u1,u2,…,un),令 uσ=(uσ(1),uσ(2),…,uσ(n))。對GF(2)n上的一個(gè)線性碼C,Cσ={uσ|u∈C},如果C=Cσ,則稱σ是線性碼C的一個(gè)自同構(gòu),C的全體自同構(gòu)的集合構(gòu)成n階對稱群Sn的一個(gè)子群,稱為自同構(gòu)群。設(shè)p是素?cái)?shù),如果σ有c個(gè)p循環(huán)和f= n-cp個(gè)固定點(diǎn),則稱σ是p-(c,f)型的。

線性碼的構(gòu)造和分類是編碼理論的基本內(nèi)容,自對偶碼在編碼理論中具有重要作用。對碼長不超過32的自對偶碼,其構(gòu)造和分類已經(jīng)得到完全解決［3-4］。但對碼長較長的二元自對偶碼研究得還很少。文獻(xiàn)［5］證明了對二元自對偶碼［48,24,10］,有3-(16,0)型的線性碼在等價(jià)情況只有264種［6］。文獻(xiàn)［7］證明了對有7階自同構(gòu)的二元極值碼［42, 21,8］,在等價(jià)情況下只有29種［8］。本文對碼長為54,56和58的二元自對偶碼有特殊型時(shí)進(jìn)行研究。

2 有13-(4,2)型的二元自對偶碼

對長度為54的二元自對偶碼進(jìn)行討論,得到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)。現(xiàn)考慮有13-(4,2)型自同構(gòu)的自對偶碼。

2.1 碼的生成矩陣

設(shè):

σ=(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個(gè)固定點(diǎn),并用2個(gè)0補(bǔ)充所得的碼字,Eσ(C)={u∈C|wt(ˉu|Ωi)=0(mod2)},(u|Ωi是u在Ωi上的限制),由文獻(xiàn)［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導(dǎo)出的收縮線性碼。

對?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個(gè)條件同時(shí)成立［9］。

(1)收縮線性碼η(Fσ(C))是一個(gè)自對偶碼;

(2)Eσ(C)*是關(guān)于內(nèi)積

因此,η(Fσ(C))是一個(gè)［6,3］二元自對偶碼。由文獻(xiàn)［4］知,在等價(jià)情況下,該線性碼只有一個(gè),其生成矩陣為:

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

證明:e=x+x2+x3+…+x12是I1的一個(gè)單位元。由于212-1=32×5×7×13,且

因此α(x)的階為212-1。證畢。

令β=α(x)65,γ=α(x)63,δ=γ13,則β和γ的階分別為63和65,βγ的階為6365=212-1,δ的階為5。可用βγ來代替上面矩陣中的α(x),得到:

對其進(jìn)行一系列的矩陣初等變換得:

由于e,δ,δ2,δ3,δ4為(γ5)在(γ)中的陪集代表,δ=1+x4+x10+x12,δ2=1+x7+x8+x11,δ3=1+x2+x5+x6,δ4=1+x+x3+x9。根據(jù)引理4的(2),可用(γ5)的一個(gè)元素乘Eσ(C)*經(jīng)變換后的生成矩陣得:

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的乘法群的一個(gè)階為63的子群。β的所有冪在表1中列出(βi=xj1+xj2+…+xjr)。

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

經(jīng)過計(jì)算機(jī)搜索,只有當(dāng)i,j3,j,j4滿足表2取值時(shí),式(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循環(huán)矩陣,且每個(gè)循環(huán)矩陣的第一行分別對應(yīng)于矩陣(5)中的多項(xiàng)式δl,δt,βi,βjδs,βiδs。

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

定理1 有13-(4,2)型自同構(gòu)的二元自對偶碼的生成矩陣為:

其中,前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個(gè)具有相同型(13-(4,2))的二元自對偶碼,如果C′可以通過對C進(jìn)行下列變換的乘積得到,則C和C′是等價(jià)的［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個(gè)循環(huán)的置換;

(4)C的后2個(gè)固定點(diǎn)的一個(gè)置換。

因此,在矩陣(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)重復(fù)應(yīng)用6次式(4)中置換,可得:

由于23×9≡9(mod63),運(yùn)用式(4)可得:

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

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

令K={1,(1,2)(3,4),(1,3)(2,4),(1,4)(2, 3)},對矩陣的列應(yīng)用置換(1,2)(3,4),得:

類似的,(1,4)(2,3)所對應(yīng)的變換是:

K是交錯(cuò)群A4的正規(guī)子群,{1,(1,4,3),(1,4, 3)(1,4,3)}是K在A4中的陪集代表［7］。置換(1,4, 3)對應(yīng)變換:

應(yīng)用式(4)～式(11)的變換,可把集合{(l,t,s,i, j)|{i,j}∈M,0≤l,t,s≤4,l,t,s不全相等,且l,t,s至多一個(gè)為0}分成不相鄰的子集,這些子集對應(yīng)的線性碼是不等價(jià)的。(l,t,s,i,j)可能的取值如下:

運(yùn)用Matlab程序［11］,計(jì)算得:當(dāng)(l,t,s,i,j)取前8個(gè)元素時(shí),得到的線性碼最小距離為10,其余的線性碼最小距離均小于10。用Ci表示(l,t,s,i,j)取第i個(gè)元素時(shí)所生成的線性碼,可得到以下結(jié)論:

定理2 在等價(jià)情況下,有型(13-(4,2))的二元自對偶碼［54,27,10］只有8種。C1的生成矩陣如下:

3 有類似型的二元自對偶碼

由定理2知,對有13-(4,4)型的二元自對偶碼, η(Fσ(C))是一個(gè)［8,4］碼,根據(jù)文獻(xiàn)［3］,［8,4］二元自對偶碼在等價(jià)情況下只有2種C42和A8,C42的生成矩陣為:

有13-(4,4)型的二元自對偶碼［56,28,10］,碼字的重量不應(yīng)是4的倍數(shù)。因此,該碼只能等價(jià)于。Eσ(C)的生成矩陣同上。故得到:

定理3 有13-(4,4)型的二元自對偶碼［56, 28,10］的生成矩陣為:

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

對生成矩陣進(jìn)行類似變形,并運(yùn)行Matlab程序,無論(l,t,s,i,j)取任何數(shù)值,由該生成矩陣得到的碼字最小距離都小于10。因此:

定理4 有13-(4,4)型的二元自對偶碼［56, 28,10］共有16種,分別為:C30,C31,…,C45。

類似地,對有13(4,6)型的二元自對偶碼進(jìn)行考慮,運(yùn)行程序,得到:

定理5 有13-(4,6)型的二元自對偶碼［58, 29,10］［12］只有10種,分別為:

4 結(jié)束語

本文針對線性碼中最重要的二元自對偶碼進(jìn)行論述,試圖找出其生成矩陣和分類情況。但對長度較長的線性碼,要找到這樣的線性碼非常困難。原因是對長度較長的線性碼進(jìn)行討論時(shí),總是先將它分成幾個(gè)長度較短的線性碼的直和,但長度小于32的線性碼在等價(jià)情況下也有多種。因此,限制了長度為54的線性碼有一個(gè)13-(4,2)型的自同構(gòu),得到了它的生成矩陣及分類情況。下一步將研究對其他型的自同構(gòu),以用于線性碼及解碼工作的發(fā)展。

［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)上線性碼自同構(gòu)群的進(jìn)一步研究［J］.云南大學(xué)學(xué)報(bào):自然科學(xué)版,2011, 23(6):401-404.

［11］ 張 斌,李夕海,蘇 娟,等.基于IDL和Visual C++的混合編程［J］.計(jì)算機(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

教育部人文社會科學(xué)研究青年基金資助項(xiàng)目(12YJCZH098);山西省教育科學(xué)“十二五”規(guī)劃2012年度課題基金資助項(xiàng)目(GH-12034)。

王 榮(1980-),女,講師、博士研究生,主研方向:代數(shù)編碼。

2014-03-31

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

中文引用格式:王 榮.有13-(4,m)型的二元自對偶碼(m=2,4,6)［J］.計(jì)算機(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.