On Reed-Solomon codes

Abstract

The complexity of decoding the standard Reed-Solomon code is a well-known open problem in coding theory. The main problem is to compute the error distance of a received word. Using the Weil bound for character sum estimate, Li and Wan showed that the error distance can be determined when the degree of the received word as a polynomial is small. In the first part, the result of Li and Wan is improved. On the other hand, one of the important parameters of an error-correcting code is the dimension. In most cases, one can only get bounds for the dimension. In the second part, a formula for the dimension of the generalized trace Reed-Solomon codes in some cases is obtained.

Keywords

Reed-Solomon code / Weil bound / Error distance / Rational function / Trace Reed-Solomon code / Trace map

References

[1] Cheng Q., Murray E.. On deciding deep holes of Reed-Solomon codes, Proceedings of TAMC 2007, 2007, Berlin: Springer-Verlag 296-305

[2] Cheng, Q. and Wan, D. Q., On the list and bounded distance decodibility of the Reed-Solomon codes (extended abstract), Proc. 45th IEEE Symp. On Foundation of Comp. Sciences (FOCS), Rome, 2004, 335–341.

[3] Cheng Q., Wan D. Q.. On the list and bounded distance decodibility of Reed-Solomon codes. SIAM J. Comput., 2007, 37(1): 195-209

[4] Cheng Q., Wan D. Q.. Complexity of decoding positive rate Reed-Solomon codes, 35-th International Colloquium on Automata, Languages and Programming (ICALP08), 2008, Berlin: Springer-Verlag 283-293

[5] Guruswami V., Sudan M.. Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theorey, 1999, 45(6): 1757-1767

[6] Henning S.. Algebraic Functions Fields and Codes, 1993, Berlin, Heidelberg, New York: Springer-Verlag

[7] Guruswami V., Vardy A.. Maximal-likelihood decoding of Reed-Solomon codes is NP-hard. IEEE Transactions on Information Theory, 2005, 51(7): 2249-2256

[8] Li J. Y., Wan D. Q.. On the subset sum problem over finite fields. Finite Fields and Appl., 2008, 14(4): 911-929

[9] Li Y. J., Wan D. Q.. On error distance of Reed-Solomon codes. Sci. China Ser. A, 2008, 51(11): 1982-1988

[10] Macwilliams F. J., Sloane N. J.. The Theory of Error-Correcting Codes, 1983, Amsterdam: North-Holland

[11] Sudan M.. Decoding of Reed-Solomon codes beyond the error-correction bound. J. Complexity, 1997, 13: 180-193

[12] van der Vlugt M.. On the dimension of trace codes. IEEE Transactions on Information Theory, 1991, 37(1): 196-199

[13] van der Vlugt M.. A new upper bound for the dimension of trace codes. Bull. London Math. Soc., 1991, 23: 395-400

[14] Wan D. Q.. Generators and irreducible polynomials over finite fields. Mathematics of Computation, 1997, 66: 1195-1212