編碼的構造與譯碼問題及其在密碼學中的應用
發(fā)布時間：2018-08-09 13:23
【摘要】：本論文主要研究代數(shù)編碼的構造與譯碼相關問題,及編碼理論在密碼學中的應用。 對于二元非對稱錯誤信道,非對稱即發(fā)送1接收0的概率遠大于發(fā)送0接收1的概率,與經(jīng)典編碼理論(基于對稱錯誤信道模型)相比,非對稱錯誤給研究帶來極大困難,然而這樣的信道又普遍存在,比如光通訊等。本文基于代數(shù)曲線構造了一類二元非對稱糾錯碼,取一些特殊的代數(shù)曲線,該構造給出的編碼的參數(shù)在漸進意義下都要優(yōu)于已有的結果。 Reed-Solomon碼是編碼理論中最重要的編碼之一,它的編碼方式很簡單,在工程中被廣泛應用,所以它的譯碼問題吸引了大批數(shù)學家與計算機學家的興趣。Cheng和Murray在2007年對于Reed-Solomon碼的深洞進行研究,他們發(fā)現(xiàn)了一類深洞,并猜想奇特征有限域時對于擴展Reed-Solomon碼(即賦值集合為D=Fq),這構成所有的深洞。之后洪紹方教授與他的博士生對于本原Reed-Solomon碼使用Fourier變換以及循環(huán)碼的知識發(fā)現(xiàn)了另一類深洞,但是他們的方法只能適用于這類特殊的Reed-Solomon碼。本文通過很簡單的方法對于一般的Reed-Solomon碼發(fā)現(xiàn)了新的一類深洞,推廣了洪教授他們的結果,Cheng等人最新的結果證明了在一些情形下只有這兩類深洞。本文對于偶特征時,除了以上兩類深洞外給出了新的一類深洞。另外,本文還研究擴展Reed-Solomon碼的k+2次多項式定義的深洞,證明沒有k+2次多項式定義的深洞,支持了Cheng和Murray最初的猜想。 迭代譯碼是常見譯碼方法之一,迭代譯碼中最重要的兩個概念是停止集及其分布,因為它們刻畫了迭代譯碼的效率。對于一些經(jīng)典的線性碼,目前已知停止集分布的也相當?shù)纳�。本文研究代�?shù)幾何碼的停止集及其分布。我們給出一般代數(shù)曲線構造的代數(shù)幾何碼的停止集兩個描述：一是使用Riemann-Roch空間的代數(shù)描述,二是使用除子(divisor)的幾何描述。這時發(fā)現(xiàn)存在一個區(qū)間(跟代數(shù)曲線的虧格有關),大小在這個區(qū)間外的停止集很容易得到,但是大小在這個區(qū)間內(nèi)的停止集很難確定。對于最簡單的代數(shù)幾何碼—廣義Reed-Solomon碼,此時不存在這個區(qū)間,所以它的停止集及其分布問題非常簡單。其次考慮橢圓曲線碼,它的停止集及其分布是非平凡的,并且本文用橢圓曲線的有理點群完全刻畫出其停止集。這樣,停止集及其分布、停止集距離問題都歸結到橢圓曲線有理點群上的子集和問題,于是就證明了對于一般的橢圓曲線碼,在隨機多項式時間歸約下計算它的停子集及其分布已經(jīng)是NP困難問題。對于更高虧格的代數(shù)幾何碼,我們還沒有太多結果,猜想它的停止集及其分布問題仍是NP困難問題。 編碼的極小距離完全刻畫了這個糾錯碼的檢錯與糾錯能力,所以希望構造出具有較大的極小距離的糾錯碼。對于有限域Fq上線性碼[n, k, d], Singleton界告訴我們極小距離d不會超過n-k+1。當d=n-k+1時,稱這個線性碼為極大距離可分(MDS)碼。著名的MDS猜想是說MDS碼的碼長n不會超過q+l(q為有限域Fq的大小),除了個別情況可以達到q+2。對于一般的線性碼,這個猜想是一個純組合問題,沒有太多方法,極其困難。不少學者開始考慮一些特殊的線性碼,特別地,代數(shù)幾何碼。對于橢圓曲線構造的代數(shù)幾何碼,利用橢圓曲線的幾何性質(zhì),MDS猜想已經(jīng)被證明。而對于高虧格的代數(shù)曲線構造的代數(shù)幾何碼,MDS猜想還沒有完全被解決。本文對于橢圓曲線構造的代數(shù)幾何碼,利用Li和Wan的篩法,給出一個簡單的組合的證明,并且如果對碼的維數(shù)k做細微的限制,我們證明MDS碼的碼長n不會超過(2/3+∈)q,這個結果比MDS猜想要強很多。 最后,論文給出編碼理論在密碼學中的一個簡單的應用。基于線性碼以及密鑰分享的思想,我們對于經(jīng)典多用戶通訊構造了一個信息論意義下無條件安全的消息認證體制。
[Abstract]:This paper mainly studies the construction and decoding of algebraic coding, and the application of coding theory in cryptography.
For two element asymmetric error channels, the probability of asymmetric transmission 1 receiving 0 is far greater than the probability of sending 0 to receive 1. Compared with the classical coding theory (based on symmetric error channel model), asymmetric error brings great difficulty to the study. However, such channels are common, such as optical communication. This paper is based on algebraic curves. A class of two element asymmetric error correcting codes is used to obtain some special algebraic curves. The parameters given by this structure are better than those obtained in the progressive sense.
Reed-Solomon code is one of the most important codes in the coding theory. Its encoding method is very simple and widely used in engineering. So its decoding problem attracts a large number of mathematicians and computer scientists' interest.Cheng and Murray in the deep hole of the Reed-Solomon code in 2007. They found a kind of deep hole, and guess strange. The extended Reed-Solomon code (i.e. the assignment set is D=Fq) when the characteristic finite field is characteristic, which makes all deep holes. Then professor Hong Shaofang and his doctoral student find another kind of deep hole for the original Reed-Solomon code using the knowledge of Fourier transform and cyclic code, but their square method can only be applied to this special Reed-Solomon code. In this paper, a new kind of deep hole is found for the general Reed-Solomon code by a simple method. The results of Professor Hong are popularized. The latest results of Cheng et al. Prove that there are only two kinds of deep holes in some cases. In this paper, a new kind of deep hole is given in addition to the two kinds of deep holes for the even characteristics. The deep holes defined by k+2 polynomials of Reed-Solomon codes prove that there is no deep hole defined by k+2 polynomials, which supports the initial conjecture of Cheng and Murray.
Iterative decoding is one of the common decoding methods. The two most important concepts in iterative decoding are the stop set and its distribution, because they characterize the efficiency of iterative decoding. For some classical linear codes, the known stop set distribution is quite small. This paper studies the stop set and its distribution of Algebraic Geometric Codes. Two description of the stop set of Algebraic Geometric Codes constructed by the number curve: one is to use the algebraic description of the Riemann-Roch space and the two is to use the geometric description of the divison (divisor). Then, it is found that there is an interval (related to the genus of algebraic curves), and the stop set size outside this interval is easily obtained, but the size is within this interval. The stop set is difficult to determine. For the simplest algebraic geometry code, generalized Reed-Solomon code, it does not exist at this time, so its stop set and its distribution problem are very simple. Secondly, the elliptic curve code is considered, its stop set and its distribution are nontrivial, and this paper completely portrays its stop by the rational point group of the elliptic curve. In this way, the stop set and its distribution and the stop set distance are all reduced to the subset and the problem on the rational point group of the elliptic curve. Therefore, it is proved that for the general elliptic curve code, it is NP difficult to calculate its stop subset and its distribution under the random polynomial time reduction. Without much result, it is still difficult for NP to guess its stopping set and its distribution.
The coded minimum distance fully portrays the error correction and error correction ability of the error correcting code, so we want to construct a error correcting code with a larger minimum distance. For the linear code [n, K, d], Singleton on the finite field Fq, we tell us that the minimum distance D does not exceed n-k+1. when d=n-k+1, and that this linear code is a maximum distance separable (MDS) code. The MDS conjecture of the name is that the code length n of the MDS code does not exceed the q+l (q is the size of the finite field Fq). In addition to a few cases, the conjecture can reach the general linear code. This conjecture is a pure combinatorial problem. There are not too many methods and extremely difficult. Many scholars begin to consider some special linear codes, especially, algebraic geometry code. For ellipse MDS conjecture has been proved by the geometric properties of the elliptic curve, and the MDS conjecture is not completely solved for the algebraic geometric code constructed by the algebraic curve of the high genus. In this paper, a simple combination of the Algebraic Geometric Codes constructed by the elliptical curve is given by the Li and Wan sieving methods. As for the slight restriction on the dimension k of the code, we prove that the code length of MDS code n will not exceed (2/3+ *) Q, which is much better than that of the MDS conjecture.
Finally, the paper gives a simple application of the coding theory in cryptography. Based on the idea of linear code and key sharing, we construct a message authentication system for unconditional security in the information theory for the classical multiuser communication.
【學位授予單位】：南開大學
【學位級別】：博士
【學位授予年份】：2014
【分類號】：TN918.1
本文編號：2174207
[Abstract]:This paper mainly studies the construction and decoding of algebraic coding, and the application of coding theory in cryptography.
For two element asymmetric error channels, the probability of asymmetric transmission 1 receiving 0 is far greater than the probability of sending 0 to receive 1. Compared with the classical coding theory (based on symmetric error channel model), asymmetric error brings great difficulty to the study. However, such channels are common, such as optical communication. This paper is based on algebraic curves. A class of two element asymmetric error correcting codes is used to obtain some special algebraic curves. The parameters given by this structure are better than those obtained in the progressive sense.
Reed-Solomon code is one of the most important codes in the coding theory. Its encoding method is very simple and widely used in engineering. So its decoding problem attracts a large number of mathematicians and computer scientists' interest.Cheng and Murray in the deep hole of the Reed-Solomon code in 2007. They found a kind of deep hole, and guess strange. The extended Reed-Solomon code (i.e. the assignment set is D=Fq) when the characteristic finite field is characteristic, which makes all deep holes. Then professor Hong Shaofang and his doctoral student find another kind of deep hole for the original Reed-Solomon code using the knowledge of Fourier transform and cyclic code, but their square method can only be applied to this special Reed-Solomon code. In this paper, a new kind of deep hole is found for the general Reed-Solomon code by a simple method. The results of Professor Hong are popularized. The latest results of Cheng et al. Prove that there are only two kinds of deep holes in some cases. In this paper, a new kind of deep hole is given in addition to the two kinds of deep holes for the even characteristics. The deep holes defined by k+2 polynomials of Reed-Solomon codes prove that there is no deep hole defined by k+2 polynomials, which supports the initial conjecture of Cheng and Murray.
Iterative decoding is one of the common decoding methods. The two most important concepts in iterative decoding are the stop set and its distribution, because they characterize the efficiency of iterative decoding. For some classical linear codes, the known stop set distribution is quite small. This paper studies the stop set and its distribution of Algebraic Geometric Codes. Two description of the stop set of Algebraic Geometric Codes constructed by the number curve: one is to use the algebraic description of the Riemann-Roch space and the two is to use the geometric description of the divison (divisor). Then, it is found that there is an interval (related to the genus of algebraic curves), and the stop set size outside this interval is easily obtained, but the size is within this interval. The stop set is difficult to determine. For the simplest algebraic geometry code, generalized Reed-Solomon code, it does not exist at this time, so its stop set and its distribution problem are very simple. Secondly, the elliptic curve code is considered, its stop set and its distribution are nontrivial, and this paper completely portrays its stop by the rational point group of the elliptic curve. In this way, the stop set and its distribution and the stop set distance are all reduced to the subset and the problem on the rational point group of the elliptic curve. Therefore, it is proved that for the general elliptic curve code, it is NP difficult to calculate its stop subset and its distribution under the random polynomial time reduction. Without much result, it is still difficult for NP to guess its stopping set and its distribution.
The coded minimum distance fully portrays the error correction and error correction ability of the error correcting code, so we want to construct a error correcting code with a larger minimum distance. For the linear code [n, K, d], Singleton on the finite field Fq, we tell us that the minimum distance D does not exceed n-k+1. when d=n-k+1, and that this linear code is a maximum distance separable (MDS) code. The MDS conjecture of the name is that the code length n of the MDS code does not exceed the q+l (q is the size of the finite field Fq). In addition to a few cases, the conjecture can reach the general linear code. This conjecture is a pure combinatorial problem. There are not too many methods and extremely difficult. Many scholars begin to consider some special linear codes, especially, algebraic geometry code. For ellipse MDS conjecture has been proved by the geometric properties of the elliptic curve, and the MDS conjecture is not completely solved for the algebraic geometric code constructed by the algebraic curve of the high genus. In this paper, a simple combination of the Algebraic Geometric Codes constructed by the elliptical curve is given by the Li and Wan sieving methods. As for the slight restriction on the dimension k of the code, we prove that the code length of MDS code n will not exceed (2/3+ *) Q, which is much better than that of the MDS conjecture.
Finally, the paper gives a simple application of the coding theory in cryptography. Based on the idea of linear code and key sharing, we construct a message authentication system for unconditional security in the information theory for the classical multiuser communication.
【學位授予單位】：南開大學
【學位級別】：博士
【學位授予年份】：2014
【分類號】：TN918.1
【相似文獻】
相關期刊論文 前10條
1 王加瑩;5490km Ultra Long Haul WDM System[J];光通信技術;2004年10期
2 張俊;符方偉;廖群英;;廣義Reed-Solomon碼的深洞[J];中國科學:數(shù)學;2013年07期
3 王勇;量子Reed-Solomon碼[J];福建電腦;2002年05期
4 Richard Huynh;葛寧;楊華中;;A Low Power Error Detection in the Syndrome Calculator Block for Reed-Solomon Codes: RS(204,188)[J];Tsinghua Science and Technology;2009年04期
5 張建文,王宏遠;Reed-Solomon碼的原理和軟硬件實現(xiàn)[J];電視技術;2001年07期
6 ;An Analysis and Design of the Virtual Simulation Software Based on Pattern[J];The Journal of China Universities of Posts and Telecommunications;2002年02期
7 忻鼎稼;Homogeneous Interpolation Problem and Key Equation for Decoding Reed-Solomon Codes[J];Science in China,Ser.A;1994年11期
8 ;Dr Solomon's FindVirus[J];互聯(lián)網(wǎng)周刊;1998年11期
9 徐小凡;譚千蓉;;關于標準Reed-Solomon碼的平凡碼字的注記[J];四川大學學報(自然科學版);2014年01期
10 王泉,馬旭東,齊春,羅新民;Reed-Solomon時域編、譯碼算法與AVR優(yōu)化實現(xiàn)[J];計算機工程與應用;2004年15期
相關會議論文 前1條
1 ;Iterative Decoding Algorithm for Interleaved RS Codes over Partial Response Channels[A];中國電子學會第十五屆信息論學術年會暨第一屆全國網(wǎng)絡編碼學術年會論文集（下冊）[C];2008年
相關重要報紙文章 前1條
1 特約編譯 王晉;新加坡亞太釀酒公司收購Solomon啤酒廠[N];華夏酒報;2011年
相關博士學位論文 前1條
1 張俊;編碼的構造與譯碼問題及其在密碼學中的應用[D];南開大學;2014年
相關碩士學位論文 前3條
1 張揚慶;Reed-Solomon糾錯碼研究及在Modbus通信協(xié)議中的應用[D];電子科技大學;2010年
2 鄧廣來;DVD伺服芯片中Reed-Solomon碼解碼器的研究與FPGA實現(xiàn)[D];大連海事大學;2005年
3 吳強;Reed-Solomon碼在無線問答信號設計中的應用[D];電子科技大學;2007年
，本文編號：2174207
本文鏈接：http://sikaile.net/kejilunwen/wltx/2174207.html
最近更新
教材專著
