Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs

Noga Alon, Jehoshua Bruck, Moni Naor, Joseph Naor, Ron M. Roth

Research output: Contribution to journalArticlepeer-review

181 Scopus citations


A new technique, based on the pseudo-random properties of certain graphs, known as expanders, is used to obtain new 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 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 Zyablov bound, they are still superior to previously-known explicit constructions in the zero-rate neighbor-hood.

Original languageEnglish (US)
Pages (from-to)509-516
Number of pages8
JournalIEEE Transactions on Information Theory
Issue number2
StatePublished - Mar 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Expanders
  • Justesen codes
  • Zyablov bound
  • independent sets


Dive into the research topics of 'Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs'. Together they form a unique fingerprint.

Cite this