亚洲免费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}的完備刪位糾錯碼的存在性*
        亚洲自偷自拍熟女另类| 国产高清无码在线| 精品福利一区| 欧洲人体一区二区三区| 永久免费中文字幕av| 国产在线拍偷自拍偷精品| 亚洲AV无码未成人网站久久精品| 99亚洲精品久久久99| 又黄又爽又色的视频| 国产精品一久久香蕉国产线看观看| 精品亚洲成a人在线观看青青| 天下第二社区在线视频| 亚洲午夜福利在线观看| 天天爽夜夜爽人人爽曰喷水| 97精品国产高清自在线看超 | 极品少妇被后入内射视| 日本高清不卡二区三区| 国产午夜精品久久精品| 久久精品av在线观看| 国产偷国产偷亚洲高清视频| 国产精品视频亚洲二区| 天堂中文官网在线| 国语对白做受xxxxx在线中国| 天天躁日日躁狠狠躁av中文| 欧美老妇与禽交| 精品高清国产乱子伦| 美女狂喷白浆网站视频在线观看| 国产91精品一区二区麻豆亚洲 | 精品国产性色无码av网站| 99精品国产综合久久久久五月天| 区二区欧美性插b在线视频网站 | 国产婷婷丁香五月麻豆| 亚洲一区二区三区中文视频| 中文字幕无线精品亚洲乱码一区| 亚洲色图偷拍自拍亚洲色图| 久久精品国产亚洲av专区| 久久久黄色大片免费看| 少妇激情av一区二区三区| 特级毛片a级毛片100免费播放| 亚洲永久无码7777kkk| 亚洲深深色噜噜狠狠爱网站|