Abstract
Under polynomial time reduction, the maximum likelihood decoding of a linear code is equivalent to computing the error distance of a received word. It is known that the decoding complexity of standard Reed-Solomon codes at certain radius is at least as hard as the discrete logarithm problem over certain large finite fields. This implies that computing the error distance is hard for standard Reed-Solomon codes. Using the Weil bound and a new sieve for distinct coordinates counting, we are able to compute the error distance for a large class of received words. This significantly improves previous results in this direction. As a corollary, we also improve the existing results on the Cheng-Murray conjecture about the complete classification of deep holes for standard Reed-Solomon codes.
This work is partially supported by NSF of the USA and by the National Natural Science Foundation of China (Grant No.60910118 and 61133013).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berlekamp, E., Welch, L.: Error correction of algebraic block codes. U.S. Patent Number 4633470 (1986)
Cafure, A., Matera, G., Privitelli, M.: Singularities of symmetric hypersurfaces and an application to Reed-Solomon codes. arXiv 1109.2265v1 (September 10, 2011)
Cheng, Q., Murray, E.: On Deciding Deep Holes of Reed-Solomon Codes. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol. 4484, pp. 296–305. Springer, Heidelberg (2007)
Cheng, Q., Wan, D.: On the list and bounded distance decodability of Reed-Solomon codes. SIAM J. Comput. 37(1), 195–209 (2007)
Cheng, Q., Wan, D.: Complexity of decoding positive-rate Reed-Solomon codes. IEEE Trans. Inform. Theory 56(10), 5217–5222 (2010)
Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inform. Theory 45(6), 1757–1767 (1995)
Guruswami, V., Vardy, A.: A Maximum-likelihood decoding of Reed-Solomon codes is NP-Hard. IEEE Trans. Inform. Theory 51(7), 2249–2256 (2005)
Li, J.Y., Wan, D.: On the subset sum problem over finite fields. Finite Fields Appl. 14, 911–929 (2008)
Li, J.Y., Wan, D.: A new sieve for distinct coordinate counting. Science China Mathematics 53(9), 2351–2362 (2010)
Li, J.Y., Wan, D.: Counting subset sums of finite abelian groups. Journal of Combinatorial Theory Series A 119(1) (January 2012)
Li, J.Y., Wan, D.: On error distance of Reed-Solomon codes. Science in China Mathematics 51(11), 1982–1988 (2008)
Liao, Q.: On Reed-Solomon Codes. Chinese Annals of Mathematics Series B 32B(1), 89–98 (2011)
Sudan, M.: Decoding of Reed-Solomon codes beyond the error-correction bound. J. Complexity 13, 180–193 (2007)
Wan, D.: Generators and irreducible polynomials over finite fields. Mathematics of Computation 66, 119–1212 (1997)
Zhu, G., Wan, D.: An asymptotic formula for counting subset sums over subgroups of finite fields. Finite Fields Appl. (2011), doi:10.1016/j.ffa.2011.07.010
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhu, G., Wan, D. (2012). Computing Error Distance of Reed-Solomon Codes. In: Agrawal, M., Cooper, S.B., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2012. Lecture Notes in Computer Science, vol 7287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29952-0_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-29952-0_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29951-3
Online ISBN: 978-3-642-29952-0
eBook Packages: Computer ScienceComputer Science (R0)