Expander-based constructions of efficiently decodable codes
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 658-667
- https://doi.org/10.1109/sfcs.2001.959942
Abstract
We present several novel constructions of codes which share the common thread of using expander (or expander-like) graphs as a component. The expanders enable the design of efficient decoding algorithms that correct a large number of errors through various forms of "voting" procedures. We consider both the notions of unique and list decoding, and in all cases obtain asymptotically good codes which are decodable up to a "maximum" possible radius and either: (a) achieve a similar rate as the previously best known codes but come with significantly faster algorithms, or (b) achieve a rate better than any prior construction with similar error-correction properties. Among our main results are: i) codes of rate /spl Omega/(/spl epsi//sup 2/) over constant-sized alphabet that can be list decoded in quadratic time from (1-/spl epsi/) errors; ii) codes of rate /spl Omega/(/spl epsi/) over constant-sized alphabet that can be uniquely decoded from (1/2-/spl epsi/) errors in near-linear time (this matches AG-codes with much faster algorithms); iii) linear-time encodable and decodable binary codes of positive rate (in fact, rate /spl Omega/(/spl epsi//sup 2/)) that can correct up to (1/4-/spl epsi/) fraction errors.Keywords
This publication has 17 references indexed in Scilit:
- A low complexity algorithm for the construction of algebraic geometric codes better than the Gilbert-Varshamov boundPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On representations of algebraic-geometry codesIEEE Transactions on Information Theory, 2001
- List decoding algorithms for certain concatenated codesPublished by Association for Computing Machinery (ACM) ,2000
- Efficient decoding of Reed-Solomon codes beyond half the minimum distanceIEEE Transactions on Information Theory, 2000
- List decoding of algebraic-geometric codesIEEE Transactions on Information Theory, 1999
- Decoding of Reed Solomon Codes beyond the Error-Correction BoundJournal of Complexity, 1997
- Expander codesIEEE Transactions on Information Theory, 1996
- Linear-time encodable and decodable error-correcting codesIEEE Transactions on Information Theory, 1996
- A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rateIEEE Transactions on Information Theory, 1993
- Ramanujan graphsCombinatorica, 1988