Stopping sets determine the performance of low-density parity-check (LDPC) codes under iterative decoding over erasure channels. We derive several results on the asymptotic behavior of stopping sets in Tanner-graph ensembles, including the following. An expression for the normalized average stopping set distribution, yielding, in particular, a critical fraction of the block length above which codes have exponentially many stopping sets of that size. A relation between the degree distribution and the likely size of the smallest nonempty stopping set, showing that for a /spl radic/1-/spl lambda/'(0)/spl rho/'(1) fraction of codes with /spl lambda/'(0)/spl rho/'(1)2, the smallest nonempty stopping set is linear in the block length. Bounds on the average block error probability as a function of the erasure probability /spl epsi/, showing in particular that for codes with lowest variable degree 2, if /spl epsi/ is below a certain threshold, the asymptotic average block error probability is 1-/spl radic/1-/spl lambda/'(0)/spl rho/'(1)/spl epsi/.
Stopping sets determine the performance of low-density parity-check (LDPC) codes under iterative decoding over erasure channels. We derive several results on the asymptotic behavior of stopping sets in Tanner-graph ensembles, including the following. An expression for the normalized average stopping set distribution, yielding, in particular, a critical fraction of the block length above which codes have exponentially many stopping sets of that size. A relation between the degree distribution and the likely size of the smallest nonempty stopping set, showing that for a /spl radic/1-/spl lambda/'(0)/spl rho/'(1) fraction of codes with /spl lambda/'(0)/spl rho/'(1)2, the smallest nonempty stopping set is linear in the block length. Bounds on the average block error probability as a function of the erasure probability /spl epsi/, showing in particular that for codes with lowest variable degree 2, if /spl epsi/ is below a certain threshold, the asymptotic average block error probability is 1-/spl radic/1-/spl lambda/'(0)/spl rho/'(1)/spl epsi/.
In this paper, we study the asymptotic behavior of two quantities: the distribution of stopping sets, and the stopping number s/sup */-the size of the smallest nonempty stopping set in a code and use it to bound the error probability of LDPC codes with large blocklength. We derive an expression for the normalized average stopping set distribution of regular and irregular LDPC codes and use it to obtain a critical fraction of the block length above which codes have exponentially many stopping sets of that size.
This work presents an ensemble of irregular low-density parity check (LDPC) codes based on an ensemble of bipartite graphs, which formulated the average weight distribution. An analysis of the error performance of LDPC codes over a binary erasure channel together with an iterative decoding algorithm based on belief propagation has been clarified that a notion of stopping sets and their distribution with the asymptotic expression are derived. An irregular LDPC code ensemble that exhibits better performance in the sense of threshold is obtained by density evolution and explicitly formulates weight and stopping set distributions are defined.
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
This thesis addresses the topic of Low-Density Parity-Check (LDPC) code analysis, both asymptotically and for finite block lengths. Since in general it is a difficult problem to analyze individual code instances, ensemble averages are studied by following Gallager's original idea and results of Luby et al. Often, one can relate the insights gained by studying ensemble averages to statements regarding individual codes by proving that most elements in the ensemble behave "close" to the average. One important such average is the average weight distribution, another is the average pseudo-codeword distribution, where pseudo-codewords play the same role under iterative decoding as codewords do for maximum likelihood decoding. One of the main contributions of this thesis is the calculation of such averages for fully irregular LDPC code ensembles. Much of classical coding theory is aimed at the construction of codes with large minimum distance. This is so since away from capacity accurate bounds on the performance of a code can be given in terms of its minimum distance (or more generally, in terms of its weight distribution). Therefore, it is of interest to investigate what role the minimum distance plays for iteratively decoded LDPC code ensembles. In particular, sequences of capacity-achieving LDPC code ensembles of increasing length when transmission takes place over the Binary Erasure Channel (BEC) are investigated. It is shown that, under certain technical conditions, the minimum distance of such ensembles grows sub-linearly in the block length, a result which is somewhat surprising from a classical point of view. Specific attention is also given to the design of LDPC code ensembles, where an inherent trade-off is observed between achieving large minimum distance (which is relevant for the so called error-floor regime) and achieving a large threshold (which in the limit of long block lengths determines the worst channel on which transmission can be accomplished reliably). Most results on iterative coding systems to date address their asymptotic performance, i.e., their performance when the block length tends to infinity. For small and moderate block lengths the behavior of a code can deviate significantly from its asymptotic limit. It is therefore of high practical value to be able to analyze the finite-length performance of LDPC code ensembles. In this thesis, an exact such analysis is presented for iteratively decoded LDPC code ensembles over the BEC. In particular, expressions for the exact average bit and block erasure probabilities are computed by solving a set of recursions. Such an analysis is the starting point for a finite-length optimization, a topic which is slated for future work. The methods used in this thesis include a combinatorial approach (familiar to the coding society) as well as the powerful techniques developed in the statistical physics community, for example, the replica method or the mean-field approximation. Although the statistical physics techniques are ideally suited for the analysis of iterative coding systems, they are to date only accessible to a relatively small community. Therefore, an overview of these techniques is first presented using a language familiar to the coding theory community. Next, in order to highlight the differences and common points between the combinatorial and the statistical physics approaches, both techniques are applied to the weight distribution problem. It turns out that for regular ensembles, both methods yield the same result, while for irregular ensembles, they do differ in general.
The performance of low-density parity-check (LDPC) codes over the binary erasure channel for a low erasure probability is limited by small stopping sets. The frame error rate over the additive white Gaussian noise (AWGN) channel for a high signal-to-noise ratio is limited by small trapping sets and by the minimum distance of the LDPC code, which is equal to the codeword with the minimal Hamming weight. In this paper, we present a simple and fast algorithm based on the error impulse method to find small stopping sets in the Tanner graphs of LDPC codes. Since a codeword with small Hamming weight can be represented by a special stopping set, the algorithm can also be used to find the minimum distance of LDPC codes. Furthermore, we use the size of the small stopping sets and the minimum distance of the code to calculate asymptotic performance bounds for LDPC codes transmitted over the binary erasure and the AWGN channel, respectively and compare the bounds with simulations. 1
Low-density parity-check (LDPC) codes in conjunction with iterative decoding based on message-passing algorithms have been shown to achieve excellent performance over a variety of communication channels. In this dissertation, we investigate LDPC codes under two scenarios which present different challenges for providing robust communications. First, LDPC codes are analyzed and designed for time-selective, frequency-nonselective complex-fading channels where both the amplitude and the phase of the transmitted signal are altered by the channel. To combat the fading, we use a pilot symbol-assisted scheme where known pilot symbols are added to the LDPC code and used to help estimate the channel at the receiver. Using asymptotic, infinite-length analysis, we investigate several iterative, message-passing, joint-estimation-and-decoding strategies; optimal energy distribution between pilot and data symbols; and LDPC code design. Several interesting results are obtained regarding unification of analysis and code design. Next, we address the issue of achieving very low error rates with practical, finite-length LDPC codes for binary erasure channels. Finite-length LDPC codes suffer from error floors which limit the achievable error rate, and this error-floor performance is determined by stopping sets. Asymptotic analysis of weight and stopping-set enumerators, for codewords and stopping sets which grow linearly with codelength, has aided in designing codes with lower error floors but does not reflect the behavior of sublinearly-sized stopping sets, which can dominate the iterative-decoding, error-floor performance. Thus, we provide a perspective on protograph-based and standard LDPC ensemble enumerators, based on analysis of stopping sets with sublinear growth, which brings new insight into sublinear stopping-set behavior, advantages of protograph structure, and effects of precoding. We show for stopping sets that grow at most logarithmically with codelength, the enumerators follow a polynomial relationship with codelength, unlike the exponential relationship for linearly-growing stopping sets, and this polynomial relationship can be approximately captured by a single parameter. Further, we begin to address the question, Given finite stopping-set sizes and finite codelengths, do the stopping sets follow the behavior predicted by linear or sublinear analysis?