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

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

https://pastel.archives-ouvertes.fr/pastel-00759820
Contributor : Guillaume Quintin <>
Submitted on : Monday, December 3, 2012 - 1:16:45 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM
Long-term archiving on : Saturday, December 17, 2016 - 6:24:42 PM

Identifiers

  • HAL Id : pastel-00759820, version 1

Collections

Citation

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

Share

Metrics

Record views

794

Files downloads

1184