In this paper, we propose a new characterization and an efficient exhaustive search algorithm for elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. Recently, Karimi and Banihashemi proposed a characterization of ETSs, which was based on viewing an ETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. Compared to the LSS-based characterization, which is based on a single LSS expansion technique, the new characterization involves two additional expansion techniques. The introduction of the new techniques mitigates two problems that LSS-based characterization/search suffers from: (1) exhaustiveness: not every ETS structure is an LSS of a cycle, (2) search efficiency: LSS-based search algorithm often requires the enumeration of cycles with length much larger than the girth of the graph, where the multiplicity of such cycles increases rapidly with their length. We prove that using the three expansion techniques, any ETS structure can be obtained starting from a simple cycle, no matter how large the size of the structure a or the number of its unsatisfied check nodes b are, i.e., the characterization is exhaustive. We also demonstrate that for the proposed characterization to exhaustively cover all the ETS structures within the (a, b) classes with a ≤ amax, b ≤ bmax, for any value of amaxand bmax, the maximum length of the required cycles is minimal. The proposed characterization corresponds to a provably efficient search algorithm, significantly more efficient than the LSS-based search.
In this paper, we propose a new characterization and an efficient exhaustive search algorithm for elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. Recently, Karimi and Banihashemi proposed a characterization of ETSs, which was based on viewing an ETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. Compared to the LSS-based characterization, which is based on a single LSS expansion technique, the new characterization involves two additional expansion techniques. The introduction of the new techniques mitigates two problems that LSS-based characterization/search suffers from: (1) exhaustiveness: not every ETS structure is an LSS of a cycle, (2) search efficiency: LSS-based search algorithm often requires the enumeration of cycles with length much larger than the girth of the graph, where the multiplicity of such cycles increases rapidly with their length. We prove that using the three expansion techniques, any ETS structure can be obtained starting from a simple cycle, no matter how large the size of the structure a or the number of its unsatisfied check nodes b are, i.e., the characterization is exhaustive. We also demonstrate that for the proposed characterization to exhaustively cover all the ETS structures within the (a, b) classes with a ≤ amax, b ≤ bmax, for any value of amaxand bmax, the maximum length of the required cycles is minimal. The proposed characterization corresponds to a provably efficient search algorithm, significantly more efficient than the LSS-based search.
In this paper, we propose a new characterization for elementary trapping sets (ETSs) of variable-regular low-density parity-check (LDPC) codes. Recently, Karimi and Banihashemi proposed a characterization of ETSs, which was based on viewing an ETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. A notable advantage of LSS characterization is that it corresponds to a simple LSS-based search algorithm that starts from short cycles of the graph and finds the ETSs with LSS structure efficiently. Compared to the LSS-based characterization of Karimi and Banihashemi, which is based on a single LSS expansion technique, the new characterization involves two additional expansion techniques. The introduction of the new techniques mitigates two problems that LSS-based characterization/search suffers from: (1) exhaustiveness, (2) search efficiency. We prove that using the three expansion techniques, any ETS structure can be obtained starting from a simple cycle, no matter how large the size of the structure a or the number of its unsatisfied check nodes b are. We also demonstrate that for the proposed characterization/search to exhaustively cover all the ETS structures within the (a,b) classes with a≤amax,b≤bmax, for any value of amax and bmax, the length of the short cycles required to be enumerated is less than that of the LSS-based characterization/search. We also prove that the three expansion techniques, proposed here, are the only expansions needed for characterization of ETS structures starting from simple cycles in the graph, if one requires each and every intermediate sub-structure to be an ETS as well. Extensive simulation results are provided to show that, compared to LSS-based search, significant improvement in search speed and memory requirements can be achieved.
In this paper, we propose an efficient exhaustive search algorithm for elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. Recently, Karimi and Banihashemi proposed a characterization of ETSs, which was based on viewing an ETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. A notable advantage of LSS characterization is that it corresponds to a simple LSS-based search algorithm (expansion technique) that starts from short cycles of the graph and finds the ETSs with LSS structure efficiently. Compared to the LSS-based search, which is based on a single LSS expansion technique, the new search algorithm involves two additional expansion techniques. The introduction of the new techniques results in significant improvements in search efficiency compared to the LSS-based search. We prove that using the three expansion techniques, each and every ETS structure can be obtained starting from a simple cycle. We also provide extensive simulation results that show, compared to the LSS-based search, up to three orders of magnitude improvement in search speed and memory requirements can be achieved.
In this paper, we propose a new characterization for leafless elementary trapping sets (LETSs) of variable-regular lowdensity parity-check codes. Recently, Karimi and Banihashemi proposed a characterization of LETSs, which was based on viewing an LETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. A notable advantage of LSS characterization is that it corresponds to a simple LSS-based search algorithm (expansion technique) that starts from short cycles of the graph and finds the LETSs with LSS structure efficiently. Compared with the LSS-based characterization of Karimi and Banihashemi, which is based on a single LSS expansion technique, the new characterization involves two additional expansion techniques. The introduction of the new techniques mitigates two problems that LSS-based characterization/search suffers from: 1) exhaustiveness: not every LETS structure is an LSS of a cycle and 2) search efficiency: LSS-based search algorithm often requires the enumeration of cycles with length much larger than the girth of the graph, where the multiplicity of such cycles increases rapidly with their length. We prove that using the three expansion techniques, any LETS structure can be obtained starting from a simple cycle, no matter how large the size of the structure a or the number of its unsatisfied check nodes b are, i.e., the characterization is exhaustive. We also demonstrate that for the proposed characterization/search to exhaustively cover all the LETS structures within the (a, b) classes with a amax and b bmax, for any value of amax and bmax, the length of the short cycles required to be enumerated is less than that of the LSS-based characterization/search. We, in fact, show that such a length for the proposed search algorithm is minimal. We also prove that the three expansion techniques, proposed here, are the only expansions needed for characterization of LETS structures starting from simple cycles in the graph, if one requires each and every intermediate sub-structure to be a LETS as well. Extensive simulation results are provided to show that, compared with LSS-based search, significant improvement in search speed and memory requirements can be achieved.
Recently, Karimi and Banihashemi demonstrated that a large majority of the elementary trapping set (ETS) structures of variable-regular low-density parity-check (LDPC) codes are layered supersets (LSS) of short cycles. The LSS property corresponds to a simple search algorithm that can find all ETSs with LSS structure starting from short cycles in a guaranteed fashion. In this letter, we complement this characterization by demonstrating that the remaining structures of ETSs, that are not LSS of short cycles, are all LSS of a small number of other graphical structures within the Tanner graph of the code, and thus can also be found efficiently. This together with the results of Karimi and Banihashemi provides a simple search algorithm that can find all the (a,b) ETSs of any variable-regular LDPC code for any size a and any number of unsatisfied check nodes b in a guaranteed fashion.
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 dland 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 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. The results of this work can be used for the error floor analysis and for the design of LDPC codes with low error floors.
In this paper, we propose a characterization of elementary trapping sets (ETSs) for irregular low-density paritycheck (LDPC) codes. These sets are known to be the main culprits in the error floor region of such codes. The characterization of ETSs for irregular codes has been known to be a challenging problem due to the large variety of nonisomorphic ETS structures that can exist within the Tanner graph of these codes. This is a direct consequence of the variety of the degrees of the variable nodes that can participate in such structures. The proposed characterization is based on a hierarchical graphical representation of ETSs, starting from simple cycles of the graph, or from single variable nodes, and involves three simple expansion techniques: degree-one tree (dot), path, and lollipop, thus, the terminology dpl characterization. A similar dpl characterization was proposed in an earlier work by the authors for the leafless ETSs of variable-regular LDPC codes. The present paper generalizes the prior work to codes with a variety of variable node degrees and to ETSs that are not leafless. The proposed dpl characterization corresponds to an efficient search algorithm that, for a given irregular LDPC code, can find all the instances of (a, b) ETSs with size a and with the number of unsatisfied check nodes b within any range of interest a amax and b bmax, exhaustively. Although branch-&-bound exhaustive search algorithms for finding ETSs of irregular LDPC codes exist, to the best of our knowledge, the proposed search algorithm is the first of its kind, in that, it is devised based on a characterization of ETSs that makes the search process efficient. For a constant degree distribution and range of search, the worst-case complexity of the proposed dpl algorithm increases linearly with the block length n. The average complexity, excluding the search for the input simple cycles, is constant in n. Extensive simulation results are presented to show the versatility of the search algorithm, and to demonstrate that, compared to the literature, significant improvement in search speed can be obtained.