王 榮,王俊新

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

有19-(4,f)型自同構(gòu)的二元自對(duì)偶碼*

王 榮,王俊新

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

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

自對(duì)偶碼;生成矩陣;自同構(gòu);等價(jià)

1 引言

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

2 基礎(chǔ)知識(shí)

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

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

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

證明當(dāng)p≥19時(shí)，對(duì)二元自對(duì)偶碼[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)。應(yīng)用引理2易得：除了型19-(4,2)，其余的型都不可能存在。

□

定理2當(dāng)碼長(zhǎng)大于80且小于100時(shí)，不存在有19-(4,f)型的二元自對(duì)偶碼。

證明當(dāng)碼長(zhǎng)大于80且小于100時(shí)，最小距離為16，這些碼可能的自同構(gòu)型為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階自同構(gòu)的二元自對(duì)偶碼，根據(jù)定理1，可假設(shè)自同構(gòu)具有如下形式：

σ=(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)。

設(shè)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上的限制。由文獻(xiàn)[1]知：C=Fτ(C)⊕Eτ(C)。

令P是GF(2)n上由x-1生成的長(zhǎng)度為19的循環(huán)碼。由于x18+x17+…+x+1是GF(2)n上的不可約多項(xiàng)式。域P有218個(gè)元素。令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是自對(duì)偶?下列兩條件同時(shí)成立。

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

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

(1)

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

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

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)

現(xiàn)考慮A2，由于行的正交性，得到b(x)t3+29t1=b(x)t4+29t2g(x)s，s只能為0(s>0，設(shè)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可簡(jiǎn)化為：

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

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

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

2.2 碼的分類(lèi)

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

(3)C中4個(gè)循環(huán)的一個(gè)置換；

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

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

(2)

對(duì)矩陣應(yīng)用置換(1,2)(3,4)得：

(3)

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

(4)

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

(5)

(6)

運(yùn)用Matlab程序，其設(shè)計(jì)思路如下：

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

(2)根據(jù)定理2中每一個(gè)黑體元素所對(duì)應(yīng)的循環(huán)矩陣得到二元自對(duì)偶碼[78,39,14]的生成矩陣；

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

(4)計(jì)算矩陣M生成的任意碼字間的最小距離d1，如果d1+1=14，則輸出對(duì)應(yīng)的參數(shù)，否則繼續(xù)下一次循環(huán)。

(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)的二元自對(duì)偶碼[78,39,14]在等價(jià)情況下共有11種:C1,C2,…,C11。

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

3 有相似性自同構(gòu)的二元自對(duì)偶碼

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)型自同構(gòu)的二元自對(duì)偶碼[80,40,16]在等價(jià)情況下共有11種。

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

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

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

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

運(yùn)行Matlab程序，得到:

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

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

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

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

附中文參考文獻(xiàn)：

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

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

[6] 楊慶. 碼長(zhǎng)為38的二元自對(duì)偶極值碼[J]. 科技創(chuàng)新導(dǎo)報(bào),2011(35):76.

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

[10] 陸正福，李亞?wèn)|，王國(guó)棟.GF(2m)上線性碼自同構(gòu)群的進(jìn)一步研究[J].云南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011,23(6):401-404.

[11] 寧平. FPGA上實(shí)現(xiàn)CRC16糾錯(cuò)編碼并行計(jì)算的探討[J]. 計(jì)算機(jī)工程與科學(xué),2014,36(6):1023-1027.

王榮(1980-),女,山西晉城人，博士，講師，研究方向?yàn)榇鷶?shù)編碼。E-mail:wangrong101377@126.com

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

王俊新(1966-),男，山西呂梁人，博士，教授，研究方向?yàn)槿捍鷶?shù)。

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基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(70973072，70573066);山西財(cái)經(jīng)大學(xué)青年科研基金資助項(xiàng)目(晉財(cái)大校[2014]90號(hào))

TN911.22

A

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

通信地址：030006 山西省太原市山西財(cái)經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院

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