Concatenated codes can achieve list-decoding capacity

ABSTRACT

We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any 0 < ρ < 1/2 and ε > 0, there exist concatenated codes of rate at least 1 -- H(ρ) -- ε that are (combinatorially) list-decodable up to a fraction ρ of errors. (The best possible rate, aka list-decoding capacity, for such codes is 1 -- H(ρ), and is achieved by random codes.) A similar result, with better list size guarantees, holds when the outer code is also randomly chosen. Our methods and results extend to the case when the alphabet size is any fixed prime power q ≥ 2.

Our result shows that despite the structural restriction imposed by code concatenation, the family of concatenated codes is rich enough to include capacity achieving list-decodable codes. This provides some encouraging news for tackling the problem of constructing explicit binary list-decodable codes with optimal rate, since code concatenation has been the preeminent method for constructing good codes over small alphabets.

REFERENCES

• 1: E. L. Blokh and Victor V. Zyablov. Existence of linear concatenated binary codes with optimal correcting properties. Prob. Peredachi Inform., 9:3--10, 1973.
• 2: Ilya I. Dumer. Concatenated codes and their multilevel generalizations. In V. S. Pless and W. C. Huffman, editors, Handbook of Coding Theory, volume 2, pages 1911--1988. North Holland, 1998.
• 3: G. David Forney. Concatenated Codes. MIT Press, Cambridge, MA, 1966.
• 4: Venkatesan Guruswami, Johan Hastad, Madhu Sudan, and David Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory, 48(5):1021--1035, 2002.
• 5: 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
• 6: Venkatesan Guruswami , Atri Rudra, Explicit capacity-achieving list-decodable codes, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132518]
• 7: Venkatesan Guruswami and Atri Rudra. Limits to list decoding Reed-Solomon codes. IEEE Transactions on Information Theory, 52(8), August 2006.
• 8: Venkatesan Guruswami and Atri Rudra. Better binary list-decodable codes via multilevel concatenation. In Proceedings of the 11th International Workshop on Randomization and Computation (RANDOM), pages 554--568, 2007.
• 9: F. J. MacWilliams and Neil J. A. Sloane. The Theory of Error-Correcting Codes. Elsevier/North-Holland, Amsterdam, 1981.
• 10: Jørn Justesen. A class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory, 18:652--656, 1972.
• 11: Atri Rudra , Venkatesan Guruswami, List decoding and property testing of error-correcting codes, University of Washington, Seattle, WA, 2007
• 12: Michael Sipser and Daniel Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710--1722, 1996.
• 13: Daniel A. Spielman, The Complexity of Error-Correcting Codes, Proceedings of the 11th International Symposium on Fundamentals of Computation Theory, p.67-84, September 01-03, 1997
• 14: Christian Thommesen. The existence of binary linear concatenated codes with Reed-Solomon outer codes which asymptotically meet the Gilbert-Varshamov bound. IEEE Transactions on Information Theory, 29(6):850--853, November 1983.

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
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Theory