有19-(4,f)型自同構的二元自對偶碼*

王 榮,王俊新

(山西財經大學應用數學學院,山西 太原 030006)

有19-(4,f)型自同構的二元自對偶碼*

王 榮,王俊新

(山西財經大學應用數學學院,山西 太原 030006)

應用二元自對偶碼可看成幾個自對偶碼的直和理論，研究了具有19-(4,f)型自同構、碼長在100以內的的二元自對偶碼。這種對偶碼都可看成一個碼長為4的收縮碼和GF(2)n上一些偶重量多項式的直和。證明了碼長大于80且小于100時，不存在19-(4,f)型的二元自對偶碼。根據碼長較短的自對偶碼分別構造出了碼長為76、78和80的二元自對偶碼，并給出其生成矩陣。由碼的等價得到了這幾類碼可能的分類情況。運行Matlab程序，證明了具有19-(4,2)型和19-(4,4)型的二元自對偶碼在等價情況下都有11個，19-(4,0)型的二元自對偶碼在等價情況下是不存在的。

自對偶碼;生成矩陣;自同構;等價

1 引言

自對偶碼是一種特殊的糾錯碼，為使碼有較強的糾錯能力，需要增加碼元，以增加碼字間的差別，使碼字的錯誤發生在一定的范圍內，不會變成另一個碼字。也就是說，按照一定規則把原來的碼字變成有剩余長度的碼字，并且碼字的碼元之間存在著一定的關系，這種關系的建立過程就是編碼。碼字到達接收端，用編碼的規則來檢驗，如果不發生錯誤，原規則一定是適用的，否則原規則不滿足。因此，可根據編碼規則來判定編碼過程中是否發生了錯誤。如果發生，在糾錯能力內按照一定的規則確定位置并糾錯。自對偶碼在編碼糾錯中有非常重要的作用，清楚地知道其分類和構成情況也更為必要。長度不大于32的自對偶碼的生成矩陣及分類情況已經全部解決[1]。2012年，Bouyuklieva S[2]證明了不存在有3-(12,12)和3-(14,6)型自同構的自對偶碼，并且有3-(16,0)型自同構的自對偶碼共有264種。同年，王榮、王俊新[3]證明了有17階自同構的二元自對偶碼[52,26,10]僅有一種。近期，王榮[4]證明有13-(4,2)型的二元自對偶碼只有8個,存在16個有13-(4,4)型的二元自對偶碼，有13-(4,6)型的二元自對偶碼有10種。 2011年，Yorgov V[5]給出了長度為42的二元自對偶碼，有7階自同構情況時有29種。楊慶[6]構建了369種長度為38的二元自對偶極值碼。2008年，樊繼秋[7]考慮了碼長為38的二元自對偶極值碼，并給出其矩陣算法，得到了該極值碼。2007年，Bouyuklieva S[8]指出有3-(14,0)型自同構的自對偶碼有16 607種。本文試圖解決有19階自同構的自對偶碼。

2 基礎知識

對一個二元域GF(2)n上的線性碼，碼字的前一部分是信息自身：u1,u2,…,uk，后一部分是校驗符：uk+1,uk+2,…,un，所有的碼字構成了長度為n、維數為k的一個線性子空間，稱為GF(2)n上的一個[n,k]線性碼C。對一個線性碼C，其對偶碼C⊥={v|(u,v)=0,?u∈C}((u,v)為GF(2)n上的內積)，若C=C⊥，C就叫二元自對偶碼。對一個自對偶碼，維數必滿足k=n-k，即k=n/2，n一定是偶數。對?u=(u1,u2,…,un)∈C，u的重量wt(u)指u1,u2,…,un中非零數的個數。兩個碼字的距離dist(u,v)指任意兩個不相同碼字u=(u1,u2,…,un)和v=(v1,v2,…,vn)在相同位置上取值不相同的位數，即dist(u,v)=wt(u-v)。GF(2)n上最小距離為d的 [n,k]碼稱為二元自對偶[n,k,d]碼。由于自對偶碼是一個線性子空間，所以二元自對偶碼C的最小距離是非零碼字的最小wt(u)值。如果一個二元自對偶碼的碼字重量都能被4整除，這個碼稱為雙偶碼，否則是單偶碼。

