編碼的構(gòu)造與譯碼問題及其在密碼學(xué)中的應(yīng)用.pdf

1、本論文主要研究代數(shù)編碼的構(gòu)造與譯碼相關(guān)問題，及編碼理論在密碼學(xué)中的應(yīng)用。
　　對于二元非對稱錯(cuò)誤信道，非對稱即發(fā)送1接收0的概率遠(yuǎn)大于發(fā)送0接收1的概率，與經(jīng)典編碼理論（基于對稱錯(cuò)誤信道模型）相比，非對稱錯(cuò)誤給研究帶來極大困難，然而這樣的信道又普遍存在，比如光通訊等。本文基于代數(shù)曲線構(gòu)造了一類二元非對稱糾錯(cuò)碼，取一些特殊的代數(shù)曲線，該構(gòu)造給出的編碼的參數(shù)在漸進(jìn)意義下都要優(yōu)于已有的結(jié)果。
　　Reed-Solomon碼是編碼理

2、論中最重要的編碼之一，它的編碼方式很簡單，在工程中被廣泛應(yīng)用，所以它的譯碼問題吸引了大批數(shù)學(xué)家與計(jì)算機(jī)學(xué)家的興趣。Cheng和Murray在2007年對于Reed-Solomon碼的深洞進(jìn)行研究，他們發(fā)現(xiàn)了一類深洞，并猜想奇特征有限域時(shí)對于擴(kuò)展Reed-Solomon碼（即賦值集合為D=Fq），這構(gòu)成所有的深洞。之后洪紹方教授與他的博士生對于本原Reed-Solomon碼使用Fourier變換以及循環(huán)碼的知識發(fā)現(xiàn)了另一類深洞，但是他們的

3、方法只能適用于這類特殊的Reed-Solomon碼。本文通過很簡單的方法對于一般的Reed-Solomon碼發(fā)現(xiàn)了新的一類深洞，推廣了洪教授他們的結(jié)果，Cheng等人最新的結(jié)果證明了在一些情形下只有這兩類深洞。本文對于偶特征時(shí)，除了以上兩類深洞外給出了新的一類深洞。另外，本文還研究擴(kuò)展Reed-Solomon碼的k+2次多項(xiàng)式定義的深洞，證明沒有k+2次多項(xiàng)式定義的深洞，支持了Cheng和Murray最初的猜想。
　　迭代譯碼是常

4、見譯碼方法之一，迭代譯碼中最重要的兩個(gè)概念是停止集及其分布，因?yàn)樗鼈兛坍嬃说g碼的效率。對于一些經(jīng)典的線性碼，目前已知停止集分布的也相當(dāng)?shù)纳?。本文研究代?shù)幾何碼的停止集及其分布。我們給出一般代數(shù)曲線構(gòu)造的代數(shù)幾何碼的停止集兩個(gè)描述:一是使用Riemann-Roch空間的代數(shù)描述，二是使用除子(divisor)的幾何描述。這時(shí)發(fā)現(xiàn)存在一個(gè)區(qū)間（跟代數(shù)曲線的虧格有關(guān)），大小在這個(gè)區(qū)間外的停止集很容易得到，但是大小在這個(gè)區(qū)間內(nèi)的停止集很難確

5、定。對于最簡單的代數(shù)幾何碼一廣義Reed-Solomon碼，此時(shí)不存在這個(gè)區(qū)間，所以它的停止集及其分布問題非常簡單。其次考慮橢圓曲線碼，它的停止集及其分布是非平凡的，并且本文用橢圓曲線的有理點(diǎn)群完全刻畫出其停止集。這樣，停止集及其分布、停止集距離問題都?xì)w結(jié)到橢圓曲線有理點(diǎn)群上的子集和問題，于是就證明了對于一般的橢圓曲線碼，在隨機(jī)多項(xiàng)式時(shí)間歸約下計(jì)算它的停子集及其分布已經(jīng)是NP困難問題。對于更高虧格的代數(shù)幾何碼，我們還沒有太多結(jié)果，猜想它

6、的停止集及其分布問題仍是NP困難問題。
　　編碼的極小距離完全刻畫了這個(gè)糾錯(cuò)碼的檢錯(cuò)與糾錯(cuò)能力，所以希望構(gòu)造出具有較大的極小距離的糾錯(cuò)碼。對于有限域Fq上線性碼[n，k，d]，Singleton界告訴我們極小距離d不會(huì)超過n-k+1。當(dāng)d=n-k+1時(shí)，稱這個(gè)線性碼為極大距離可分(MDS)碼。著名的MDS猜想是說MDS碼的碼長n不會(huì)超過q+1(q為有限域Fq的大小)，除了個(gè)別情況可以達(dá)到q+2。對于一般的線性碼，這個(gè)猜想是一個(gè)純組

7、合問題，沒有太多方法，極其困難。不少學(xué)者開始考慮一些特殊的線性碼，特別地，代數(shù)幾何碼。對于橢圓曲線構(gòu)造的代數(shù)幾何碼，利用橢圓曲線的幾何性質(zhì)，MDS猜想已經(jīng)被證明。而對于高虧格的代數(shù)曲線構(gòu)造的代數(shù)幾何碼，MDS猜想還沒有完全被解決。本文對于橢圓曲線構(gòu)造的代數(shù)幾何碼，利用Li和Wan的篩法，給出一個(gè)簡單的組合的證明，并且如果對碼的維數(shù)k做細(xì)微的限制，我們證明MDS碼的碼長n不會(huì)超過(2/3+∈)q，這個(gè)結(jié)果比MDS猜想要強(qiáng)很多。