We address the problem of evaluating the asymptotic normalized distributions of a class of combinatorial configurations in random, regular, binary low-density parity-check (LDPC) code ensembles.Among the configurations considered are trapping and stopping sets 1 ; these sets represent induced subgraphs in the Tanner graph of a code that, for certain classes of channels, exhibit a strong influence on the height and point of onset of the error-floor.The techniques used in the derivations are based on large deviation theory and statistical methods for enumerating random-like matrices.These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, which are known to characterize other important properties of soft-decision decoders of linear codes.
We address the problem of evaluating the asymptotic normalized distributions of a class of combinatorial configurations in random, regular, binary low-density parity-check (LDPC) code ensembles.Among the configurations considered are trapping and stopping sets 1 ; these sets represent induced subgraphs in the Tanner graph of a code that, for certain classes of channels, exhibit a strong influence on the height and point of onset of the error-floor.The techniques used in the derivations are based on large deviation theory and statistical methods for enumerating random-like matrices.These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, which are known to characterize other important properties of soft-decision decoders of linear codes.
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
Trapping sets represent subgraphs in the Tanner graph of a code that, for certain classes of channels, exhibit a strong influence on the height and point of onset of the error-floor. We compute the asymptotic normalized distributions of trapping sets in random, irregular, binary low-density parity-check (LDPC) code ensembles. Our derivations rely on techniques from large deviation theory and statistical methods for enumeracting random-like matrices. Similar methods can be used for computing the spectra of other combinatorial entities in LDPC code, such as subcodes and/or minimal codewords.
It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. Past work has focused on characterizing the distribution of trapping sets for a variety of code ensembles, including regular, irregular and structured LDPC codes. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In this paper, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. The calculations are based on the trapping set enumeration method proposed by Milenkovic, Soljanin, and Whiting in [1]. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders.
Several combinatorial properties of low-density parity-check (LDPC) codes, such as minimum distance, diameter, stopping number, girth and cycle-length distribution of the corresponding Tanner graph, are known to influence their performance under iterative decoding. Recently, a new class of combinatorial configurations, termed trapping sets, was shown to be of significant importance in determining the properties of LDPC codes in the error-floor region. Very little is known both about the existence/parameters of trapping sets in structured LDPC codes and about possible techniques for reducing their negative influence on the code's performance. In this paper, we address both these problems from an algorithmic and combinatorial perspective. We first provide a numerical study of the trapping phenomena for the Margulis code, which exhibits a fairly high error-floor. Based on this analysis, conducted for two different implementations of iterative belief propagation, we propose a novel decoding process, termed averaged decoding. Averaged decoding provides for a significant reduction in the number of incorrectly decoded frames in the error-floor region of the Margulis code. Furthermore, based on the results of the algorithmic approach, we suggest a novel combinatorial characterizations of trapping sets in the class of LDPC codes based on finite geometries. Projective geometry LDPC codes are suspected to have extremely low error-floors, which is a property that we may attribute to the non-existence of certain small trapping sets in the code graph.
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 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.