對GF(2)n上的二元自對偶碼C的碼字u=(u1,u2,…,un)和n次對稱群Sn中的τ，定義Cτ中的元素uτ=(uτ(1),uτ(2),…,uτ(n))，則碼Cτ和C稱為等價的。置換τ叫碼C的一個自同構。C的所有自同構的集合形成Sn的一個子群，叫碼C的自同構群，用AUT(C)表示。若τ∈AUT(C)，τ的階為p，且有c個獨立的循環，f個固定點，則τ有型p-(c,f)。

定理1對有型p-(c,f)的二元自對偶碼[78,39,14]，只存在p-(c,f)=19-(4,2)。

證明當p≥19時，對二元自對偶碼[78,39,14]，所有可能的型為：19-(4,2)，19-(3,21)，19-(2,40)，19-(1,59)，23-(3,9)，23-(2,32)，23-(1,55)，29-(2,20)，29-(1,49)，31-(2,16)，31-(1,47)，37-(2,4)，37-(1,41)，41-(1,37)，43-(1,35)，47-(1,31)，53-(1,25)，59-(1,19)，61-(1,17)，67-(1,11)，71-(1,7)，73-(1,5)。應用引理2易得：除了型19-(4,2)，其余的型都不可能存在。

□

定理2當碼長大于80且小于100時，不存在有19-(4,f)型的二元自對偶碼。

證明當碼長大于80且小于100時，最小距離為16，這些碼可能的自同構型為19-(4,6)， 19-(4,8)， 19-(4,10)， 19-(4,12)， 19-(4,14)， 19-(4,16)， 19-(4,18)和19-(4,20)。

□

2.1 碼的生成矩陣

令C是有19階自同構的二元自對偶碼，根據定理1，可假設自同構具有如下形式：

σ=(1,2,…,19)(20,21,…,38)…(51,52,…,76)(77)(78)。

令Ω1=(1,2,…,19),Ω2=(20,21,…,38),Ω3=(39,40,…,57),Ω4=(58,59,…,76),Ω5=(77),Ω6=(78)。

設Fτ(C)={u∈C|uτ=u}，Eτ(C)={u∈C|wt(u|Ωi)≡0(mod 2)},i=1,2,3,4.}。其中，u|Ωi指u在Ωi上的限制。由文獻[1]知：C=Fτ(C)⊕Eτ(C)。

令P是GF(2)n上由x-1生成的長度為19的循環碼。由于x18+x17+…+x+1是GF(2)n上的不可約多項式。域P有218個元素。令Eτ(C)*是去掉最后兩位的碼字，?u ∈Eτ(C)*，u|Ωi有偶重量。作映射u|Ωi→P，即:

(u0,u1,…,u18)→u0+u1x+…+u18x18，則有φ:Eτ(C)*→P4。

引理3[9]有型p-(c,f)的線性碼C是自對偶?下列兩條件同時成立。

(1)收縮碼π(Fτ(C))是自對偶碼；

由引理3知，π(Fτ(C))是一個[6,3]二元自對偶碼。由文獻[1]得，[6,3]二元自對偶碼在等價情況下只有一個，生成矩陣為：

(1)

的 [4,2]二元自對偶碼。因此，假定φ(Eτ(C)*)的生成矩陣為下述矩陣：

其中，ai(x)∈P,i=1,2,3,4。e(x)=x+x2+…+x18是域P的單位元。A的兩行在內積式(1)下是正交的，等價下有兩種可能矩陣：

s=0,1,…,18;ti=1,2,…,27×511,i=1,2,3,4。b(x)=1+x2+x3+x6+x7+x9+x10+x11+x13+x14+x15+x18為P的本原元(階為27×511)，g(x)=xe(x)，階為19。A1的行只可能是下列四種情形：

