最大距離可分碼的上界

楊建生， 張運英， 王德秀

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

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

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

1 符號說明及MDS碼的基本結果

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

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

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

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

(2)設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碼的分割重量計數子(partition weight enumerator，PWE)和組合學方法研究Mq(k)，得到了Mq(k)一些新的上界.特別地，得到了Mq(q-1)≤q+1(q為奇數)，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).

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

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

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

關于分割重量計數子，有如下定理成立.

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

2 MDS碼新的上界

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

證明 采用反證法.

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

不失一般性，可以假設a=1，b=1.

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

通過以上討論，可得

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

證明 采用反證法.

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

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

成立.

情況1 當l=k時.

情況2 當l=q-2時.

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

因此，當l=k或l=q-2時，有

通過定理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.結合推論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)).結合引理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.