List decoding of algebraic-geometric codes

Author

Shokrollahi, M. Amin ; Wasserman, Hal

Author_Institution

AT&T Bell Labs., Murray Hill, NJ, USA

Volume

45

Issue

2

fYear

1999

fDate

3/1/1999 12:00:00 AM

Firstpage

432

Lastpage

437

Abstract

We generalize Sudan´s (see J. Compl., vol.13, p.180-93, 1997) results for Reed-Solomon codes to the class of algebraic-geometric codes, designing algorithms for list decoding of algebraic geometric codes which can decode beyond the conventional error-correction bound (d-1)/2, d being the minimum distance of the code. Our main algorithm is based on an interpolation scheme and factorization of polynomials over algebraic function fields. For the latter problem we design a polynomial-time algorithm and show that the resulting overall list-decoding algorithm runs in polynomial time under some mild conditions. Several examples are included

Keywords

algebraic geometric codes; decoding; interpolation; polynomials; Reed-Solomon codes; Sudan´s results; algebraic function fields; algebraic-geometric codes; error-correction bound; interpolation; linear code; list-decoding algorithm; minimum distance; polynomial-time algorithm; polynomials factorization; Algorithm design and analysis; Computer science; Computer science education; Decoding; Encoding; Galois fields; Interpolation; Linear code; Poles and zeros; Polynomials;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/18.748993

Filename

748993