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

王 榮，王俊新

（山西財經大學應用數學學院，山西 太原030006）

1 引言

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

2 基本知識

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

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

引理1［11］C是有型p－（c，f）的自對偶編碼［n，n/2，d］，p是一個奇素數，定義g（k）＝d＋d/2＋…＋d/2k－1，則：

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

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

對長度為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 碼的構造

對長度為56的編碼，當具有型7－（8，0）時，自同構形式為：

σ＝（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｝，對?u∈F（σ），s，l∈Ωi，1≤i≤8，有us＝ul。定義映射（ηu）i＝uj，j∈Ωi，i＝1，2，…，8。把η（F（σ））稱為由C導出的收縮碼。顯然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。令Ij＝〈（x7＋1）/hj（x）〉，j＝0，1，2，則R＝I0⊕I1⊕I2。

對長度為7 的向量（a0，a1，…，a6），可看成R上的多項式a0＋a1x＋…＋a6x6［12］。設P是R上偶重量多項式的集合，則P＝I1⊕I2，且I1?I2?GF（23）。把I1和I2看成長度為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。根據文獻［11］得C＝F（σ）⊕E1（σ）⊕E2（σ）。對編碼C的每個元素u＝u1u2…u56，定義j＝1，2，…，8；Ei（σ）＊＝｛u＊｜u∈Ei（σ）｝，i＝1，2。令E（σ）＊＝E1（σ）＊⊕E2（σ）＊，?u∈E（σ）＊，有映射：E（σ）＊→P。由于C是二元雙偶極值碼，由文獻［3］知，η（F（σ））是一個［8，4］二元雙偶碼，［8，4］二元自對偶碼在等價情況下只有和A8兩種，的生成矩陣為：

A8的生成矩陣為：

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

引理2［13］兩個有相同自同構σ的雙偶極值碼C和C′是等價的充分必要條件是C可經過下列變換得到C′：

（1）7個8循環；

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

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

3.1 K＝2的情形

根據引理2，在等價情況下，K＝2時，E1（σ）＊的生成矩陣為：

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

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

定理1 當E1（σ）＊的維數為2時，不存在有7階自同構的二元雙偶極值碼［56，28，12］。

3.2 K＝4的情形

當E1（σ）＊的維數K＝4時，E1（σ）＊的生成矩陣為：

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

則碼長為56 的二元雙偶極值碼的生成矩陣為：

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

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

表2中＃代表7個0，例如當r、s、t、u、v、w、x、y取值為01＃000＃2時，E1（σ）＊所對應的生成矩陣為：

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

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

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

因此，得到如下定理：

定理2 當E1（σ）＊的維數K＝4 時，長度為56的有7－（8，0）型自同構的二元雙偶極值碼共有75種。

4 有相似型的雙偶極值碼

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

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

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

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

長度為60的雙偶極值碼的最小距離為12，對生成矩陣運行Matlab程序，得到與長度為56的雙偶極值碼相類似結論：

定理3 當E1（σ）＊的維數為2時，不存在有7階自同構的二元雙偶極值碼［60，30，12］。

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

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

定理5 當E1（σ）＊的維數為2時，不存在有7階自同構的二元雙偶極值碼［62，31，12］和［64，32，12］。

定理6 當E1（σ）＊的維數K＝4 時，長度為62的有7－（8，6）型自同構的二元雙偶極值碼共有2 308種。

定理7 當E1（σ）＊的維數K＝4 時，長度為64的有7－（8，8）型自同構的二元雙偶極值碼共有2 976種。

5 結束語

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

［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）

附中文參考文獻：

［1］ 寧平.FPGA 上實現CRC16糾錯編碼并行計算的探討［J］.計算機工程與科學，2014，36（6）：1023－1027.

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