最大距離可分碼的上界

楊建生， 張運(yùn)英， 王德秀

(1.上海大學(xué)理學(xué)院，上海200444;2.上海市亭新中學(xué)，上海201505)

設(shè)q，n，k為整數(shù)，且n≥k，A={0，1，2，…，q-1}(模q)為加法群.(n，qk，d)表示A上含有qk個(gè)碼字且最小漢明距離為d的碼.如果d=n-k+1，則稱其為A上最大距離可分碼，即MDS碼.MDS碼是組合數(shù)學(xué)研究的重要內(nèi)容，Macwilliams等［1］認(rèn)為：MDS碼是編碼理論中最令人著迷的一章內(nèi)容.

MDS碼一般分為線性和非線性.由于線性MDS碼具有良好的代數(shù)結(jié)構(gòu)與幾何結(jié)構(gòu)，因此，可以借助線性代數(shù)與有限幾何的方法進(jìn)行研究，其中特別引人注目的是“編碼理論中的主猜想”的研究.

1 符號說明及MDS碼的基本結(jié)果

設(shè)A為域，mq(k)表示A上的線性MDS碼(n，qk，n-k+1)的最大碼長，即mq(k)=max{n|存在A上(n，qk，n-k+1)MDS碼}，則關(guān)于mq(k)的“編碼理論主猜想”為

由于此猜想在編碼理論與有限幾何的研究中具有重要意義，因此，關(guān)于mq(k)的研究［2］十分豐富.

對于非線性MDS碼，由于其缺乏良好的代數(shù)與幾何結(jié)構(gòu)，因此，很難找到系統(tǒng)的方法進(jìn)行研究.從組合學(xué)角度考慮，非線性碼的研究價(jià)值在于其應(yīng)該具有比線性碼更好的糾錯(cuò)能力.因此，對于非線性MDS碼，研究人員提出了類似線性MDS碼的問題，即在參數(shù)k確定的前提下，(n，qk，n-k+1)MDS碼的最大碼長Mq(k)具有什么性質(zhì)?然而令人遺憾的是，研究Mq(k)的難度遠(yuǎn)大于研究mq(k).迄今為止，關(guān)于Mq(k)的研究［3-8］十分零散，并且主要采用有限幾何的方法，其中有關(guān)Mq(k)的研究結(jié)果可概括為定理1和定理2.

定理1［7］(1)設(shè)k≥3，q＞2，如果存在(q+ k-1，qk，q)MDS碼，則4整除q;

(2)設(shè)k＞3，q＞2，如果存在(q+k-1，qk，q) MDS碼，則36整除q.

定理2［4］(1)對于(n，qk，d)MDS碼，如果36不整除q，且k≥4，則n≤q+k-3;

(2)如果q＞2，且q≡2(mod 4)，則(q+1，q3，q-1)MDS碼不存在.

由于MDS碼縮短后仍為MDS碼，因此，有如下引理：

引理1 Mq(k)≤Mq(k-1)+1.

本研究利用 MDS碼的分割重量計(jì)數(shù)子(partition weight enumerator，PWE)和組合學(xué)方法研究Mq(k)，得到了Mq(k)一些新的上界.特別地，得到了Mq(q-1)≤q+1(q為奇數(shù))，Mq(q-1)≤q+2 (q≡4(mod 6))，Mq(q-2)≤q+1(q≡4(mod 6))，Mq(k)≤q+k-3(q≡36(mod 180)，且k≥6).

為了討論方便，下面引入一些符號和基本結(jié)果.

(3)對于A上的(n，qk，d)MDS碼，其重量計(jì)數(shù)子［1］為

式中，w≥d.由文獻(xiàn)［9］可知，式(1)不僅對線性的MDS碼成立，對含有零碼字的一般MDS碼也成立.

關(guān)于分割重量計(jì)數(shù)子，有如下定理成立.

文獻(xiàn)［10］在定理3的證明中假設(shè)A為域，但其證明與A是否為域無關(guān)，也與MDS碼是否為線性碼無關(guān)，只用到該MDS碼含有零碼字這個(gè)條件.因此，該定理對所有包含零碼字的MDS碼都成立.

