I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm.

For example, I know that Sipser and Spielman proved that there is an algorithm that can correct a constant fraction of errors for expander codes (in Expander codes, 1996).

But, is there any equivalent theorem for other families of LDPC codes (like regular LDPC or irregular LDPC, for example)? References would be useful.


  • $\begingroup$ I do not understand the question. There are plenty of distinct examples of codes that are based on expanders and are analyzed using similar ideas to Sipser-Spielman. Are you looking for LDPC codes that are not based on expanders? $\endgroup$ – Or Meir Mar 27 '17 at 11:01
  • $\begingroup$ I am looking for any LDPC code as long as it can correct any constant fraction of errors. They can be based on expander graphs or not, although I would prefer not based on expanders. Thanks! $\endgroup$ – P.B. Mar 27 '17 at 13:05

Here are a few examples:

There are the expander codes of Spielman (not to be confused with Sipser-Spielman): http://www.cs.yale.edu/homes/spielman/Research/ITsuperc.pdf

There are the linear-time codes of Guruswami-Indyk: https://www.cs.cmu.edu/~venkatg/pubs/papers/lin-zyablov.pdf

There are the expander codes of Zemor: https://courses.engr.illinois.edu/cs598sgt/zemor.pdf


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.