In this paper, we propose a characterization for nonelementary trapping sets (NETSs) of low-density parity-check (LDPC) codes. The characterization is based on viewing a NETS as a hierarchy of embedded graphs starting from an ETS. The characterization corresponds to an efficient search algorithm that under certain conditions is exhaustive. As an application of the proposed characterization/search, we obtain lower and upper bounds on the stopping distance smin of LDPC codes. We examine a large number of regular and irregular LDPC codes, and demonstrate the efficiency and versatility of our technique in finding lower and upper bounds on, and in many cases the exact value of, smin. Finding smin, or establishing search-based lower or upper bounds, for many of the examined codes are out of the reach of any existing algorithm.

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.

In this paper, we propose a characterization of elementary trapping sets (ETSs) for irregular low-density parity-check (LDPC) codes. These sets are known to be the main culprits in the error floor region of such codes. 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: depth-one tree (dot), path and lollipop, thus, the terminology dpl characterization. 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 ≤ amaxand b ≤ bmax, exhaustively. 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.

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 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 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.

In the above paper, there are some erroneous entries in Tables I, III, IV, VII, and X, which are corrected here. Moreover, for the proper application of the definition of layered superset (LSS) property to all the results of Tables I –VII in the above-mentioned paper, the LSS definition needs to be extended as described here.