论文标题:一类代数几何码的译码
Decoding of A Class of Algebraic Geometric Codes
论文作者 李宝
论文导师 肖国镇,论文学位 博士,论文专业 密码学
论文单位 西安电子科技大学,点击次数 896,论文页数 77页File Size2092k
1998-01-01论文网 http://www.lw23.com/lunwen_3388327/ 序列，递推关系，Berlekamp-Massey算法，大数表决，代数几 何码，伴随式，译码
sequence. recurring relation, Berlekamp-Massey algorithm. majority voting, algebraic-geometric code. syndrome, decoding
本文主要研究一类代数几何码的译码问题。在介绍了线性分组码、代数曲线、代数几何码的有关概念和性质后，首先深入研究了序列上递推关系的概念，引入了A-型递推关系的概念，建立了一致预言定理和广义Berlekamp-Massey算法以及大数表决方案。然后，在错误向量的伴随式序列上引入了一种A-型递推关系。最后，给出了一点代数几何码的一个有效译码算法。主要研究结果如下： （1）推广了序列上线性递推关系的概念，在序列上引入了一类新型递推关系——A-型递推关系。这类递推关系依赖于一族给定的多项式，一般说来是非线性的。 （2）引入了A-型递推关系的极小多项式集的概念以及刻划A-型速推关系长度的d-集的概念。 （3）对满足一定条件的A-型递推关系建立了一致预言定理等基础性定理。 （4）推广Berlekamp-Massey算法，对满足一定条件的A-型递推关系建立了广义Berlekamp-Massey算法并讨论了其复杂度。用这个算法，我们可以求出一个序列所满足的A-型递推关系的极小多项式集。 （5）对序列上的A-型递推关系建立了大数表决方案。 （6）对于一点代数几何码，研究了错误向量的伴随式序列。在其上引入了一种A-型递推关系。并用代数曲线的知识证明这种A-型递推关系的d-集的大小受到错误个数的限制。 （7）利用我们建立的广义Berlekamp-Massey算法和大数表决方案，将BCH码和Goppa码的译码算法推广，建立了一点代数几何码的一个有效译码算法，其复杂度达到目前国际同类算法的最好水平。
ABSTRACT The thesis is devoted to the decoding of a class of algebraic-geometric codes. After some conception and properties on linear block codes. algebraic curves and algebraic-geometric codes introduced, the conception of recurring relation on sequence is investigated, and the concept of A-type recurring relation is proposed. Then the agreement theorem and generalized Berlekamp-Massev algorithm as well as majority voting scheme are established. An A-type recurring relation is introduced on the syndrome sequence of an error vector. Lastly an efficient decoding algorithm is presented for one point algebraic-geometric codes. Main contributions of this work are as follows: (1) We generalize the concept of linear recurring relation and propose a new type of recurring relation on sequence-type recurring relation on sequence. This type of recurring relation depends on a group of given polynomials, and in general is non-linear. (2) We propose the concepts of minimal polynomial set of A-type of recurring relation and d-set which describes the length of .A-type recurring relation. (3) We establish some essential properties such as the agreement theorem etc. for A-type recurring relation satisfying some conditions. (4) By generalizing Berlekamp-Massey algorithm we develop a generalized Berlekamp-Massey algorithm for A-type recurring relation satisfying some conditions and discuss its complexity. Using the algorithm we can calculate a minimal polynom~al set of A-type recurring relation. (5) We develop a majority voting scheme for A-type recurring relation. (6) For one point algebraic-geometric codes we introduce an A-type recurring relation on the syndrome sequence of an error vector. And we show that the size of d-sets of the A-type recurring relation is limited by the number of errors by using knowledge of algebraic curves. (7) Using the generalized Berlekamp-Massey algorithm and majority voting scheme we present an efficient decoding algorithm for one point algebraic-geometric codes, whose complexity achieves the most advanced world standards in the same class of algorithms.
|
