A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes. (English) Zbl 1380.94150
Summary: We tighten a key estimate, which dictates the computational complexity of Guruswami-Sudan algorithm, on the lower bound of the degrees of freedom, and then propose a modified decoding algorithm for Reed-Solomon codes beyond half the minimum distance. The computational complexity of the modified algorithm is lower than the Guruswami-Sudan algorithm for the medium to high rate Reed-Solomon codes, and has the same asymptotic complexity as the algorithm proposed by Wu. Besides we also claim that our modified algorithm outperforms Wu’s algorithm to some extent.
Keywords:
Reed-Solomon codes; list decoding algorithm; design of algorithms; computational complexityReferences:
| [1] | Berlekamp, E. R., Algebraic Coding Theory (1968), McGraw-Hill: McGraw-Hill New York · Zbl 0199.54101 |
| [2] | Duggan, A.; Barg, A., Performance analysis of algebraic soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inform. Theory, 54, 5012-5018 (Nov. 2008) · Zbl 1319.94110 |
| [3] | Elias, P., Error-correcting codes for list decoding, IEEE Trans. Inform. Theory, 37, 5-12 (Jan. 1991) · Zbl 0712.94021 |
| [4] | Gao, S.; Shokrollahi, M. A., Computing roots of polynomials over function fields of curves, unpublished manuscript, Aug. 1998. Available at |
| [5] | Gao, S., A new algorithm for decoding Reed-Solomon codes, (Communications, Information and Network Security, vol. 712 (2003), Kluwer Academic Publisher), 55-68 · Zbl 1330.94063 |
| [6] | Guruswami, V.; Sudan, M., Improved decoding of Reed-Solomon codes and algebraic-geometry codes, IEEE Trans. Inform. Theory, 45, 6, 1757-1767 (Sept. 1999) · Zbl 0958.94036 |
| [7] | Johnson, S. M., A new upper bound for error-correcting codes, IEEE Trans. Inform. Theory, 8, 203-207 (Apr. 1962) · Zbl 0102.34602 |
| [8] | Kötter, R., Fast generalized minimum-distance decoding of algebraic-geometry and Reed-Solomon codes, IEEE Trans. Inform. Theory, 42, 721-737 (May 1996) · Zbl 0861.94030 |
| [9] | Kötter, R.; Vardy, A., Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inform. Theory, 49, 11, 2809-2825 (Nov. 2003) · Zbl 1301.94159 |
| [12] | Massey, J. L., Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15, 122-127 (Jan. 1969) · Zbl 0167.18101 |
| [13] | McEliece, R. J., The Guruswami-Sudan decoding algorithm for Reed-Solomon codes, JPL progress report: 42-153, Apr. 2003. Available at |
| [14] | Roth, R.; Ruckenstein, G., Efficient decoding of Reed-Solomon codes beyond half the minimum distance, IEEE Trans. Inform. Theory, 46, 1, 246-257 (2000) · Zbl 1001.94046 |
| [15] | Sudan, M., Decoding of Reed-Solomon codes beyond the error-correction bound, J. Complexity, 13, 1, 180-193 (1997) · Zbl 0872.68026 |
| [16] | Wu, Y., New list decoding algorithms for Reed-Solomon and BCH codes, IEEE Trans. Inform. Theory, 54, 3611-3630 (Aug. 2008) · Zbl 1329.94103 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
