# Error Floors, Trapping Sets and Pseudo-codewords

Iterative message passing algorithms for decoding LDPC codes operate by passing messages along the edges of a graphical representation of the code known as the Tanner graph. These algorithms are optimal when the underlying graph is a tree, but in the presence of cycles, the decoding becomes sub-optimal and there exist low-weight patterns known as near codewords or trapping sets uncorrectable by the decoder. It is now well established that the trapping sets lead to error floor in the high SNR region.

# Constructing Structured LDPC Codes Free of Small Trapping Sets

## Members

- Bane Vasic
- Michael Marcellin
- Dung Viet Nguyen
- Shiva Kumar Planjery

## Collaborators

- David Declercq
- Misha Chertkov
- Misha Stepanov

# Project Publications

## Journal Papers

BibTeX |
D. V. Nguyen, S. K. Chilappagari, B. Vasić, and M. W. Marcellin, "On the construction of structured LDPC codes free of small trapping sets," *IEEE Trans. Inf. Theory, *vol. 58, no. 4, pp. 2280 - 2302, Apr. 2012. |

BibTeX |
S. K. Chilappagari, D. V. Nguyen, B. Vasić, and M. W. Marcellin, "Error correction capability of column-weight-three LDPC codes under the Gallager A algorithm - PART II," *IEEE Trans. Inf. Theory, *vol. 56, no. 6, pp. 2626 - 2639, Jun. 2010. |

BibTeX |
M. G. Stepanov, V. Chernyak, M. Chertkov, and B. Vasić, "Diagnosis of weaknesses in modern error correction codes: A physics approach," *Physical Review Lett., *vol. 95, no. 22, pp. 228701 - 228704, Nov. 2005. |

BibTeX |
V. Chernyak, M. Chertkov, M. G. Stepanov, and B. Vasić, "Error correction on a tree: an instanton approach," *Physics Review Lett., *vol. 93, no. 19, pp. 1 - 4, Nov. 2004. |

## Conference Papers

BibTeX |
D. V. Nguyen, B. Vasić, and M. W. Marcellin, "Methods of searching for trapping sets of quasi-cylic LDPC codes and their applications in code construction," *Proc. 47th Int. Telemetering Conf., *Oct. 24 - 27 2011, pp. 1 - 10. |

BibTeX |
D. V. Nguyen, B. Vasić, M. W. Marcellin, and S. K. Chilappagari, "Structured LDPC codes from permutation matrices free of small trapping sets," *Proc. IEEE Inform. Theory Workshop, *Aug. 30 - Sep. 3 2010, pp. 1 - 5. |

BibTeX |
B. Vasić, S. K. Chilappagari, D. V. Nguyen, and S. K. Planjery, "Trapping set ontology," *Proc. 47th Allerton Conf. on Commun., Control, and Computing, *Sep. 30 - Oct. 2 2009, pp. 1 - 7. |

BibTeX |
S. K. Chilappagari, B. Vasić, M. Stepanov, and M. Chertkov, "Analysis of error floors of LDPC codes under LP decoding over the BSC," *Proc. IEEE Int. Symp. on Inform. Theory, *Jun. 28 - Jul. 3 2009, pp. 379 - 383. |

BibTeX |
S. K. Chilappagari, B. Vasić, and M.W. Marcellin, "Guaranteed error correction capability of codes on graphs," *Proc. Inform. Theory and Applicat. Workshop, *Feb. 8 - 13 2009, pp. 50 - 55. |

BibTeX |
S. K. Chilappagari, D. V. Nguyen, B. Vasić, and M. W. Marcellin, "On guaranteed error correction capability of GLDPC codes," *Proc. 44th Int. Telemetering Conf., *Oct. 2008. |

BibTeX |
S. K. Chilappagari, D. V. Nguyen, B. Vasić, and M. W. Marcellin, "Girth of the Tanner graph and error correction capability of LDPC codes," *Proc. 46th Allerton Conf. on Commun., Control, and Computing, *Sep. 23 - 26 2008. |

BibTeX |
S. K. Chilappagari, D. V. Nguyen, B. Vasić, and M. W. Marcellin, "On the guaranteed error correction capability of LDPC codes," *Proc. IEEE Int. Symp. on Inform. Theory, *Jul. 6 - 11 2008, pp. 434 - 438. |

BibTeX |
S. K. Chilappagari, A. R. Krishnan, and B. Vasić, "LDPC codes which can correct three errors under iterative decoding," *Proc. IEEE Inform. Theory Workshop, *May 5 - 9 2008, pp. 406 - 410. |