Trapping sets are known to be the main cause for the error floor of low-density parity-check (LDPC) codes. They are often classified by their size a and the number of unsatisfied check nodes b in their subgraph. Trapping sets can be partitioned into two categories of elementary and non-elementary, where the first category are those whose subgraph only contains degree-1 and degree-2 check nodes. Empirical results have shown that often the most harmful trapping sets are elementary. In this letter, we derive a lower bound on the size of the smallest non-elementary trapping sets for a given b in variable-regular LDPC codes. The derived lower bound demonstrates that the size of the smallest possible non-elementary trapping set is, in general, larger than that of an elementary trapping set with the same b value. This provides a theoretical justification as to why non-elementary trapping sets are often not among the most harmful trapping sets.

elementary trapping set (ETS), error floor, leafless elementary trapping set (LETS), Low-density parity-check (LDPC) codes, non-elementary trapping set (NETS)
IEEE Communications Letters
Department of Systems and Computer Engineering

Hashemi, Y. (Yoones), & Banihashemi, A. (2017). Lower Bounds on the Size of Smallest Elementary and Non-Elementary Trapping Sets in Variable-Regular LDPC Codes. IEEE Communications Letters, 21(9), 1905–1908. doi:10.1109/LCOMM.2017.2707553