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, 2017 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, 2017 at 13:05

1 Answer 1


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 agree to our terms of service and acknowledge you have read our privacy policy.

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