On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes

DOI10.1109/TIT.2014.2334657zbMATH Open1360.94378arXiv1308.1259MaRDI QIDQ2986137FDOQ2986137

Authors: Mehdi Karimi, Amir H. Banihashemi 

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper, we study the graphical structure of elementary trapping sets (ETS) 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 $d_l$ and girth $g$, we identify all the non-isomorphic 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. Our study 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 $calS$ 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 $calS$. 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 $d_l=3,4,5,6$, $g=6,8$ and $a,bleq10$ 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.

Full work available at URL: https://arxiv.org/abs/1308.1259

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Cited In (6)

• On the Construction of Structured LDPC Codes Free of Small Trapping Sets
• Asymptotic Spectra of Trapping Sets in Regular and Irregular LDPC Code Ensembles
• On the complexity of and solutions to the minimum stopping and trapping set problems
• Cospectral bipartite graphs with the same degree sequences but with different number of large cycles
• Characterization and Efficient Search of Non-Elementary Trapping Sets of LDPC Codes With Applications to Stopping Sets
• Eliminating trapping sets in low-density parity-check codes by using Tanner graph covers

This page was built for publication: On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986137)