Trapping set ontology

Home Publications Projects Tools Links
  • Contact
    • +1-520-626-5550
    • vasic@ece.arizona.edu

Summary

The failures of iterative message passing for decoding low-density parity-check (LDPC) codes on the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC) can be understood in terms of combinatorial objects known as trapping sets. We have derived a systematic method to identify the most relevant trapping sets for decoding over the BSC in the error floor region. We have also elaborated on the notion of the critical number of a trapping set and derived a classification of trapping sets. We developed the trapping set ontology, a database of trapping sets that summarizes the topological relations among trapping sets. This page exibits our database of trapping sets.

For more information (background, methodology, applications, references), please refer to our published work: "Trapping Set Ontology", Allerton 2009.

Notations

The girth of the Tanner graph which represents the LDPC code is denoted as g. The subgraph induced by an (a, b) trapping set has a variable nodes and b odd degree check nodes.
There might be more than one (a, b) trapping set. Subgraphs induced by these trapping sets are not isomorphic but have the same number of variable nodes and odd degree check nodes. For this reason, we arbitrarily index trapping sets and use the notation (a, b){i}, where {i} represents the index of a trapping set.

Tanner Graph Representation

The Tanner graph representation of an (a, b) trapping set T is the sub-graph induced by the variable nodes in the trapping set. Variable nodes are represented by solid circles. Even degree check nodes are represented by hollow squares while odd degree check nodes are reprented by solid squares. The figure below shows the Tanner graph representation of the (4,4) trapping set.

Lines and Points Representation

We choose an alternate graphical representation of trapping sets based on the incidence structure of lines and points. In combinatorial mathematics, an incidence structure is a triple (P,L, I) where P is a set of "points", L is a set of "lines" and I ⊆ P × L is the incidence relation. The elements of I are called flags. If (p, l) ⊆ I, we say that point p "lies on" line l. In this representation of trapping sets, variable nodes correspond to lines and check nodes correspond to points. A point is solid if it has odd number of lines passing through it otherwise it is hollow. An (a, b) trapping set is thus an incidence structure with a lines and b solid points. The figure below shows the lines and points representation of the (4,4) trapping set.

Classification of Trapping Sets

A list of possible candidates for trapping sets and corresponding subgraphs will be useful for analyzing Tanner graphs of any code. Such a list will make the trapping set identification process independent of the code. The problem of creating a list of possible candidates can be related to the coloring problems in graph theory.

Trapping Set (TS)# TSg=6g=8g=10g=12g=14g=16
(3,3)11
(4,4)11
(4,2)11
(4,0)11
(5,5)11
(5,3)212
(5,1)11
(6,6)11
(6,4)41, 23, 4
(6,2)41, 2, 43
(6,0)212
(7,7)11
(7,5)61, 2, 53, 64
(7,3)101, 2, 5, 6, 7, 8, 93, 4, 10
(7,1)42, 3, 41
(8,8)11
(8,6)101, 2, 3, 54, 7, 96,108
(8,4)251, 2, 3, 4, 5, 9, 10, 13, 14, 18, 19, 20, 21, 22, 236, 7, 8, 11, 15, 16, 17, 24, 2512
(8,2)191, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 175, 15, 16, 18, 19
(8,0)53, 4, 51, 2

Trapping Sets Database

The following tables exibit out trapping sets database and their topological relations.


(4,4){1}

(5,3){2}

(6,4){4}

(6,4){8}


(6,2){3}

(6,0){2}

(7,5){3}

(7,5){6}


(7,3){3}

(7,3){4}

(7,3){10}

(7,1){1}


(8,6){4}

(8,6){7}

(8,6){9}

(8,4){6}


(8,4){7}

(8,4){8}

(8,4){11}

(8,4){15}


(8,4){16}

(8,4){17}

(8,4){24}

(8,4){25}


(8,2){5}

(8,2){15}

(8,2){16}

(8,2){8}


(8,2){19}

(8,0){1}

(8,0){2}


