Skip to Main content Skip to Navigation

On the Algorithms of Guruswami-Sudan List Decoding over Finite Rings

Guillaume Quintin 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 : This thesis studies the algorithmic techniques of list decoding, first proposed by Guruswami and Sudan in 1998, in the context of Reed-Solomon codes over finite rings. Two approaches are considered. First we adapt the Guruswami-Sudan (GS) list decoding algorithm to generalized Reed-Solomon (GRS) codes over finite rings with identity. We study in details the complexities of the algorithms for GRS codes over Galois rings and truncated power series rings. Then we explore more deeply a lifting technique for list decoding. We show that the latter technique is able to correct more error patterns than the original GS list decoding algorithm. We apply the technique to GRS code over Galois rings and truncated power series rings and show that the algorithms coming from this technique have a lower complexity than the original GS algorithm. We show that it can be easily adapted for interleaved Reed-Solomon codes. Finally we present the complete implementation in C and C++ of the list decoding algorithms studied in this thesis. All the needed subroutines, such as univariate polynomial root finding algorithms, finite fields and rings arithmetic, are also presented. Independently, this manuscript contains other work produced during the thesis. We study quasi cyclic codes in details and show that they are in one-to-one correspondence with left principal ideal of a certain matrix ring. Then we adapt the GS framework for ideal based codes to number fields codes and provide a list decoding algorithm for the latter.
Complete list of metadatas

Cited literature [154 references]  Display  Hide  Download
Contributor : Guillaume Quintin <>
Submitted on : Monday, December 3, 2012 - 1:16:45 AM
Last modification on : Friday, November 22, 2019 - 1:18:32 AM
Long-term archiving on: : Saturday, December 17, 2016 - 6:24:42 PM


  • HAL Id : pastel-00759820, version 1



Guillaume Quintin. On the Algorithms of Guruswami-Sudan List Decoding over Finite Rings. Information Theory [cs.IT]. Ecole Polytechnique X, 2012. English. ⟨pastel-00759820⟩



Record views


Files downloads