Asymptotic Average Number of Different Categories of Trapping Sets, Absorbing Sets and Stopping Sets in Random Regular and Irregular LDPC Code Ensembles.
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.
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.
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 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.
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 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.
We evaluate the asymptotic normalized average distributions of a class of combinatorial configurations in random, regular and irregular, binary low-density parity-check (LDPC) code ensembles. Among the configurations considered are trapping and stopping sets. These sets represent subsets of variable nodes in the Tanner graph of a code that play an important role in determining the height and point of onset of the error-floor in its performance curve. The techniques used for deriving the spectra include large deviations theory and statistical methods for enumerating binary matrices with prescribed row and column sums. These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, that are known to characterize other important properties of soft-decision decoders of linear block codes
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.