Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates

Full text

Pdf (67 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

New Orleans, Louisiana

SESSION: Session 9A table of contents

Pages: 756 - 757

Year of Publication: 2004

ISBN:0-89871-558-X

Authors

Venkatesan Guruswami	University of Washington, Seattle
Piotr Indyk	Laboratory for Computer Science, MIT, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 1

Additional Information:

abstract references cited by collaborative colleagues peer to peer

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

ABSTRACT

We demonstrate a probabilistic construction of binary linear codes meeting the GV bound (with overwhelming probability) for rates up to about 10^-4 together with polynomial time algorithms to perform encoding and decoding up to half the distance. The only previous result of this type (for rates up to about 0.02) suffered from sub-exponential time decoding [3].

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	Venkatesan Guruswami , Madhu Sudan, Decoding Concatenated Codes using Soft Information, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.148, May 21-24, 2002
	2	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, 1983.
	3	Victor V. Zyablov and Mark S. Pinsker. List cascading decoding, Problems of Information Transmission, 17(4):29--34, 1981 (in Russian), pages 236--240 (in English), 1982.

CITED BY

Jon Feldman , Cliff Stein, LP decoding achieves capacity, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia

Collaborative Colleagues:

Venkatesan Guruswami: colleagues

Piotr Indyk: colleagues

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski

Adobe Acrobat

QuickTime

Windows Media Player

Real Player