Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets

ABSTRACT

We present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a fraction (1&mdash:r&egr;)/2 of errors over an alphabet of constant size depending only on &egr;, for every 0 < r < 1 and arbitrarily small &egr;> 0. The error-correction performance of these codes is optimal as seen by the Singleton bound (these are "near-MDS" codes). Such near-MDS linear-time codes were known for the decoding from erasures [2]; our construction generalizes this to handle errors as well. Concatenating these codes with good, constant-sized binary codes gives a construction of linear-time binary codes which meet the so-called "Zyablov bound". In a nutshell, our results match the performance of the previously known explicit constructions of codes that had polynomial time encoding and decoding, but in addition have linear time encoding and decoding algorithms.We also obtain some results for list decoding targeted at the situation when the fraction of errors is very large, namely (1—&egr;) for an arbitrarily small constant &egr; > 0. The previously known constructions of such codes of good rate over constant-sized alphabets either used algebraic-geometric codes and thus suffered from complicated constructions and slow decoding, or as in the recent work of the authors [9], had fast encoding/decoding, but suffered from an alphabet size that was exponential in 1/&egr;. We present two constructions of such codes with rate close to &OHgr;(&egr;²) over an alphabet of size quasi-polynomial in 1/&egr;. One of the constructions, at the expense of a slight worsening of the rate, can achieve an alphabet size which is polynomial in 1/&egr;. It also yields constructions of codes for list decoding from erasures which achieve new trade-offs. In particular, we construct codes of rate close to the optimal &OHgr;(&egr;) rate which can be efficiently list decoded from a fraction (1—&egr;) of erasures.

REFERENCES

• 1: Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ronny Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 38:509--516, 1992.
• 2: N. Alon , J. Edmonds , M. Luby, Linear time erasure codes with nearly optimal recovery, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.512, October 23-25, 1995
• 3: Alexander Barg and Gillés Zémor. Error exponents of expander codes. IEEE Transactions on Information Theory, to appear, 2001.
• 4: E. L. Blokh and V. V. Zyablov. Linear concatenated codes. Nauka, Moscow, 1982 (in Russian).
• 5: 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.
• 6: G. David Forney. Generalized Minimum Distance decoding. IEEE Transactions on Information Theory, 12:125--131, 1966.
• 7: Venkatesan Guruswami , Madhu Sudan, List decoding of error-correcting codes, 2001
• 8: Venkatesan Guruswami, List Decoding from Erasures: Bounds and Code Constructions, Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, p.195-206, December 13-15, 2001
• 9: 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
• 10: Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757--1767, 1999.
• 11: Piotr Indyk. List decoding in linear-time. Manuscript, 2002.
• 12: G. L. Katsman, Michael A. Tsfasman, and Serge G. Vlǎdut. Modular curves and codes with a polynomial construction. IEEE Transactions on Information Theory, 30:353--355, 1984.
• 13: Alex Lubotzky, R. Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.
• 14: Rasmus R. Nielsen and Tom Høholdt. Decoding Reed-Solomon codes beyond half the minimum distance. Coding Theory, Cryptography and Related areas, (eds. Buchmann, Hoeholdt, Stichtenoth and H. tapia-Recillas), pages 221--236, 1999.
• 15: Ronny Roth and Gitit Ruckenstein. Efficient decoding of Reed-Solomon codes beyond half the minimum distance. IEEE Transactions on Information Theory, 46(1):246--257, January 2000.
• 16: Ba-Zhong Shen. A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate. IEEE Transactions on Information Theory, 39:239--242, 1993.
• 17: M. Amin Shokrollahi and Hal Wasserman. List decoding of algebraic-geometric codes. IEEE Transactions on Information Theory, 45(2):432--437, 1999.
• 18: Michael Sipser and Daniel Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710--1722, 1996.
• 19: Daniel Alan Spielman , Michael Sipser, Computationally efficient error-correcting codes and holographic proofs, 1995
• 20: Daniel Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6):1723--1732, 1996.
• 21: 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]
• 22: Gillés Zémor. On expander codes. IEEE Transactions on Information Theory, 47(2):835--837, 2001.
• 23: Victor V. Zyablov. An estimate of the complexity of constructing binary linear cascaded codes. Problemy Peridachi Informatsii, 15(2):58--70, 1971.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
      G.1.2 Approximation
          Subjects: Linear approximation

General Terms:
Algorithms, Experimentation, Performance, Theory