具有7－（8，0）型自同構(gòu)的二元雙偶極值碼＊

王 榮，王俊新

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

1 引言

無(wú)線數(shù)據(jù)傳輸是當(dāng)今通信領(lǐng)域中最為活躍的研究熱點(diǎn)之一［1］，隨著其蓬勃發(fā)展，對(duì)編碼糾錯(cuò)的精確位數(shù)和程度要求越來(lái)越高。自對(duì)偶編碼在編碼糾錯(cuò)中起著重要的作用。所有長(zhǎng)度不超過(guò)32的自對(duì)偶編碼的生成矩陣及其分類已全部解決［2，3］。對(duì)長(zhǎng)度大于32的編碼雖已有很多研究，但找出其生成矩陣和分類情況仍是很困難的。2012 年，Bouyuklieva S［4］對(duì)二元自對(duì)偶編碼［48，24，10］進(jìn)行討論，得到在等價(jià)情況下，共有264種3－（16，0）型的編碼。同年，Aguilar－Melchor C、Gaborit P和Kim J－L［5］證明了存在2 744種［38，19，8］，極值碼，兩個(gè)s－極值碼。2011年，Yorgov V［6，7］證明了對(duì)于有7階自同構(gòu)的二元極值碼［42，21，8］，在等價(jià)情況下只有29種。2005年，Bouyuklieva S、Yankov N 和Russeva R［8］證 明 了 有3 階 自 同 構(gòu) 的 二 元 自對(duì)偶碼［42，21，8］恰 好 有16 607 種。2005 年，Goodwin V 和Yorgov V［9］證明了至少存在70種長(zhǎng)度為88的雙偶極值碼。本文對(duì)碼長(zhǎng)為50到70之間的二元雙偶極值碼進(jìn)行研究。

2 基本知識(shí)

二元的［n，k］編碼C是指二元域GF（2n）上的k維線性子空間，n稱為編碼的碼長(zhǎng)。C的每個(gè)元素稱為一個(gè)碼字。對(duì)編碼C的每一個(gè)碼字u＝（u1，u2，…，un），其重量wt（u）是u的非零位的位數(shù)。兩個(gè) 碼 字u＝（u1，u2，…，un）和v＝（v1，v2，…，vn）的距離指它們?cè)趯?duì)應(yīng)位取值不同的位數(shù)，用dis（u，v）表示，dis（u，v）＝wt（u－v）。最小距離為d的［n，k］編碼稱為［n，k，d］編碼。對(duì)一個(gè)編碼C，令C⊥＝｛v｜（u，v）＝0，?u∈C｝（（u，v）為GF（2n）上的內(nèi)積），如果C＝C⊥，則C在該內(nèi)積下自對(duì)偶。

對(duì)［n＝2k，k，d］二元自對(duì)偶碼，若其碼字的重量都是4的倍數(shù)，則稱該編碼是雙偶編碼。對(duì)一個(gè)長(zhǎng)度為n的雙偶編碼的距離d≤4［n/24］＋4，若等號(hào)成立，編碼是極值碼［10］。?σ∈Sn（Sn為n階對(duì)稱群），?u∈C，定義uσ＝（uσ（1），uσ（2），…，uσ（n）），則Cσ和C是等價(jià)的。如果Cσ＝C，σ就是編碼C的一個(gè)自同構(gòu)，C的所有自同構(gòu)形成了Sn的一個(gè)子群，稱之為C的自同構(gòu)群，用AUT（C）表示。設(shè)置換σ∈AUT（C），若σ的階為奇素?cái)?shù)p，有c個(gè)獨(dú)立的循環(huán)和f個(gè)固定點(diǎn)，則這個(gè)置換具有型p－（c，f）。

引理1［11］C是有型p－（c，f）的自對(duì)偶編碼［n，n/2，d］，p是一個(gè)奇素?cái)?shù)，定義g（k）＝d＋d/2＋…＋d/2k－1，則：

（1）pc≥g（（p－1）c/2），如果d≤2［（p－1）c/2］－2，等號(hào)不滿足；

（2）若f＞c，則f＞g（（f－c）/2），若d≤2［（f－c）/2］－2，等號(hào)不滿足。

