arXiv:cs/0512066 · IEEE Transactions on Information Theory

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

Vishwambhar Rathi

Published Aug 29, 2006• 32 citations

Abstract

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

DOI: 10.1109/tit.2006.880065

Related papers

On the asymptotic weight distribution of regular LDPC ensembles

Vishwambhar Rathi

We estimate the variance of weight distribution of regular 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 close to the ensemble average. We are able to show that a large fraction of total number of codes have their weight distribution close to the average

IEEE International Symposium on Information Theory (ISIT)Jan 1, 200511 citations

Weight and Trapping Set Distributions for Non-Binary Regular Low-Density Parity-Check Code Ensembles

Emna Ben Yacoub

The variances of weight and trapping set distributions of non-binary regular low-density parity-check ensembles are derived. Using the second moment method, bounds on the probabilities that a randomly chosen code from the ensemble has its weight and trapping set distributions close to the ensemble averages are obtained.

IEEE International Symposium on Information Theory (ISIT)Jun 25, 20230 citations

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

Weight Distributions of Regular Low-Density Parity-Check Codes Over Finite Fields

Shengtian Yang, Thomas Honold, Yan Chen +2 more

The average weight distribution of a regular low-density parity-check (LDPC) code ensemble over a finite field is thoroughly analyzed. In particular, a precise asymptotic approximation of the average weight distribution is derived for the small-weight case, and a series of fundamental qualitative properties of the asymptotic growth rate of the average weight distribution are proved. Based on this analysis, a general result, including all previous results as special cases, is established for the minimum distance of individual codes in a regular LDPC code ensemble.

arXiv:1010.2030IEEE Transactions on Information TheoryAug 3, 201110 citations

Stopping set distribution of LDPC code ensembles

Alon Orlitsky, Krishnamurthy Viswanathan, J. Zhang

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.

IEEE International Symposium on Information Theory (ISIT)Jan 1, 200324 citations

Average Coset Weight Distributions of Gallager's LDPC Code Ensemble

Tadashi Wadayama

In this correspondence, the average coset weight distributions of Gallager's low-density parity-check (LDPC) code ensemble are investigated. Gallager's LDPC code ensemble consists of regular mtimesn-LDPC matrices with column weight j and row weight k. The average coset weight distribution can be derived by enumerating the number of parity-check matrices in the ensemble satisfying certain conditions. Based on combinatorial arguments, a formula for the average coset weight distribution will be proved. From the formula, we can show some properties of the average coset weight distributions such as equivalence classes of syndromes, symmetry of the distributions, and a lower bound on coset weight

IEEE Transactions on Information TheoryJun 28, 20055 citations