Explicit capacity-achieving list-decodable codes

ABSTRACT

For every 0 < R < 1 and ε > 0, we present an explicit construction of error-correcting codes of rate R that can be list decoded in polynomial time up to a fraction (1-R-ε) of errors. These codes achieve the "capacity" for decoding from adversarial errors, i.e., achieve the optimal trade-off between rate and error-correction radius. At least theoretically, this meets one of the central challenges in coding theory.Prior to this work, explicit codes achieving capacity were not known for any rate R. In fact, our codes are the first to beat the error-correction radius of 1-√R, that was achieved for Reed-Solomon (RS) codes in [9], for all rates R. (For rates R < 1/16, Parvaresh and Vardy [12] had recently improved upon the 1-√R bound; for R → 0, their algorithm can decode a fraction 1-O(R log(1/R)) of errors.)Our codes are simple to describe --- they are certain folded Reed-Solomon codes, which are in fact exactly RS codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, since the codes we propose are not too far from the ones in actual use.The main insight in our work is that some carefully chosen folded RS codes are "compressed" versions of a related family of Parvaresh-Vardy codes. Further, the decoding of the folded RS codes can be reduced to list decoding the related Parvaresh-Vardy codes. The alphabet size of these folded RS codes is polynomial in the block length. This can be reduced to a constant that depends on the distance ε to capacity using ideas concerning "list recovering" and expander-based codes from [7, 8]. Concatenating the folded RS codes with suitable inner codes also gives us polytime constructible binary codes that can be efficiently list decoded up to the Zyablov bound.

REFERENCES

• 1: P. Elias. List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT, 1957.
• 2: P. Elias. Error-correcting codes for list decoding. IEEE Transactions on Information Theory, 37:5--12, 1991.
• 3: Venkatesan Guruswami, Limits to list decodability of linear codes, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510022]
• 4: Venkatesan Guruswami, List Decoding of Error-Correcting Codes: Winning Thesis of the 2002 ACM Doctoral Dissertation Competition (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 1899
• 5: V. Guruswami. Algebraic-geometric generalizations of the Parvaresh-Vardy codes. ECCC Technical Report TR05-132, 2005.
• 6: V. Guruswami, J. Hästad, M. Sudan, and D. Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory, 48:1021--1035, May 2002.
• 7: 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
• 8: V. Guruswami and P. Indyk. Linear time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory, 51(10):3393--3400, October 2005.
• 9: V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757--1767, 1999.
• 10: V. Y. Krachkovsky. Reed-Solomon codes for correcting phased error bursts. IEEE Transactions on Information Theory, 49(11):2975--2984, November 2003.
• 11: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 12: Farzad Parvaresh , Alexander Vardy, Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.285-294, October 23-25, 2005 [doi>10.1109/SFCS.2005.29]
• 13: A. Patthak. Reducing the alphabet size of the Parvaresh-Vardy code using Algebraic Geometry codes. Manuscript, September 2005.
• 14: Ronen Shaltiel , Christopher Umans, Simple extractors for all min-entropies and a new pseudorandom generator, Journal of the ACM (JACM), v.52 n.2, p.172-216, March 2005 [doi>10.1145/1059513.1059516]
• 15: 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]
• 16: Madhu Sudan, List decoding: algorithms and applications, ACM SIGACT News, v.31 n.1, p.16-27, March 2000 [doi>10.1145/346048.346049]
• 17: J. M. Wozencraft. List Decoding. Quarterly Progress Report, Research Laboratory of Electronics, MIT, 48:90--95, 1958.
• 18: V. V. Zyablov and M. S. Pinsker. List cascade decoding. Problems of Information Transmission, 17(4):29--34, 1981 (in Russian); pp. 236--240 (in English), 1982.

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:
Reed-Solomon codes, Zyablov bound, algebraic decoding, channel capacity, list decoding