對(duì)長(zhǎng)度為56 的二元雙偶碼討論，得到p－（c，f）只有以下幾種可能：3－（18，2），3－（16，8），3－（14，14），5－（10，6），7－（8，0），7－（7，7），13－（4，4）。本文考慮有型為7－（8，0）的二元雙偶極值碼。

3 碼的構(gòu)造

對(duì)長(zhǎng)度為56的編碼，當(dāng)具有型7－（8，0）時(shí)，自同構(gòu)形式為：

σ＝（1，2，…，7）（8，9，…，14）…（50，51，…，56）

令Ω1＝（1，2，…，7），Ω2＝（8，9，…，14），Ω8＝（50，51，…，56）。

令F（σ）＝｛u∈C｜uσ＝u｝，對(duì)?u∈F（σ），s，l∈Ωi，1≤i≤8，有us＝ul。定義映射（ηu）i＝uj，j∈Ωi，i＝1，2，…，8。把η（F（σ））稱為由C導(dǎo)出的收縮碼。顯然F（σ）由收縮碼η（F（σ））唯一確定。

令R＝GF（2）［x］/〈x7＋1〉，x是 不 定 元，〈x7＋1〉是x7＋1 生成的理想。x7＋1＝h0（x）h1（x）h2（x），其中，h0（x）＝x＋1，h1（x）＝x3＋x2＋1，h2（x）＝x3＋x＋1。令I(lǐng)j＝〈（x7＋1）/hj（x）〉，j＝0，1，2，則R＝I0⊕I1⊕I2。

對(duì)長(zhǎng)度為7 的向量（a0，a1，…，a6），可看成R上的多項(xiàng)式a0＋a1x＋…＋a6x6［12］。設(shè)P是R上偶重量多項(xiàng)式的集合，則P＝I1⊕I2，且I1?I2?GF（23）。把I1和I2看成長(zhǎng)度為7的編碼，表1給出I0、I1和I2的元素，α和γ是I1和I2的本原元。

Table 1 Elements of I0，I1and I2表1 I0、I1 和I2 的元素

令Ei（σ）＝｛u∈C｜且有u｜Ωj∈Ii，1≤j≤8｝，i＝1，2。根據(jù)文獻(xiàn)［11］得C＝F（σ）⊕E1（σ）⊕E2（σ）。對(duì)編碼C的每個(gè)元素u＝u1u2…u56，定義j＝1，2，…，8；Ei（σ）＊＝｛u＊｜u∈Ei（σ）｝，i＝1，2。令E（σ）＊＝E1（σ）＊⊕E2（σ）＊，?u∈E（σ）＊，有映射：E（σ）＊→P。由于C是二元雙偶極值碼，由文獻(xiàn)［3］知，η（F（σ））是一個(gè)［8，4］二元雙偶碼，［8，4］二元自對(duì)偶碼在等價(jià)情況下只有和A8兩種，的生成矩陣為：

A8的生成矩陣為：

由于二元雙偶極值碼的碼字重量都為4的倍數(shù)，顯然η（F（σ））等價(jià)于A8。

引理2［13］兩個(gè)有相同自同構(gòu)σ的雙偶極值碼C和C′是等價(jià)的充分必要條件是C可經(jīng)過(guò)下列變換得到C′：

（1）7個(gè)8循環(huán)；

（2）在E1（σ）＊的列中，用α的冪取代原來(lái)的值；

（3）在（E1（σ）＊）中，用xt取代x，1≤t≤6。

3.1 K＝2的情形

根據(jù)引理2，在等價(jià)情況下，K＝2時(shí)，E1（σ）＊的生成矩陣為：

此時(shí)，E2（σ）＊的生成矩陣為：

把A8生成矩陣中的粗體的1和0分別用7個(gè)1和7個(gè)0代替［14］，E1（σ）＊、E2（σ）＊、生成矩陣中的每個(gè)元素對(duì)應(yīng)一個(gè)3×7的循環(huán)矩陣，且這個(gè)矩陣的第一行對(duì)應(yīng)于生成矩陣中的元素在表1的一個(gè)7維數(shù)組。這樣我們得到了二元雙偶極值碼在K＝2 的生成矩陣。經(jīng)過(guò)運(yùn)用Matlab程序，不論i、j、k、l取什么值，該生成矩陣生成的編碼最小距離均為8，故得到：