(e(x)0e(x)0)

(e(x)0b(x)5110)

(e(x)0b(x)3×5110)

(e(x)0b(x)9×5110)

現考慮A2，由于行的正交性，得到b(x)t3+29t1=b(x)t4+29t2g(x)s，s只能為0(s>0，設b(x)t4+29t2的階為r，g(x)s的階為19，必有(r,19)=1，b(x)t4+29t2g(x)s的階為19×r，所以19整除b(x)t3+29t1的階，矛盾)，因此A2可簡化為：

故φ(Eτ(C)*)的生成矩陣為：

定理3有型19-(4,2)的二元自對偶碼[78,39,14]的生成矩陣為：

前三行中，黑體0和1表示元素全為0和1的1×19行向量。后兩行中的U和Vi(i=1,2,3,4)和前兩列中的0如前所述，后兩列的0表示18×1的列向量。

2.2 碼的分類

引理4[9]兩個有同樣型(19-(4,2))的二元自對偶碼C和C′，如果碼C可通過對碼C′進行下列變換的乘積得到，則這兩個碼是等價的。

(3)C中4個循環的一個置換；

(4)C中固定點的一個置換。

在矩陣A′中作變換x→x2(參考文獻[10])，則:

(2)

對矩陣應用置換(1,2)(3,4)得：

(3)

應用置換(1,3)(2,4)可得：

(4)

應用置換(1,3)和(2,3)可得：

(5)

(6)

運用Matlab程序，其設計思路如下：

(1)用一個行向量表示一個多項式，并定義兩多項式的加法及乘法；

(2)根據定理2中每一個黑體元素所對應的循環矩陣得到二元自對偶碼[78,39,14]的生成矩陣；

(3)對生成矩陣的行、列進行線性變換，得到形如(M|I)的矩陣形式，M、I為39×39的矩陣，其中I為單位矩陣。

(4)計算矩陣M生成的任意碼字間的最小距離d1，如果d1+1=14，則輸出對應的參數，否則繼續下一次循環。

(93,476,16,8,11,25) (77,182,2,4,14,19)

(77,182,0,1,19,23) (29,118,0,2,3,24)

(23,428,6,6,6,6) (27,467,6,16,19,21)

(9,388,15,1,3,15) (9,388,3,19,23,11)

(3,342,13,19,26,17) (3,342,11,7,9,17)

(3,342,8,6,12,22)

定理4有型19-(4,2)的二元自對偶碼[78,39,14]在等價情況下共有11種:C1,C2,…,C11。

C1的生成矩陣如圖1所示。

3 有相似性自同構的二元自對偶碼

3.1 p-(c,f)=19-(4,4)

A8的生成矩陣為：

在該生成矩陣中，前四行黑體0和1表示元素全為0和1的1×19行向量。后兩行中的U和Vi(i=1,2,3,4)如前所述，后兩行前兩列中的0表示18×19的零矩陣，后兩行后兩列的0表示18×1的列向量。

(91,472,15,8,11,23) (75,180,2,3,16,21)

(73,181,0,1,19,23) (39,128,0,2,3,24)

(23,428,3,6,7,6) (29,463,6,16,17,21)

(9,358,15,1,3,15) (9,358,3,17,23,11)

(3,332,13,17,26,17) (3,342,7,7,9,17)

(3,332,8,4,10,22)