Trapping SetParentsChildren
(4,4){1}All remaining trapping sets
(5,3){2}(4,4){1}(6,2){3}, (6,0){2}, (7,3){4}, (7,1){1}, (8,4){7}, (8,2){16}, (8,2){18}
(6,4){3}(4,4){1}(7,3){3}, (7,3){10}, (8,4){6}, (8,4){16}, (8,4){25}, (8,2){5}, (8,2){15}, (8,2){19}, (8,0){1}, (8,0){2}
(6,4){4}(4,4){1}(7,3){3}, (7,3){4}, (7,1){1}, (8,4){11}, (8,4){15}, (8,4){17}, (8,2){5}
(6,2){3}(4,4){1}, (5,3){2}(7,1){1}, (8,2){16}
(6,0){2}(4,4){1}, (5,3){2}
(7,5){3}(4,4){1}(8,4){15}, (8,4){17}, (8,4){24}, (8,4){25}, (8,2){19}
(7,5){6}(4,4){1}(8,4){7}, (8,4){8}, (8,4){16}, (8,4){24}, (8,2){15}, (8,2){16}, (8,2){18}
(7,3){3}(4,4){1}, (6,4){3}, (6,4){4}(8,2){5}, (8,2){19}, (8,0){2}
(7,3){4}(4,4){1}, (5,3){2}, (6,4){4}(8,2){18}
(7,3){10}(4,4){1}, (6,4){3}(8,2){15}, (8,0){1}
(7,1){1}(4,4){1}, (5,3){2}, (6,4){4}, (6,2){3}
(8,6){4}(4,4){1}
(8,6){7}(4,4){1}
(8,6){9}(4,4){1}
(8,4){6}(4,4){1}, (6,4){3}
(8,4){7}(4,4){1}, (5,3){2}, (7,5){6}
(8,4){8}(4,4){1}, (7,5){6}
(8,4){11}(4,4){1}, (6,4){4}
(8,4){15}(4,4){1}, (6,4){4}, (7,5){3}
(8,4){16}(4,4){1}, (6,4){3}, (7,5){6}
(8,4){17}(4,4){1}, (6,4){4}, (7,5){3}
(8,4){24}(4,4){1}, (7,5){3}, (7,5){6}
(8,4){25}(4,4){1}, (6,4){3}, (7,5){3}
(8,2){5}(4,4){1}, (6,4){3}, (6,4){4}, (7,3){3}
(8,2){15}(4,4){1}, (6,4){3}, (7,5){6}, (7,3){10}
(8,2){16}(4,4){1}, (5,3){2}, (6,2){3}, (7,5){6}
(8,2){18}(4,4){1}, (5,3){2}, (6,4){4}, (7,5){6}, (7,3){4}
(8,2){19}(4,4){1}, (6,4){3}, (6,4){4}, (7,5){3}, (7,3){3}
(8,0){1}(4,4){1}, (6,4){3}, (7,3){10}
(8,0){2}(4,4){1}, (6,4){3}, (6,4){4}, (7,3){3}

Members

  • Shiva Kumar Planjery
  • Dung Viet Nguyen
  • Ludovic Danjean
  • Bane Vasic
  • Michael Marcellin

Sponsor

  • NSF Grant CCF-0963726

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, M. Chertkov, and B. Vasić, "An Efficient Instanton Search Algorithm for LP Decoding of LDPC Codes Over the BSC," IEEE Trans. Inf. Theory, vol. 57, no. 7, pp. 4417 - 4426, Jul. 2011.
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 S. K. Chilappagari, D. V. Nguyen, B. Vasić, and M. W. Marcellin, "On Trapping Sets and Guaranteed Error Correction Capability of LDPC codes and GLDPC Codes," IEEE Trans. Inf. Theory, vol. 56, no. 4, pp. 1600 - 1611, Apr. 2010.
BibTeX S. K. Chilappagari, M. Chertkov, M. Stepanov, and B. Vasić, "Instanton-based techniques for analysis and reduction of error floors of LDPC codes," IEEE J. Sel. Areas Commun., vol. 27, no. 6, pp. 855 - 865, Aug. 2009.
BibTeX M. Ivkovic, S. K. Chilappagari, and B. Vasić, "Eliminating Trapping Sets in Low-Density Parity-Check Codes by Using Tanner Graph Covers," IEEE Trans. Inf. Theory, vol. 54, no. 8, pp. 3763 - 3768, Aug. 2008.
BibTeX S. K. Chilappagari and B. Vasić, "Error-Correction Capability of Column-Weight-Three LDPC Codes," IEEE Trans. Inf. Theory, vol. 55, no. 5, pp. 2055 - 2061, May 2008.

Conference Papers


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, 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.
BibTeX S. K. Chilappagari, S. Sankaranarayanan, and B. Vasić, "Error floors of LDPC codes on the binary symmetric channel," Proc. IEEE Int. Conf. on Commun., vol. 3, Jun. 2006, pp. 1089 - 1094.
BibTeX B. Vasić, S. K. Chilappagari, S. Sankaranarayanan, and R. Radhakrishnan, "Failures of the Gallager B decoder: analysis and applications," Proc. 2nd Inform. Theory and Applicat. Workshop, Feb. 2006, pp. paper 160.