定理1 當(dāng)E1（σ）＊的維數(shù)為2時(shí)，不存在有7階自同構(gòu)的二元雙偶極值碼［56，28，12］。

3.2 K＝4的情形

當(dāng)E1（σ）＊的維數(shù)K＝4時(shí)，E1（σ）＊的生成矩陣為：

對(duì)應(yīng)E2（σ）＊的生成矩陣為：

則碼長(zhǎng)為56 的二元雙偶極值碼的生成矩陣為：

前4行粗體的1和0都表示元素全為1和0的1×7的行向量，后8行的每一個(gè)元素都代表一個(gè)3×7的循環(huán)矩陣，且循環(huán)矩陣αi，γj（i，j＝0，r，s，t，u，v，w，x，y｜r，s，t，u，v，w，x，y∈｛0，1，…，6｝）的第一行對(duì)應(yīng)表1中的元素。粗體0表示3×7的零矩陣，運(yùn)行Matlab程序，得到當(dāng)r、s、t、u、v、w、x、y取表2中的值時(shí)，二元雙偶極值碼的最小距離確為12。

Table 2 Values of r，s，t，u，v，w，x，y表2 r，s，t，u，v，w，x，y的取值

表2中＃代表7個(gè)0，例如當(dāng)r、s、t、u、v、w、x、y取值為01＃000＃2時(shí)，E1（σ）＊所對(duì)應(yīng)的生成矩陣為：

E2（σ）＊的生成矩陣為：

長(zhǎng)度為56的二元雙偶極值碼的生成矩陣如圖1所示。

Figure 1 Generator matrix of the extremal self－dual doubly－even binary codes with length of 56圖1 長(zhǎng)度為56的二元雙偶極值碼的生成矩陣

因此，得到如下定理：

定理2 當(dāng)E1（σ）＊的維數(shù)K＝4 時(shí)，長(zhǎng)度為56的有7－（8，0）型自同構(gòu)的二元雙偶極值碼共有75種。

4 有相似型的雙偶極值碼

由引理2知，對(duì)長(zhǎng)度為60 的有7－（8，4）型的雙偶極值碼，η（Fσ（C））是一個(gè)［12，6］碼，根據(jù)文獻(xiàn)［3］，［12，6］二元自對(duì)偶碼在等價(jià)情況下只有三種和B12。的生成矩陣為：

在該生成矩陣中，粗體的0代表1×7的零向量，黑體的1代表1×7的行向量，且所有元素全為1，其余的1和0僅表示自身。

因?yàn)橛?－（8，4）型自同構(gòu)的長(zhǎng)度為60的雙偶極值碼最小距離為12。顯然η（Fσ（C））不等價(jià)于同樣的討論可得η（Fσ（C））不等價(jià)因此，η（Fσ（C））一定等價(jià)于B12。E1（σ）＊、E2（σ）＊的生成矩陣同上。有7－（8，4）型自同構(gòu)的長(zhǎng)度為60的雙偶極值碼的生成矩陣如下：

注：該生成矩陣后8 行中黑體元素與碼長(zhǎng)為56的二元雙偶極值碼生成矩陣中后8行的元素一致。

長(zhǎng)度為60的雙偶極值碼的最小距離為12，對(duì)生成矩陣運(yùn)行Matlab程序，得到與長(zhǎng)度為56的雙偶極值碼相類似結(jié)論：

定理3 當(dāng)E1（σ）＊的維數(shù)為2時(shí)，不存在有7階自同構(gòu)的二元雙偶極值碼［60，30，12］。

定理4 當(dāng)E1（σ）＊的維數(shù)K＝4 時(shí)，長(zhǎng)度為60的有7－（8，4）型自同構(gòu)的二元雙偶極值碼共有3種（r、s、t、u、v、w、x、y取值為最后三個(gè)值時(shí)）。

由引理1知，長(zhǎng)度為66、68、70的碼，都不存在有7－（8，m）（m＝10，12，14）型的自同構(gòu)。對(duì)長(zhǎng)度為62和64的雙偶極值碼進(jìn)行相似討論，得：

