Abstract
This correspondence presents an algorithmic improvement to Sudan's list-decoding algorithm for Reed-Solomon codes and its generalization to algebraic-geometric codes from Shokrollahi and Wasserman. Instead of completely factoring the interpolation polynomial over the function field of the curve, we compute sufficiently many coefficients of a Hensel development to reconstruct the functions that correspond to codewords. We prove that these Hensel developments can be found efficiently using Newton's method. We also describe the algorithm in the special case of Reed-Solomon codes.
| Original language | English |
|---|---|
| Pages (from-to) | 2605-2614 |
| Number of pages | 10 |
| Journal | IEEE Transactions on Information Theory |
| Volume | 46 |
| Issue number | 7 |
| DOIs | |
| Publication status | Published - 1 Dec 2000 |
Keywords
- Algebraic-geometric codes
- Hensel lifting
- List decoding
- Newton's method
- Polynomials over algebraic function fields
- Reed-solomon codes