111111111111111111100000000000000000000000000000000000000111111111111111111100000000000000000000011111111111111111110000000000000000000000000000000000000010000000000000000000000000000000000000001111111111111111111000000000000000000001011111111111111111100000000000000000000000110110111110010101010101111101010100101111111111111111100000000000000000000000011011011111001110101010111110101000110111111111111111100000000000000000001000001101101111100011010101011111010100111011111111111111100000000000000000000100000110110111110101101010101111101000111101111111111111100000000000000000000010000011011011111010110101010111110100111110111111111111100000000000000000001001000001101101111101011010101011111000111111011111111111100000000000000000001100100000110110111010101101010101111100111111101111111111100000000000000000001110010000011011011101010110101010111100111111110111111111100000000000000000001111001000001101101110101011010101011100111111111011111111100000000000000000001111100100000110110111010101101010101100111111111101111111100000000000000000000111110010000011011111101010110101010100111111111110111111100000000000000000001011111001000001101111110101011010101000111111111111011111100000000000000000001101111100100000110011111010101101010100111111111111101111100000000000000000000110111110010000011101111101010110101000111111111111110111100000000000000000001011011111001000001010111110101011010100111111111111111011100000000000000000001101101111100100000101011111010101101000111111111111111101100000000000000000000110110111110010000010101111101010110100111111111111111110100000000000000000000011011011111001000101010111110101011000000000000000000000001111111111111111111101010111110101010001001111101101100000000000000000000000010111111111111111110110101011111010101000100111110110110000000000000000000000011011111111111111111011010101111101010000010011111011011000000000000000000000011101111111111111110101101010111110101000001001111101101100000000000000000000011110111111111111111010110101011111010100000100111110110100000000000000000000011111011111111111110101011010101111101110000010011111011000000000000000000000011111101111111111111010101101010111110011000001001111101100000000000000000000011111110111111111110101010110101011111101100000100111110100000000000000000000011111111011111111111010101011010101111110110000010011111000000000000000000000011111111101111111111101010101101010111011011000001001111100000000000000000000011111111110111111111110101010110101011101101100000100111100000000000000000000011111111111011111111111010101011010101110110110000010011100000000000000000000011111111111101111111111101010101101010111011011000001001100000000000000000000011111111111110111110111110101010110101111101101100000100100000000000000000000011111111111111011111011111010101011010111110110110000010000000000000000000000011111111111111101110101111101010101101011111011011000001000000000000000000000011111111111111110111010111110101010110001111101101100000100000000000000000000011111111111111111010101011111010101011100111110110110000000

Figure 1 Matrix generated byC1

圖1C1的生成矩陣

定理5有19-(4,4)型自同構的二元自對偶碼[80,40,16]在等價情況下共有11種。

3.2 p-(c,f)=19-(4,0)

由引理3知，有19-(4,0)型自同構的二元自對偶碼[76,38,14]，π(Fτ(C))是一個[4,2]碼，由文獻[1]知,[4,2]二元自對偶碼在等價情況只有一種，其生成矩陣為：

同上節，有19-(4,0)型自同構的二元自對偶碼[76,38,14]的生成矩陣為：

矩陣中前兩行黑體0和1表示元素全為0和1的1×19行向量。后兩行中的U和Vi(i=1,2,3,4)如前所述，0表示18×19的零矩陣。

運行Matlab程序，得到:

定理6不存在有19-(4,0)型自同構的二元自對偶碼[76,38,14] 。

4 結束語

對糾錯碼中的二元自對偶碼討論[11]，以期找出長度較長的二元自對偶碼的生成矩陣及分類。但是，對此類線性碼，由于其長度較長和所有型的復雜性，要解決它的分類非常困難。本文中把碼長為76、78和80的碼分解成長度為4的收縮碼和GF(2)n上偶重量多項式的直和，得到了它們的生成矩陣及其分類，并且證明了長度大于80且小于100的二元自對偶碼不存在19-(4,f)型的自對偶碼。對碼長更長的碼和不同型的自對偶碼，將是作者研究的下階段目標。這將對解碼工作有重要意義。

[1] Huffman W C. On the classification and enumeration of self-dual codes [J].Finite Fields and Their Appplications,2005,11(3):451-490.

[2] 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.

[3] Wang Rong, Wang Jun-xin.[52,26,10] binary self-dual codes with type of (17,3,1)[J].Computer Engineering and Applications,2012,48(19):46-47.(in Chinese)

