Limits to list decoding Reed-Solomon codes

ABSTRACT

In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Reed-Solomon codes.

1. Given n distinct elements α1,...,αn from a field F, and n subsets S1,...,Sn of F each of size at most l, the list decoding algorithm of Guruswami and Sudan [7] can in polynomial time output all polynomials p of degree at most k which satisfy p(αi) ∈ Si for every i, as long as l < ⌈ n/k ⌉. We show that the performance of this algorithm is the best possible in a strong sense; specifically, we show that when l = ⌈ n/k ⌉, the list of output polynomials can be super-polynomially large in n. One way to interpret our result is the following. The algorithm in [7] can, when given as input $n'$ distinct pairs (βi,∈i) ∈ F² (the βi's need not be distinct), find and output all degree k polynomials p such that p(βi) = γi for at least $t$ values of i, provided t > √k n'. By our result, an improvement to the Reed-Solomon list decoder of [7] that works with slightly smaller agreement, say t > √kn' - k/2, can only be obtained by exploiting some property of the βi's (for example, their (near) distinctness).
2. For Reed-Solomon codes of block length $n$ and dimension k where k = n^δ for small enough δ, we exhibit an explicit received word r with a super-polynomial number of Reed-Solomon codewords that agree with it on $(2 - ε) k locations, for any desired ε > 0 (we note agreement of k is trivial to achieve). Such a bound was known earlier only for a non-explicit center. We remark that finding explicit bad list decoding configurations is of significant interest --- for example the best known rate vs. distance trade-off is based on a bad list decoding configuration for algebraic-geometric codes [14] which is unfortunately not explicitly known.

REFERENCES

• 1: Elwyn Berlekamp. Algebraic Coding Theory. McGraw-Hill Series in Systems Science, 1968.
• 2: Qi Cheng , Daqing Wan, On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.335-341, October 17-19, 2004 [doi>10.1109/FOCS.2004.46]
• 3: Ilya Dumer, Daniele Micciancio, and Madhu Sudan. Hardness of approximating the minimum distance of a code. IEEE Transactions on Information Theory, 49(1):22--37, January 2003.
• 4: Andrew Granville. The arithmetic properties of binomial coefficients. In http://www.cecm.sfu.ca/organics/papers/granville/, 1996.
• 5: Venkatesan Guruswami, Johan Hastad, Madhu Sudan, and David Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory, 48:1021--1035, May 2002.
• 6: V. Guruswami , P. Indyk, Expander-Based Constructions of Efficiently Decodable Codes, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.658, October 14-17, 2001
• 7: Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757--1767, 1999.
• 8: Venkatesan Guruswami and Madhu Sudan. Extensions to the Johnson Bound. Manuscript; available from http://theory.lcs.mit.edu/~madhu/papers.html, 2000.
• 9: F. J. MacWilliams and Neil J. A. Sloane. The Theory of Error-Correcting Codes. Elsevier/North-Holland, Amsterdam, 1981.
• 10: Jørn Justesen and Tom Høholdt. Bounds on list decoding of MDS codes. IEEE Transactions on Information Theory, 47(4):1604--1609, May 2001.
• 11: Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]
• 12: Amnon Ta-Shma and David Zuckerman. Extractor Codes. IEEE Transactions on Information Theory, 50(12):3015--3025, 2004.
• 13: J. H. Van Lint, Introduction to Coding Theory, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 14: Chaoping Xing. Nonlinear codes from algebraic curves improving the Tsfasman-Vladut-Zink bound. IEEE Transactions on Information Theory, 49(7):1653--1657, 2003.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
BCH codes, Johnson bound, Reed-Solomon codes, list decoding, list recovering