王 榮

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

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

王 榮

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

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

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

1 概述

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

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

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

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

對(duì)長(zhǎng)度為54的二元自對(duì)偶碼進(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)?，F(xiàn)考慮有13-(4,2)型自同構(gòu)的自對(duì)偶碼。

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)。

對(duì)?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)出的收縮線(xiàn)性碼。

對(duì)?u∈Eσ(C),令=u|Ωi(看成R的元,i= 1,2,3,4),Eσ(C)*=|u∈Eσ(C)},于是Eσ(C)*是R上的線(xiàn)性碼。由Eσ(C)和I1的定義知:Eσ(C)*=。

引理2 具有型p-(c,f)的二元線(xiàn)性碼C是自對(duì)偶的?下列2個(gè)條件同時(shí)成立［9］。

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

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

因此,η(Fσ(C))是一個(gè)［6,3］二元自對(duì)偶碼。由文獻(xiàn)［4］知,在等價(jià)情況下,該線(xiàn)性碼只有一個(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。可用βγ來(lái)代替上面矩陣中的α(x),得到:

對(duì)其進(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)過(guò)計(jì)算機(jī)搜索,只有當(dāng)i,j3,j,j4滿(mǎn)足表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)矩陣的第一行分別對(duì)應(yīng)于矩陣(5)中的多項(xiàng)式δl,δt,βi,βjδs,βiδs。

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

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

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

2.2 碼的分類(lèi)情況

引理4 對(duì)2個(gè)具有相同型(13-(4,2))的二元自對(duì)偶碼,如果C′可以通過(guò)對(duì)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}}。

對(duì)(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)},對(duì)矩陣的列應(yīng)用置換(1,2)(3,4),得:

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

K是交錯(cuò)群A4的正規(guī)子群,{1,(1,4,3),(1,4, 3)(1,4,3)}是K在A4中的陪集代表［7］。置換(1,4, 3)對(duì)應(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}分成不相鄰的子集,這些子集對(duì)應(yīng)的線(xiàn)性碼是不等價(jià)的。(l,t,s,i,j)可能的取值如下:

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

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

3 有類(lèi)似型的二元自對(duì)偶碼

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

本文針對(duì)線(xiàn)性碼中最重要的二元自對(duì)偶碼進(jìn)行論述,試圖找出其生成矩陣和分類(lèi)情況。但對(duì)長(zhǎng)度較長(zhǎng)的線(xiàn)性碼,要找到這樣的線(xiàn)性碼非常困難。原因是對(duì)長(zhǎng)度較長(zhǎng)的線(xiàn)性碼進(jìn)行討論時(shí),總是先將它分成幾個(gè)長(zhǎng)度較短的線(xiàn)性碼的直和,但長(zhǎng)度小于32的線(xiàn)性碼在等價(jià)情況下也有多種。因此,限制了長(zhǎng)度為54的線(xiàn)性碼有一個(gè)13-(4,2)型的自同構(gòu),得到了它的生成矩陣及分類(lèi)情況。下一步將研究對(duì)其他型的自同構(gòu),以用于線(xiàn)性碼及解碼工作的發(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］ 陸正福,李亞?wèn)|,王國(guó)棟.GF(2m)上線(xiàn)性碼自同構(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

教育部人文社會(huì)科學(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)型的二元自對(duì)偶碼(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.