Citation
Abstract
This article is a tutorial discussion of the Guruswami–Sudan (GS) Reed–Solomon decoding algorithm, including self-contained treatments of the Ko¨tter and Roth– Ruckenstein (RR) improvements. It also contains a number of new results, including a rigorous discussion of the average size of the decoder’s list, an improvement in the RR algorithm’s stopping rule, a simplified treatment of the combinatorics of weighted monomial orders, and a proof of the monotonicity of the GS decoding radius as a function of the interpolation multiplicity.
Details
- Volume
- 42-153
- Published
- May 15, 2003
- Pages
- 1–60
- File Size
- 399.5 KB