定理5 當(dāng)E1（σ）＊的維數(shù)為2時(shí)，不存在有7階自同構(gòu)的二元雙偶極值碼［62，31，12］和［64，32，12］。

定理6 當(dāng)E1（σ）＊的維數(shù)K＝4 時(shí)，長(zhǎng)度為62的有7－（8，6）型自同構(gòu)的二元雙偶極值碼共有2 308種。

定理7 當(dāng)E1（σ）＊的維數(shù)K＝4 時(shí)，長(zhǎng)度為64的有7－（8，8）型自同構(gòu)的二元雙偶極值碼共有2 976種。

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

本文針對(duì)線性碼中長(zhǎng)度為50到60之間的雙偶極值碼進(jìn)行討論，試圖找出其生成矩陣和分類情況，但對(duì)長(zhǎng)度較長(zhǎng)的線性碼，要找到這樣的線性碼非常困難。長(zhǎng)度越長(zhǎng)，碼字的復(fù)雜程度越高，因此總是限定其有一個(gè)特殊的自同構(gòu)來(lái)進(jìn)行討論。根據(jù)特殊自同構(gòu)將它分成幾個(gè)長(zhǎng)度較短的線性碼的直和，來(lái)得到其生成矩陣和分類情況。長(zhǎng)度為52的線性碼最小距離為10，它不存在雙偶極值碼，長(zhǎng)度為56、60、62和64的雙偶極值碼分別有7－（8，0）型、7－（8，4）型、7－（8，6）型和7－（8，8）型的自同構(gòu)。本文得到了這些情形下的生成矩陣及分類情況，這些對(duì)解碼工作的發(fā)展有著積極意義。對(duì)長(zhǎng)度更長(zhǎng)的雙偶極值碼和這些碼的應(yīng)用是本文作者研究的下一個(gè)目標(biāo)。

［1］ Ning Ping.Exploration for parallel computing of CRC16checksum on FPGA［J］.Computer Engineering ＆Science，2014，36（6）：1023－1027.（in Chinese）

［2］ Huffman W C.On the classification and enumeration of selfdual codes［J］.Finite Fields and Their Appplications，2005，11（3）：451－490.

［3］ Pless V.A classification of self－orthogonal codes overGF（2）［J］.Discrete Math，1972，3：209－246.

［4］ Bouyuklieva S，Yankov N，Kim J.Classification of binary selfdual［48，24，10］codes with an automorphism of odd prime order［J］.Finite Fields and Their Applications，2012，18（6）：1104－1113.

［5］ Aguilar－Melchor C，Gborita P，Kim J－L，et al.Classification of extremal and s－extremal binary self－dual codes of length 38［J］.IEEE Transactions on Information Theory，2012，58（4）：2253－2262.

［6］ Yorgov V.The extremal codes of length 42 with automorphism of order 7［J］.Discrete Mathematics，1998，190：201－213.

［7］ Yorgov V.Erratum to“The extremal codes of length 42 with automorphism of order 7”［J］.Discrete Mathematics，2011，311：1860－1861.

［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］ Goodwin V，Yorgov V.New extremal self－dual doubly－even binary codes of length 88［J］.Finite Fields and Their Applications，2005，11（1）：1－5.

［10］ Conway J H，Sloane N J A.A new upper bound on the minimal distance of self－dual codes［J］.IEEE Transactions on Information Theory，1990，36（6）：1319－1333.

［11］ Yorgov V Y.Binary self－dual codes with automorphism of odd order［J］.Problems of Inform Transmission，1983，19：11－24.

［12］ Han S，Kim J－L，Lee H，et al.Construction of quasi－cyclic self－dual codes［J］.Finite Fields and Their Applications，2012，18（3）：613－633.

［13］ Bouyuklieva S，Bouyukliev I.An algorithm for classification of binary self－dual codes［J］.IEEE Transactions on Information Theory，2012，58（6）：3933－3940.

［14］ 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－48.（in Chinese）

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

［1］ 寧平.FPGA 上實(shí)現(xiàn)CRC16糾錯(cuò)編碼并行計(jì)算的探討［J］.計(jì)算機(jī)工程與科學(xué)，2014，36（6）：1023－1027.

［14］ 王榮，王俊新.有（17，3，1）型的二元自對(duì)偶編碼［52，26，10］［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（19）：46－48.