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

Two challenges in algebraic coding theory are addressed within this dissertation.The first one is the efficient hard- and soft-decision decoding of GeneralizedReed--Solomon codes over finite fields in Hamming metric. The motivation forthis more than 50 years old problem was renewed by the discovery of apolynomial-time interpolation-based decoding principle up to the Johnson radiusby Guruswami and Sudan at the end of the 20th century. First syndrome-basederror/erasure decoding approaches by Berlekamp--Massey and Sugiyama--Kasahara--Hirasawa--Namekawa for Generalized Reed--Solomon codes weredescribed by a Key Equation, i.e., a polynomial description of the decodingproblem. The reformulation of the interpolation-based approach in terms of KeyEquations is a central topic of this thesis. This contribution covers several aspectsof Key Equations for Generalized Reed--Solomon codes for both, thehard-decision variant by Guruswami--Sudan, as well as for the soft-decisionapproach by Kötter--Vardy. The obtained systems of linear homogeneousequations are structured and efficient decoding algorithms are developed. Thesecond topic of this dissertation is the formulation and the decoding up to lowerbounds on the minimum Hamming distance of linear cyclic block codes overfinite 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 cyclicproduct codes and code concatenation. We introduce cyclic generalized productcodes and indicate how they can be used to bound the minimum distance.Necessary and sufficient conditions for lowest-rate non-primitive binary cycliccodes of minimum distance two and a sufficient condition for binary cyclic codesof minimum distance three are worked out and their relevance for the embedding-technique is outlined. Furthermore, we give quadratic-time syndrome-basederror/erasure decoding algorithms up to some of our proposed bounds.