In this paper, we study the graphical structure of elementary trapping sets (ETSs) of variable-regular low-density parity-check (LDPC) codes. ETSs are known to be the main cause of error floor in LDPC coding schemes. For the set of LDPC codes with a given variable node degree dl and girth g, we identify all the nonisomorphic structures of an arbitrary class of (a, b) ETSs, where a is the number of variable nodes and b is the number of odd-degree check nodes in the induced subgraph of the ETS. This paper leads to a simple characterization of dominant classes of ETSs (those with relatively small values of a and b) based on short cycles in the Tanner graph of the code. For such classes of ETSs, we prove that any set S in the class is a layered superset (LSS) of a short cycle, where the term layered is used to indicate that there is a nested sequence of ETSs that starts from the cycle and grows, one variable node at a time, to generate S. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graph and finds all the ETSs with LSS property in a guaranteed fashion. Specific results on the structure of ETSs are presented for dl = 3, 4, 5, 6, g = 6, 8, and a, b ≤ 10 in this paper. The results of this paper can be used for the error floor analysis and for the design of LDPC codes with low error floors.

Characterization of elementary trapping sets, elementary trapping sets, error floor, left-regular LDPC codes, Low-density parity-check (LDPC) codes, short cycles, trapping sets
IEEE Transactions on Information Theory
Department of Systems and Computer Engineering

Karimi, M. (Mehdi), & Banihashemi, A. (2014). On characterization of elementary trapping sets of variable-regular LDPC codes. IEEE Transactions on Information Theory, 60(9), 5188–5203. doi:10.1109/TIT.2014.2334657