Publication Details
Title: Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound
Author: M. A. Shokrollahi and H. Wasserman
Group: ICSI Technical Reports
Date: June 1998
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1998/tr-98-019.pdf
Overview:
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. Keywords: Algebraic geometric codes, Reed-Solomon codes, decoding.
Bibliographic Information:
ICSI Technical Report TR-98-019
Bibliographic Reference:
M. A. Shokrollahi and H. Wasserman. Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound. ICSI Technical Report TR-98-019, June 1998
Author: M. A. Shokrollahi and H. Wasserman
Group: ICSI Technical Reports
Date: June 1998
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1998/tr-98-019.pdf
Overview:
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. Keywords: Algebraic geometric codes, Reed-Solomon codes, decoding.
Bibliographic Information:
ICSI Technical Report TR-98-019
Bibliographic Reference:
M. A. Shokrollahi and H. Wasserman. Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound. ICSI Technical Report TR-98-019, June 1998