Error correction up to the information-theoretic limit

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Error correction up to the information-theoretic limit

Full text

Digital Edition , Html

Html (69 KB), Pdf

Pdf (2.26 MB)

Source

Communications of the ACM archive
Volume 52 , Issue 3 (March 2009) table of contents
Being Human in the Digital Age

SECTION: Research highlights table of contents

Pages 87-95

Year of Publication: 2009

ISSN:0001-0782

Authors

Venkatesan Guruswami	University of Washington, Seattle, WA
Atri Rudra	University at Buffalo, SUNY, Buffalo, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 32, Downloads (12 Months): 534, Citation Count: 0

Additional Information:

appendices and supplements abstract references additional resources index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1467247.1467269 What is a DOI?

APPENDICES and SUPPLEMENTS

List Decoding with Optimal Rate: Folded Reed-Solomon Codes (641 KB),	Presentation by Venkatesan Guruswami discusses background in list decoding and the main result of the article at an intuitive yet technical level.

Recovering Data in Presence of Malicious Errors (2.49 MB),	High-level, survey-like presentation by Atri Rudra on list decoding and the results described in the article.

List Decoding of Binary Codes: New Concatenation-Based Results (799 KB),	A presentation by Venkatesan Guruswami on follow-up work on error correction for binary codes.

ABSTRACT

Ever since the birth of coding theory almost 60 years ago, researchers have been pursuing the elusive goal of constructing the "best codes," whose encoding introduces the minimum possible redundancy for the level of noise they can correct. In this article, we survey recent progress in list decoding that has led to efficient error-correction schemes with an optimal amount of redundancy, even against worst-case errors caused by a potentially malicious channel. To correct a proportion ρ(say 20%) of worst-case errors, these codes only need close to a proportion ρ of redundant symbols. The redundancy cannot possibly be any lower information theoretically. This new method holds the promise of correcting a factor of two more errors compared to the conventional algorithms currently in use in diverse everyday applications.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Berlekamp, E. Factoring polynomials over large finite fields. Math. Comput. 24 (1970), 713--735.
	2	Elias, P. List decoding for noisy channels. Technical Report 335, MIT Research Lab of Electronics, 1957.
	3	Peter Gemmell , Madhu Sudan, Highly resilient correctors for polynomials, Information Processing Letters, v.43 n.4, p.169-174, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90195-2]
	4	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	5	Guruswami, V. Artin automorphisms, cyclotomic function fields, and folded list-decodable codes, 2008. Manuscript.
	6	Guruswami, V., Indyk, P. Linear-time encodable/decodable codes with near-optimal rate. IEEE Trans. Information Theory 51, 10 (2005), 3393--3400.
	7	Guruswami, V., Patthak, A. Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets. Math. Comput. 77, 261 (Jan. 2008), 447--473.
	8	Venkatesan Guruswami , Atri Rudra, Better Binary List-Decodable Codes Via Multilevel Concatenation, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_40]
	9	Guruswami, V., Rudra, A. Explicit codes achieving list decoding capacity: Error-correction up to the Singleton bound. IEEE Trans. Information Theory 54, 1 (2008), 135--150. Preliminary version in STOC'06.
	10	Guruswami, V., Sudan, M. Improved decoding of Reed--Solomon and algebraic-geometric codes. IEEE Trans. Information Theory, 45 (1999), 1757--1767.
	11	Venkatesan Guruswami , Christopher Umans , Salil Vadhan, Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.96-108, June 13-March 16, 2007 [doi>10.1109/CCC.2007.38]
	12	Hamming, R.W. Error detecting and error correcting codes. Bell System Technical J. 29 (Apr. 1950), 147--160.
	13	Koetter, R., Vardy, A. Algebraic soft-decision decoding of Reed--Solomon codes. IEEE Trans. Information Theory 49, 11 (2003), 2809--2825.
	14	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]
	15	Peterson, W.W. Encoding and error-correction procedures for Bose--Chaudhuri codes. IEEE Trans. Information Theory, 6 (1960), 459--470.
	16	Shannon, C.E. A mathematical theory of communication. Bell System Technical J. 27 (1948), 379--423, 623--656.
	17	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]
	18	Welch, L.R., Berlekamp, E.R. Error correction of algebraic block codes. US Patent Number 4,633,470, December 1986.
	19	Wozencraft, J.M. List Decoding. Quarterly Progress Report, Research Laboratory of Electronics, MIT, 48 (1958), 90--95.