Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- 1 March 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 38 (2) , 509-516
- https://doi.org/10.1109/18.119713
Abstract
A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel simple explicit constructions of asymptotically good codes. In one of the constructions, the expanders are used to enhance Justesen codes by replicating, shuffling, and then regrouping the code coordinates. For any fixed (small) rate, and for a sufficiently large alphabet, the codes thus obtained lie above the Zyablov bound. Using these codes as outer codes in a concatenated scheme, a second asymptotic good construction is obtained which applies to small alphabets (say, GF(2)) as well. Although these concatenated codes lie below the Zyablov bound, they are still superior to previously known explicit constructions in the zero-rate neighborhood.<>Keywords
This publication has 23 references indexed in Scilit:
- On the second eigenvalue of a graphDiscrete Mathematics, 1991
- Small-bias probability spaces: efficient constructions and applicationsPublished by Association for Computing Machinery (ACM) ,1990
- Dispersers, deterministic amplification, and weak random sourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Eigenvalues, geometric expanders, sorting in rounds, and ramsey theoryCombinatorica, 1986
- A note on lower bounds (Corresp.)IEEE Transactions on Information Theory, 1986
- Explicit construction of exponential sized families of k-independent setsDiscrete Mathematics, 1986
- Modular curves and codes with a polynomial constructionIEEE Transactions on Information Theory, 1984
- Some results on the problem of constructing asymptotically good error-correcting codesIEEE Transactions on Information Theory, 1975
- Justesen's construction--The low-rate case (Corresp.)IEEE Transactions on Information Theory, 1973
- Families of k-independent setsDiscrete Mathematics, 1973