Leafless elementary trapping sets (LETSs) are known to be among the most harmful substructures of Tanner graphs of low-density parity-check (LDPC) codes in the error floor region. It is well-known that in the asymptotic regime of infinite block length, the only LETS structures that have finite non-zero average multiplicity are those that contain a single (simple) cycle. The average multiplicity of all the other LETSs, whose structures contain more than one cycle, tends to zero asymptotically. The asymptotic average multiplicity of LETS structures with a single cycle for variable-regular LDPC codes has already been derived by the authors in a previous work. In this paper, we compute the asymptotic average multiplicity of such structures for irregular LDPC code ensembles. The derivation involves counting the average number of cycles of a specific length with a specific combination of variable node degrees. We demonstrate that the asymptotic results, derived in this paper, match well with the LETS multiplicities of finite-length LDPC codes chosen randomly from the ensemble, even for rather short block lengths.
Leafless elementary trapping sets (LETSs) are known to be among the most harmful substructures of Tanner graphs of low-density parity-check (LDPC) codes in the error floor region. It is well-known that in the asymptotic regime of infinite block length, the only LETS structures that have finite non-zero average multiplicity are those that contain a single (simple) cycle. The average multiplicity of all the other LETSs, whose structures contain more than one cycle, tends to zero asymptotically. The asymptotic average multiplicity of LETS structures with a single cycle for variable-regular LDPC codes has already been derived by the authors in a previous work. In this paper, we compute the asymptotic average multiplicity of such structures for irregular LDPC code ensembles. The derivation involves counting the average number of cycles of a specific length with a specific combination of variable node degrees. We demonstrate that the asymptotic results, derived in this paper, match well with the LETS multiplicities of finite-length LDPC codes chosen randomly from the ensemble, even for rather short block lengths.
The performance of low-density parity-check (LDPC) codes in the error floor region is closely related to some substructures of the code's Tanner graph, collectively referred to as trapping sets (TSs). In this paper, we study the asymptotic average number of different types of trapping sets such as elementary TSs (ETS), leafless ETSs (LETS), absorbing sets (ABS), elementary ABSs (EABS), and stopping sets (SS), in random variable-regular and irregular LDPC code ensembles. We demonstrate that, regardless of the type of the TS, as the code's length tends to infinity, the average number of a given structure tends to infinity, to a positive constant, or to zero, if the structure contains no cycle, only one cycle, or more than one cycle, respectively. For the case where the structure contains a single cycle, we derive the asymptotic expected multiplicity of the structure by counting the average number of its constituent cycles and all the possible ways that the structure can be constructed from the cycle. This, in general, involves computing the expected number of cycles of a certain length with a certain given combination of node degrees, or computing the expected number of cycles of a certain length expanded to the desired structure by the connection of trees to its nodes. The asymptotic results obtained in this work, which are independent of the block length and only depend on the code's degree distributions, are shown to be accurate even for finite-length codes.
The performance of low-density parity-check (LDPC) codes in the error floor region is closely related to some substructures of the code's Tanner graple (simple) cycle have a nonzero finite average multiplicity. In this paper, we compute the asymptotic expected multiplicity of such ETS structures in random LDPC code ensembles. The computation, in general, involves two subproblems: (i) counting the number of cycles of a certain length with different combinations of variable node degrees, and (ii) counting the number of ways trees of different sizes can be appended to such a cycle to form an ETS. The first subproblem, which counts the number of leafless ETSs (LETSs), is solved by the authors in other papers. The second subproblem is formulated as a recursive counting problem and is solved in this paper, with the solution being a generalization of Catalan numbers. We also demonstrate through numerical results that the asymptotic expected values computed in this paper match the multiplicity of ETSs in randomly selected finite-length LDPC codes, even at relatively short block lengths.
The performance of low-density parity-check (LDPC) codes in the error floor region is closely related to some substructures of the code's Tanner graph, collectively referred to as trapping sets (TSs). In this paper, we study the asymptotic average number of different types of trapping sets such as elementary TSs (ETS), leafless ETSs (LETS), absorbing sets (ABS), elementary ABSs (EABS), and stopping sets (SS), in random variable-regular and irregular LDPC code ensembles. We demonstrate that, regardless of the type of the TS, as the code's length tends to infinity, the average number of a given structure tends to infinity, to a positive constant, or to zero, if the structure contains no cycle, only one cycle, or more than one cycle, respectively. For the case where the structure contains a single cycle, we obtain an estimate of the expected number of the structure through the available approximations for the average number of the constituent cycle. These estimates, which are independent of the block length and only depend on the code's degree distributions, are shown to be accurate even for finite-length codes.
The performance of low-density parity-check (LDPC) codes in the error floor region is closely related to some combinatorial structures of the code's Tanner graph, collectively referred to as {\it trapping sets (TSs)}. In this paper, we study the asymptotic average number of different types of trapping sets such as {\em elementary TSs (ETS)}, {\em leafless ETSs (LETS)}, {\em absorbing sets (ABS)}, {\em elementary ABSs (EABS)}, and {\em stopping sets (SS)}, in random variable-regular and irregular LDPC code ensembles. We demonstrate that, regardless of the type of the TS, as the code's length tends to infinity, the average number of a given structure tends to infinity, to a positive constant, or to zero, if the structure contains no cycle, only one cycle, or more than one cycle, respectively. For the case where the structure contains a single cycle, we obtain an estimate of the expected number of the structure through the available approximations for the average number of its constituent cycle. These estimates, which are independent of the block length and only depend on the code's degree distributions, are shown to be accurate even for finite-length codes.
Leafless elementary trapping sets (LETSs) are known to be the problematic structures in the error floor region of low-density parity-check (LDPC) codes over the additive white Gaussian (AWGN) channel under iterative decoding algorithms. While problems involving the general category of trapping sets, and the subcategory of elementary trapping sets (ETSs), have been shown to be NP-hard, similar results for LETSs, which are a subset of ETSs are not available. In this paper, we prove that for a general LDPC code, finding a LETS of a given size a with minimum number of odd-degree check nodes b is NP-hard to approximate within any approximation factor. We also prove that finding the minimum size a of a LETS with a given b is NP-hard to approximate within any approximation factor. Similar results are proved for elementary absorbing sets, a popular subcategory of LETSs.
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.