Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound

TitleDecoding Algebraic-Geometric Codes Beyond the Error-Correction Bound
Publication TypeTechnical Report
Year of Publication1998
AuthorsM. Shokrollahi, A., & Wasserman H.
Other Numbers1140
KeywordsAlgebraic geometric codes, decoding, Reed-Solomon codes
Abstract

We generalize Sudan's results for Reed-Solomon codes to the class of algebraic-geometric codes, designing polynomial-time algorithms which decode beyond the error-correction bound (d-1)/2, where d is the minimum distance of the code. We introduce [n,k,e,b]_q-codes, which are linear [n,k]_q-codes such that any Hamming sphere of radius e contains at most b codewords. Using the sequence of Garcia-Stichtenoth function fields, we construct sequences of constant-rate [n,k,e,b]_q-codes for which e/n tends to epsilon>1/2 as n grows large, while b and q remain fixed. Equivalently, we specify arbitrarily large constant-rate codes over a fixed field F_q such that a codeword is efficiently, non-uniquely reconstructible after more than half of its letters have been arbitrarily corrupted. Additionally, we discover a very simple algorithm for conventional decoding of AG-codes. Furthermore, we construct codes such that a codeword is uniquely and efficiently reconstructible after more than half of its letters have been corrupted by noise which is random in a specified sense. We summarize our results in terms of bounds on asymptotic parameters, giving a new characterization of decoding beyond the traditional error-correction bound.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1998/tr-98-019.pdf
Bibliographic Notes

ICSI Technical Report TR-98-019

Abbreviated Authors

M. A. Shokrollahi and H. Wasserman

ICSI Publication Type

Technical Report