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

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

關(guān)鍵詞:二元自對偶碼 極值碼 重量計數(shù)子 自同構(gòu)

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

1 引言

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

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

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

為C的重量計數(shù)子。

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

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

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

C=C={v|vC}。

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

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

定理1:設(shè)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]形式的二元自對偶碼.其可能的重量計數(shù)子為:

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

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

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

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

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

(1)第一種方法

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

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

()[38，19，8]:

對于有:

它們都滿足重量計數(shù)子:

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

(2)第二種方法

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

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

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

它滿足重量計數(shù)子:

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

(3)第三種方法

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

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

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

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

()[36，18，8]:

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

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

(4)第四種方法

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

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

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

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

(5)第五種方法

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

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

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]宋文兔.具有三階自同構(gòu)的二元自對偶碼[D].吉林大學(xué):吉林大學(xué)數(shù)學(xué)學(xué)院，2006.

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