List Decoding of Reed-Solomon Codes from a Groebner Basis Perspective

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The interpolation step of Guruswami and Sudan's list decoding of Reed-Solomon codes poses the problem of finding the minimal polynomial of an ideal with respect to a certain monomial order. An efficient algorithm that solves the problem is presented based on the theory of Groebner bases of modules. In a special case, this algorithm reduces to a simple Berlekamp-Massey-like decoding algorithm.
submitted to the Journal of Symbolic Computation; Shortened and revised version

Keywords

Commutative Algebra, Combinatorics, 13P10; 68W30

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/143939

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0601022
 http://arxiv.org/abs/math/0601022

Collections

arXiv