Algebraic Soft- and Hard-Decision Decoding of Generalized Reed--Solomon and Cyclic Codes
Résumé
Two challenges in algebraic coding theory are addressed within this dissertation. The first one is the efficient hard- and soft-decision decoding of Generalized Reed--Solomon codes over finite fields in Hamming metric. The motivation for this more than 50 years old problem was renewed by the discovery of a polynomial-time interpolation-based decoding principle up to the Johnson radius by Guruswami and Sudan at the end of the 20th century. First syndrome-based error/erasure decoding approaches by Berlekamp--Massey and Sugiyama--Kasahara--Hirasawa--Namekawa for Generalized Reed--Solomon codes were described by a Key Equation, i.e., a polynomial description of the decoding problem. The reformulation of the interpolation-based approach in terms of Key Equations is a central topic of this thesis. This contribution covers several aspects of Key Equations for Generalized Reed--Solomon codes for both, the hard-decision variant by Guruswami--Sudan, as well as for the soft-decision approach by Kötter--Vardy. The obtained systems of linear homogeneous equations are structured and efficient decoding algorithms are developed. The second topic of this dissertation is the formulation and the decoding up to lower bounds on the minimum Hamming distance of linear cyclic block codes over finite fields. The main idea is the embedding of a given cyclic code into a cyclic (generalized) product code. Therefore, we give an extensive description of cyclic product codes and code concatenation. We introduce cyclic generalized product codes and indicate how they can be used to bound the minimum distance. Necessary and sufficient conditions for lowest-rate non-primitive binary cyclic codes of minimum distance two and a sufficient condition for binary cyclic codes of minimum distance three are worked out and their relevance for the embedding-technique is outlined. Furthermore, we give quadratic-time syndrome-based error/erasure decoding algorithms up to some of our proposed bounds.
Deux défis de la théorie du codage algébrique sont traités dans cette thèse. Le premier est le décodage efficace (dur et souple) de codes de Reed--Solomon généralisés sur les corps finis en métrique de Hamming. La motivation pour résoudre ce problème vieux de plus de 50 ans a été renouvelée par la découverte par Guruswami et Sudan à la fin du 20ème siècle d'un algorithme polynomial de décodage jusqu'au rayon Johnson basé sur l'interpolation. Les premières méthodes de décodage algébrique des codes de Reed--Solomon généralisés faisaient appel à une équation clé, c'est à dire, une description polynomiale du problème de décodage. La reformulation de l'approche à base d'interpolation en termes d'équations clés est un thème central de cette thèse. Cette contribution couvre plusieurs aspects des équations clés pour le décodage dur ainsi que pour la variante décodage souple de l'algorithme de Guruswami--Sudan pour les codes de Reed--Solomon généralisés. Pour toutes ces variantes un algorithme de décodage efficace est proposé. Le deuxième sujet de cette thèse est la formulation et le décodage jusqu'à certaines bornes inférieures sur leur distance minimale de codes en blocs linéaires cycliques. La caractéristique principale est l'intégration d'un code cyclique donné dans un code cyclique produit (généralisé). Nous donnons donc une description détaillée du code produit cyclique et des codes cycliques produits généralisés. Nous prouvons plusieurs bornes inférieures sur la distance minimale de codes cycliques linéaires qui permettent d'améliorer ou de généraliser des bornes connues. De plus, nous donnons des algorithmes de décodage d'erreurs/d'effacements [jusqu'à ces bornes] en temps quadratique.
Loading...