IEEE International Symposium on Information Theory (ISIT)

Stopping set distribution of LDPC code ensembles

Alon Orlitsky, Krishnamurthy Viswanathan, J. Zhang

Published Jan 1, 2003• 24 citations

Abstract

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.

DOI: 10.1109/isit.2003.1228137

Related papers

Stopping Set Distribution of LDPC Code Ensembles

Alon Orlitsky, K. Viswanathan, J. Zhang

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

IEEE Transactions on Information TheoryFeb 28, 2005218 citations

On the Asymptotic Weight and Stopping Set Distribution of Regular LDPC Ensembles

Vishwambhar Rathi

In this correspondence, we estimate the variance of weight and stopping set distribution of regular low-density parity-check (LDPC) ensembles. Using this estimate and the second moment method we obtain bounds on the probability that a randomly chosen code from regular LDPC ensemble has its weight distribution and stopping set distribution close to respective ensemble averages. We are able to show that a large fraction of total number of codes have their weight and stopping set distribution close to the average

arXiv:cs/0512066IEEE Transactions on Information TheoryAug 29, 200632 citations

Average spectra for ensembles of LDPC codes and applications

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +1 more

The exact values of finite length average weight distributions for both binary ensembles and binary images of nonbinary ensembles of regular LDPC codes are computed. The exact average stopping set size distribution for the binary ensemble is also obtained. The computed spectra are applied in order to bound from above the average stopping redundancy of the ensemble of binary regular LDPC codes. The asymptotic typical normalized minimum distances for the binary image of the ensemble of nonbinary regular LDPC codes and the typical minimum stopping distances for the binary regular LDPC codes are also presented.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 201714 citations

Analysis of stopping constellation distribution for irregular non-binary LDPC code ensemble

T. Nozaki, Kenta Kasai, Kohichi Sakaniwa

The fixed points of the belief propagation decoder for non-binary low-density parity-check (LDPC) codes are referred to as stopping constellations. In this paper, we give the stopping constellation distributions for the irregular non-binary LDPC code ensembles defined over the general linear group. Moreover, we derive the exponential growth rate of the average number of the stopping constellation distributions in the limit of large code length.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20114 citations

Asymptotic weight and stopping set distributions for detailedly represented irregular LDPC code ensembles

Ryoji Ikegaya, Kenta Kasai, Tomoharu Shibuya +1 more

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.

IEEE International Symposium on Information Theory (ISIT)Dec 23, 200418 citations

Asymptotic Spectra of Trapping Sets in Regular and Irregular LDPC Code Ensembles

Olgica Milenković, Emina Soljanin, Philip Whiting

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

IEEE Transactions on Information TheoryJan 1, 2007134 citations