2 MDS碼新的上界

定理4 設(shè)q為奇數(shù)，則Mq(q-1)≤q+1.

證明 采用反證法.

假設(shè)C為一個(gè)包含零碼字的(q+2，qq-1，4)(q為奇數(shù))MDS碼.考慮分割Γ=N1∪N2，其中N1= {1，2}.由定理3，得

不失一般性，可以假設(shè)a=1，b=1.

設(shè)α，β∈C1，1，且α≠β.如果存在i∈Supp(α)∩Supp(β)，且 i≠1，2，則{1，2，i}?Supp(α)∩Supp(β).又因?yàn)閣(α)=w(β)=4，則有d(α，β)≤3，矛盾.因此，Supp(α)∩Supp(β)={1，2}.

通過以上討論，可得

定理5 設(shè)k≥4，如果q是偶數(shù)，且(k-1)!不整除(q+k-4)…(q+1)q(q-2)，則Mq(k)≤q+ k-3，Mq(q-2)≤q+k-3.

證明 采用反證法.

假設(shè)C為一個(gè)包含零碼字的(q+k-2，ql，d)(q為偶數(shù))MDS碼，其中l(wèi)=k或者l=q-2，則

考慮分割Γ=N1∪N2，其中N1={1，2}.由定理3，可得

成立.

情況1 當(dāng)l=k時(shí).

情況2 當(dāng)l=q-2時(shí).

令Bj1，j2，…，jk-3={α∈C1，1|ji∈Supp(α)，i=1，2，…，k-3}，其中j1，j2，…，jk-3為集合{3，4，…，q+ k-2}中k-3個(gè)不同的數(shù).

因此，當(dāng)l=k或l=q-2時(shí)，有

通過定理5，可以得到如下推論.

推論1 Mq(q-2)≤q+1(q≡4(mod 6)).

推論2 Mq(q-2)≤q+3(q≡6或26(mod 30)).

推論3 Mq(q-2)≤q+5(q≡8或36(mod 42)).

推論4 Mq(q-1)≤q+2(q≡4(mod 6)).

證明 由引理1，知Mq(k)≤Mq(k-1)+1.結(jié)合推論1，有Mq(q-1)≤Mq(q-2)+1=q+2(q≡4(mod 6)).

推論5 Mq(k)≤q+k-3(q≡36(mod 180)，且k≥6).

證明 如果k=6，由定理5知Mq(6)≤q+3 (q≡36(mod 180)).結(jié)合引理1，有Mq(k)≤q+k-3(q≡36(mod 180)，且k≥6).

［1］ MACWILLIAMSF J，SLOANEN J A.The theory of errorcorrecting codes［M］.Amsterdam：North-Holland Publishing Co，1977：317-329.

［2］ HIRSCHFELDJ W P.The main conjecture for MDS codes，lecture notes in computerscience［C］∥Proceedings of the 5th IMA Conference on Cryptography and Coding.1995：44-52.

［3］ ALDERSONT L.On MDS codes and Bruen-Silverman codes［D］.Ontario：University of Western Ontario，2002.

［4］ ALDERSONT L.Extending MDS codes［J］.Annals of Combinatorics，2005，9：125-135.

［5］ ALDERSONT L，BRUENA A.Codes from cubic curves and their extensions［J］.The Electronic Journal of Combinatorics，2008，15(1)：R42.

［6］ BRUCKR H，RYSERH J.The nonexistence of certain finite projective planes［J］.Canada J Math，1949(1)：88-93.

［7］ BRUENA A，SILVERMANR.On the nonexistence of certain MDS codes and projective planes［J］.Math Z，1983，183：171-175.

［8］ SILVERMAN R.A metrization forpower-setswith applications to combinatorial analysis［J］.Canad J Math，1960，12：58-176.

［9］ TOLHUIZENL M G M.On maximum distance separable codes over alphabets of arbitrary size［C］∥Proceedings of the 1994 IEEE International Symposium on Information Theory.1994：431.

［10］ EL-KHAMYM，MCELIECER J.The partition weight enumerator of MDS codes and its applications［C］∥Proceedings of the 2005 International Symposium on Information Theory.2005：926-930.