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

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

2、論中最重要的編碼之一，它的編碼方式很簡單，在工程中被廣泛應用，所以它的譯碼問題吸引了大批數(shù)學家與計算機學家的興趣。Cheng和Murray在2007年對于Reed-Solomon碼的深洞進行研究，他們發(fā)現(xiàn)了一類深洞，并猜想奇特征有限域時對于擴展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é)果證明了在一些情形下只有這兩類深洞。本文對于偶特征時，除了以上兩類深洞外給出了新的一類深洞。另外，本文還研究擴展Reed-Solomon碼的k+2次多項式定義的深洞，證明沒有k+2次多項式定義的深洞，支持了Cheng和Murray最初的猜想。
　　迭代譯碼是常

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

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

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

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