亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        最大距離可分碼的上界

        2011-01-31 06:13:06楊建生張運英王德秀
        上海大學學報(自然科學版) 2011年3期
        關(guān)鍵詞:上界碼字奇數(shù)

        楊建生, 張運英, 王德秀

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

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

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

        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)的方法進行研究.從組合學角度考慮,非線性碼的研究價值在于其應(yīng)該具有比線性碼更好的糾錯能力.因此,對于非線性MDS碼,研究人員提出了類似線性MDS碼的問題,即在參數(shù)k確定的前提下,(n,qk,n-k+1)MDS碼的最大碼長Mq(k)具有什么性質(zhì)?然而令人遺憾的是,研究Mq(k)的難度遠大于研究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碼的分割重量計數(shù)子(partition weight enumerator,PWE)和組合學方法研究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碼,其重量計數(shù)子[1]為

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

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

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

        2 MDS碼新的上界

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

        證明 采用反證法.

        假設(shè)C為一個包含零碼字的(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(β).又因為w(α)=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為一個包含零碼字的(q+k-2,ql,d)(q為偶數(shù))MDS碼,其中l(wèi)=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個不同的數(shù).

        因此,當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.結(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.

        猜你喜歡
        上界碼字奇數(shù)
        奇數(shù)湊20
        奇數(shù)與偶數(shù)
        關(guān)于奇數(shù)階二元子集的分離序列
        一個三角形角平分線不等式的上界估計
        放 下
        揚子江詩刊(2018年1期)2018-11-13 12:23:04
        數(shù)據(jù)鏈系統(tǒng)中軟擴頻碼的優(yōu)選及應(yīng)用
        一道經(jīng)典不等式的再加強
        放下
        揚子江(2018年1期)2018-01-26 02:04:06
        Nekrasov矩陣‖A-1‖∞的上界估計
        長為{4,5,6}的完備刪位糾錯碼的存在性*
        亚洲精品无码mv在线观看| 蜜桃免费一区二区三区| 亚洲综合图色40p| 人妻无码αv中文字幕久久琪琪布 美女视频黄的全免费视频网站 | 一本之道日本熟妇人妻| 一本大道av伊人久久综合| 中文字幕日韩精品无码内射| 亚洲小说图区综合在线| 在线视频日韩精品三区| 人妻少妇中文字幕在线观看| 无码精品久久久久久人妻中字| 国产乱子伦一区二区三区| 无码一区二区三区网站| 国产视频在线观看一区二区三区| 亚洲最近中文字幕在线| 风韵多水的老熟妇| 99福利在线| 亚洲视频在线中文字幕乱码| 蜜桃视频在线免费观看| 中年熟妇的大黑p| 中文AV怡红院| 国产一区二区三区尤物| 国产a√无码专区亚洲av| 亚洲的天堂av无码| 亚洲情精品中文字幕有码在线| 久久综合亚洲鲁鲁五月天| 国产又大又黑又粗免费视频| 欧美成人一区二区三区在线观看 | 亚洲中文字幕成人无码| 国产精在线| 中文字幕一区二区三区喷水| 国产成人91久久麻豆视频| 亚洲男人第一无码av网站| 99久久久无码国产精品动漫| 久久精品av在线视频| 97se狠狠狠狠狼鲁亚洲综合色| 国产精品成年片在线观看| 国产成人福利在线视频不卡| 黑人玩弄极品人妻系列视频| 无码国产69精品久久久久孕妇| 少妇人妻偷人精品一区二区|