Skip to Main content Skip to Navigation

Algebraic Soft- and Hard-Decision Decoding of Generalized Reed--Solomon and Cyclic Codes

Alexander Zeh 1, 2 
1 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : 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.
Complete list of metadata

Cited literature [194 references]  Display  Hide  Download
Contributor : Alexander Zeh Connect in order to contact the contributor
Submitted on : Friday, October 11, 2013 - 11:10:46 AM
Last modification on : Thursday, January 20, 2022 - 5:29:34 PM
Long-term archiving on: : Friday, April 7, 2017 - 2:58:22 AM


  • HAL Id : pastel-00866134, version 1



Alexander Zeh. Algebraic Soft- and Hard-Decision Decoding of Generalized Reed--Solomon and Cyclic Codes. Computational Complexity [cs.CC]. Ecole Polytechnique X, 2013. English. ⟨pastel-00866134⟩



Record views


Files downloads