碼長為38的二元自對偶極值碼

摘 要:自對偶碼是一類重要的線性碼，它也是人們研究得最多的碼之一。本文主要介紹碼長為38的二元自對偶碼。由于碼長為38時，二元自對偶碼的總數太大，要將全部的二元自對偶碼計算出并進行完全分類是不現實的。因此，本文主要介紹其中具有特殊性質的碼，尤其是極值碼。碼長為38時，Gaborit估計至少存在900個極值碼.本文將介紹五種構造極值碼的方法，迄今為止這些方法已經構造出369種極值碼，但如何將碼長為38的所有極值碼進行完全分類還是一個沒有解決的問題。

關鍵詞:二元自對偶碼 極值碼 重量計數子 自同構

中圖分類號:O174文獻標識碼:A文章編號:1674-098X(2011)12(b)-0076-02

1 引言

設F=GF(2)={0，1}表示二元域，Fn上的k維子空間C稱為[n，k]線性碼。設C為F上的[n，k]線性碼，若C的極小重量為d，則稱C為F上的[n，k，d]線性碼，以該子空間的基向量為行的矩陣稱為該線性碼的生成矩陣。對于F上的[n，k]線性碼C，如果其對偶碼C┻滿足:C┻=C，則稱C為自對偶碼。

在編碼理論中重量計數子也是十分重要的。設C為F上的[n，k]線性碼，A0，A1，…，An分別為C中重量為0，1，…，n的碼字的個數，稱(A0，A1，…，An)為C的重量分布.設Y為變元，稱n次多項式

W(Y)=A0+A1Y+…+AnYn

為C的重量計數子。

對于F上的[n，k]線性碼C和C，稱它們等價是指存在n階置換使得

若C′與C等價，則C′與C有相同的重量計數子，特別地有相同的極小重量，因此在編碼理論中，對于等價的碼不作區分。

設C是長n的二元自對偶碼，是n次對稱群Sn中的置換，如果

C=C={v|vC}。

則稱是C的一個自同構，C的全體自同構構成了Sn的一個子群，稱為C的自同構群，設p為奇素數，一個n階置換稱為是p-(c，f)型的，如果具有c個p循環和f=n-cp個不動點。

F上的[n，k，d]線性碼C，其極小重量d代表了碼的糾錯能力，是衡量碼的性質好壞的一個重要指標，關于二元自對偶碼的極小重量d的上界，Rains給出了如下重要結論:

定理1:設C為[n=2k，k，d]二元自對偶碼，則當n≡22(mod24)時，

d≤4+6;否則，d≤4+4.

如果二元自對偶碼C的極小重量d使得定理1中的等號成立，則稱C為極值碼(extremal)。

對于長38的二元自對偶極值碼。由定理1知其極小重量的最大值為8，即極值碼為[38，19，8]形式的二元自對偶碼.其可能的重量計數子為:

W1=1+171Y8+1862Y10+10374Y12+36765Y14+…

W2=1+203Y8+1702Y10+10598Y12+36925Y14+…

迄今為止人們已經構造出369個不等價的[38，19，8]二元自對偶極值碼，但如何將碼長為38的所有極值碼進行完全分類還是一個沒有解決的問題。特別地，人們對具有p-(c，f)型自同構的自對偶極值碼進行研究，得到了一些比較好的結果:具有19-(2，0)型自同構的極值碼有1個等價類;具有7-(5，3)型自同構的極值碼有7個等價類;具有5-(6，8)型自同構的極值碼不存在。Huffman給出了所有可能的3-(c，f)值，分別為3-(6，20)，3-(8，14)，3-(10，8)以及3-(12，2)，但是它們所對應的極值碼的分類問題都尚未解決。

2 碼長為38的二元自對偶極值碼

在[38，19]二元自對偶碼的研究中，主要有下列幾種方法構造自對偶碼并得到其中的極值碼。

(1)第一種方法

具有DC或BDC構造的極值碼的構造和分類。如果一個[2k，k]線性碼有一個生成矩陣為G=()，則稱它為具有DC構造;如果一個[2k，k]線性碼有一個生成矩陣為G=稱為具有BDC構造，其中為k階單位矩陣，為k-1階循環矩陣，具有BDC構造的生成矩陣只適用于的情況。