[4] Wang Rong.Binary self-dual codes with type of 13-(4,m)(m=2,4,6)[J].Computer Engineering,2014,40(11):255-259.(in Chinese)

[5] Yorgov V.Erratum to “The extremal codes of length 42 with automorphism of order 7”[J]. Discrete Mathematics,2011,311(16):1860-1861.

[6] Yang Qing.Binary self-dual codes of length 38[N].Science and Technology Innovation Herald,2011(35):76.(in Chinese)

[7] Fan Ji-qiu,Xie Jing-ran,Yang Qing. Extremal self-dual binary codes with automorphisms with type 3-(12,2)[J].Journal of Jilin University (Science Edition),2008,46(5):870-872.(in Chinese)

[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(3):605-615.

[9] Yorgov V Y,Binary self-dual codes with automorphism of odd order[J]. Problems of Inform Transmission,1983(19):11-24.

[10] Lu Zheng-fu,Li Ya-dong,Wang Guo-dong. The further research about the automorphism group of a linear code over GF(2m)[J]. Journal of Yunnan Univeristy(Natural Sciences),2011,23(6):401-404.(in Chinese)

[11] Ning Ping. Exploration for parallel computing of CRC16 checksum on FPGA[J].Computer Engineering & Science,2014,36(6):1023-1027.(in Chinese)

附中文參考文獻：

[3] 王榮,王俊新. 有(17,3,1)型的二元自對偶編碼[52,26,10][J]. 計算機工程與應用,2012,48(19):46-47.

[4] 王榮. 有13-(4,m)型的二元自對偶碼(m=2,4,6)[J]. 計算機工程,2014,40(11):255-259.

[6] 楊慶. 碼長為38的二元自對偶極值碼[J]. 科技創新導報,2011(35):76.

[7] 樊繼秋,謝敬然,楊慶. 具有3-(12,2)型自同構的二元自對偶極值碼[J]. 吉林大學學報(理學版),2008,46(5):870-872.

[10] 陸正福，李亞東，王國棟.GF(2m)上線性碼自同構群的進一步研究[J].云南大學學報(自然科學版)，2011,23(6):401-404.

[11] 寧平. FPGA上實現CRC16糾錯編碼并行計算的探討[J]. 計算機工程與科學,2014,36(6):1023-1027.

王榮(1980-),女,山西晉城人，博士，講師，研究方向為代數編碼。E-mail:wangrong101377@126.com

WANG Rong,born in 1980,PhD,lecturer,her research interest includes algebraic coding.

王俊新(1966-),男，山西呂梁人，博士，教授，研究方向為群代數。

WANG Jun-xin,born in 1966,PhD,professor,his research interest includes group alggebra.

Binary self-dual codes with 19-(4,f) automorphism

WANG Rong,WANG Jun-xin

(College of Applied Mathematics,Shanxi University of Finance and Economics,Taiyuan 030006,China )

We discuss the binary self-dual codes of length 76 and 100 with automorphism of order 19. These binary self-dual codes can be seen as a direct sum of contract code of length 4 and some even-weight polynomials overGF(2)n. We prove that self-dual codes of length between 80 and 100 do not exist. We also construct the binary self-dual codes of length 76, 78 and 80 through the shorter self-dual codes respectively, and present their generator matrices. Simulations in Matlab prove that under the condition of equivalence, there are 11 binary self-dual codes of 19-(4, 2) and 19-(4,4) types, whereas binary self-dual codes of 19-(4, 0) type do not exist.

self-dual codes;generator matrix;automorphism;equivalence

1007-130X(2015)09-1661-06

2014-12-17;

2015-04-21基金項目：國家自然科學基金資助項目(70973072，70573066);山西財經大學青年科研基金資助項目(晉財大校[2014]90號)

TN911.22

A

10.3969/j.issn.1007-130X.2015.09.010

通信地址：030006 山西省太原市山西財經大學應用數學學院

Address:College of Applied Mathematics,Shanxi University of Finance and Economics，Taiyuan 030006,Shanxi,P.R.China