IEEE International Symposium on Information Theory (ISIT)

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

Ryoji Ikegaya, Kenta Kasai, Tomoharu Shibuya, Kohichi Sakaniwa

Published Dec 23, 2004• 18 citations

Abstract

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.

DOI: 10.1109/isit.2004.1365243

Related papers

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 stopping constellation distributions in the limit of large codelength.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20111 citation

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

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

隆之野﨑, Kenta Kasai, KOHICHI SAKANIWA

The fixed points of the belief propagation decoder for nonbinary 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 stopping constellation distributions in the limit of large codelength.

Aug 1, 20110 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

Finite-length analysis of irregular expurgated LDPC codes under finite number of iterations

Ryuhei Mori, Toshiyuki Tanaka, Kenta Kasai +1 more

Communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding is considered. The average bit error probability of an irregular LDPC code ensemble after a fixed number of iterations converges to a limit, which is calculated via density evolution, as the blocklength n tends to infinity. The difference between the bit error probability with blocklength n and the large-blocklength limit behaves asymptotically like ¿/n, where the coefficient ¿ depends on the ensemble, the number of iterations and the erasure probability of the BEC. In, ¿ is calculated for regular ensembles. In this paper, ¿ for irregular expurgated ensembles is derived. It is demonstrated that convergence of numerical estimates of ¿ to the analytic result is significantly fast for irregular unexpurgated ensembles.

arXiv:0901.2204IEEE International Symposium on Information Theory (ISIT)Jun 1, 20092 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