On Generalized Reed-Solomon Codes Over Commutative and Noncommutative Rings

Abstract : In this paper we study generalized Reed-Solomon codes (GRS codes) over commutative, noncommutative rings, show that the classical Welch-Berlekamp and Guruswami-Sudan decoding algorithms still hold in this context and we investigate their complexities. Under some hypothesis, the study of noncommutative generalized Reed-Solomon codes over finite rings leads to the fact that GRS code over commutative rings have better parameters than their noncommutative counterparts. Also GRS codes over finite fields have better parameters than their commutative rings counterparts. But we also show that given a unique decoding algorithm for a GRS code over a finite field, there exists a unique decoding algorithm for a GRS code over a truncated power series ring with a better asymptotic complexity. Moreover we generalize a lifting decoding scheme to obtain new unique and list decoding algorithms designed to work when the base ring is for example a Galois ring or a truncated power series ring or the ring of square matrices over the latter ring.
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/hal-00670004
Contributor : Guillaume Quintin <>
Submitted on : Monday, February 20, 2012 - 2:28:46 PM
Last modification on : Thursday, July 4, 2019 - 9:54:02 AM
Long-term archiving on : Wednesday, December 14, 2016 - 6:48:45 AM

File

article.pdf
Files produced by the author(s)

Identifiers

Citation

Guillaume Quintin, Morgan Barbier, Christophe Chabot. On Generalized Reed-Solomon Codes Over Commutative and Noncommutative Rings. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2013, 59 (9), pp.5882-5897. ⟨10.1109/TIT.2013.2264797⟩. ⟨hal-00670004v2⟩

Share

Metrics

Record views

1041

Files downloads

1014