1990年Conway和Slone給出了[38，19，8]二元自對偶碼和。對于有:

()[38，19，8]:

對于有:

它們都滿足重量計數子:

W1=1+171Y8+1862Y10+10374Y12+36765Y14+…

(2)第二種方法

1995年M.Harada和Kimura利用下面命題構造出了一個[38，19，8]二元自對偶極值碼。

命題2.1:設，則為長的自對偶碼生成矩陣，其中是二元域上的階方陣，，其中是B的第i行。

由它可得當時，其生成[38，19，8]二元自對偶極值碼。其中，的首行是(1001111010100001100)的循環矩陣。

它滿足重量計數子:

W2=1+203Y8+1702Y10+10598Y12+36925Y14+…

(3)第三種方法

命題2.2:設是的子集，若，則為奇數;若，則為偶數若為長的自對偶碼的生成矩陣，則為長的自對偶碼的生成矩陣，，其中若，則，否則。

由該命題中的方法我們可以很容易地從碼長為2n的自對偶碼得到很多不同的碼長為2n+2的自對偶碼的生成矩陣。

MasakiHarada在已有的長36的二元自對偶碼的基礎上構造了40個新的不等價的長38的二元自對偶碼，給出了這些碼滿足的重量計數子，并給出了這些碼的自同構群的階數。

下面給出碼長為36的自對偶極值碼和。

()[36，18，8]:

由和，并利用命題2.2中的方法，可以找到40種[38，19，8]二元自對偶極值碼。這40個極值碼以及和的不等價性已經由Magma所驗證。

定理2.1:對于[36，18，8]單偶自對偶碼至少有12個不等價極值碼，[38，19，8]單偶自對偶碼至少有43個不等價極值碼。

(4)第四種方法

2001年Jon-LarkKim改進了命題2.2的方法，得到了此方法的一般形式。

命題2.3:設為的子集且為偶數，為長的自對偶碼的生成矩陣。設為的特征向量，即若，則，否則。令 ·這里的·表示向量的內積，和分別是和的第行，則為長自對偶碼C的生成矩陣。

利用命題2.3，Jon-LarkKim構造了325個新的不等價的長38的二元自對偶極值碼，給出了這些碼所滿足的重量計數子并給出了這些碼的自同構群的階數。

定理2.2對于[36，18，8]單偶自對偶碼至少有14個不等價極值碼，[38，19，8]單偶自對偶碼至少有368個不等價極值碼。

(5)第五種方法

文獻[5]中，宋文兔構造出了所有具有3-(12，2)型自同構的[38，19，8]二元自對偶碼的生成矩陣，參見文獻[5]中的定理2.3。

在文獻[6]中，樊繼秋通過三個程序，并利用定理2.3得出的二元自對偶碼構造出其中的[38，19，8]極值碼，并得出該極值碼的重量計數子為

W2=1+203Y8+1702Y10+10598Y12+36925Y14+…

同時還證明了這里所得到的與以前的368個極值碼均不等價，因此，它是一個新的[38，19，8]二元自對偶極值碼.這也解決了3-(12，2)型的[38，19，8]二元自對偶極值碼的存在性問題。

參考文獻

[1]Conway J.H，Sloane N.J.A.A new upper bound on the minimal distance of self-dual codes[J].IEEE Trans.Inform，1990，Theory IT-36:1319～1333.

[2]Harada M，Kimua H.On Extremal self-dual Codes[J].Math.J.Okayama Univ，1995，1～14.

[3]Harada M.New Extremal self-dual Codes of Length 36， 38[J].IEEE Trans. Inform，1999，45(7):2541～2543.

[4]Kim Jon-Lark.New Extremal self-dual Codes of Length 36，38 anda 58[J].IEEE Trans.Inform，2001，47(1): 386～393.

[5]宋文兔.具有三階自同構的二元自對偶碼[D].吉林大學:吉林大學數學學院，2006.

[6]樊繼秋.二元自對偶極值碼[D].吉林大學:吉林大學數學學院，2007.