Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Conditional entropy of non-binary LDPC codes over the BEC

Vishwambhar Rathi

Published Jul 1, 2008• 14 citations
Publisher

Abstract

We consider transmission over the binary erasure channel (BEC) using non-binary LDPC codes. We generalize the concept of stopping sets to non-binary LDPC codes. We give a combinatorial characterization of decoding failures for non-binary LDPC codes decoded via Belief Propagation (BP). Using the density evolution analysis, we compute the asymptotic residual degree distribution for non-binary LDPC codes. In order to show that asymptotically almost every code in the non-binary LDPC ensemble has a rate equal to the design rate, we generalize the arguments of Measson, Montanari, and Urbanke to the non-binary setting. This generalization enables us to compute the conditional entropy of non-binary LDPC codes. We observe that the Maxwell construction of Measson, Montanari, and Urbanke relating the performance of MAP and BP decoding, holds in the setting of non-binary LDPC codes.

DOI
10.1109/isit.2008.4595126

Related papers

Some Results on MAP Decoding of Non-Binary LDPC Codes Over the BEC

Vishwambhar Rathi, Iryna Andriyanova

In this paper, the transmission over the binary erasure channel (BEC) using non-binary LDPC (NBLDPC) codes is considered. The concept of peeling decoder and stopping sets is generalized to NBLDPC codes. Using these generalizations, a combinatorial characterization of decoding failures of NBLDPC codes is given, under assumption that the Belief Propagation (BP) decoder is used. Then, the residual ensemble of codes resulted by the BP decoder is defined and the design rate and the expectation of total number of codewords of the residual ensemble are computed. The decoding failure criterion combined with the density evolution analysis helps us to compute the asymptotic residual degree distribution for NBLDPC codes. Our approach to compute the residual degree distribution on the check node side is not efficient as it is based on enumeration of all the possible connections on the check node side which satisfy the decoding failure criterion. So, the computation of the asymptotic check node side residual degree distribution and further part of our analysis is performed for NBLDPC codes over GF2mwithm= 2 . In order to show that asymptotically almost every code in such LDPC ensemble has a rate equal to the design rate, we generalize the argument of the Maxwell construction to NBLDPC codes, defined over GF22. It is also observed that, like in the binary setting, the Maxwell construction, relating the performance of MAP and BP decoding holds in this setting.

IEEE Transactions on Information Theory•Mar 15, 2011•10 citations

Non-binary LDPC codes and EXIT like functions

Vishwambhar Rathi

In the first part of this thesis we are interested in the asymptotic performance analysis of Non-Binary Low-Density Parity-Check (NBLDPC) codes over the Binary Erasure Channel (BEC) decoded via the suboptimal Belief Propagation (BP) decoder as well as the optimal Maximum-A-Posteriori (MAP) decoder. Previously, NBLDPC codes defined with respect to a finite field have been studied in the literature. Unfortunately, for these codes the asymptotic analysis of the BP decoder in terms of density evolution is cumbersome since the involved densities "live" in a high dimensional space. To alleviate this problem, we introduce ensembles defined with respect to the general linear group. For these ensembles the density evolution equations can be written in a compact form. We compute thresholds for different alphabet sizes for various NBLDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. We also conjecture the stability condition for NBLDPC ensembles defined with respect to finite fields over any binary memoryless symmetric channel. We then consider the performance of NBLDPC codes under MAP decoding when transmission takes place over the BEC. Towards this goal, we generalize the concepts of the peeling decoder and stopping sets to NBLDPC codes. Using these concepts, we give a combinatorial characterization of decoding failures for NBLDPC codes decoded via the BP decoder. We use the decoding failure criterion and the density evolution analysis to compute the asymptotic residual degree distribution for NBLDPC codes. The rate of this residual ensemble gives the conditional entropy of the NBLDPC code. To compute the rate of the residual ensemble we generalize the criterion of [1] to the non-binary setting, which, when satisfied, guarantees that almost every code in the ensemble has a rate equal to the design rate. We observe that the Maxwell construction of [1], relating the performance of MAP and BP decoding via the Extended BP GEXIT (EBP GEXIT [2]) function, holds in the setting of NBLDPC codes. The weight and stopping set distribution of a code are related to its performance under the MAP and the BP decoder respectively. We first concentrate on the weight distribution of regular NBLDPC ensembles. We derive the average weight distribution of regular NBLDPC ensembles. Using this, we derive the average of equivalent binary weight distribution of regular NBLDPC ensembles. We show that as the alphabet size becomes larger the equivalent binary weight distribution converges to the weight distribution of Gallager's random parity check ensemble. The average weight distribution of binary LDPC ensembles has been extensively studied in the literature. Much less is known about the probability distribution of this quantity. In particular, the question of the concentration of the weight distribution around the ensemble average has not been addressed. We compute the variance of the weight distribution of binary regular LDPC ensembles. Using this and the second moment method we obtain bounds on the probability that a randomly chosen code has its weight distribution close to the ensemble average. We show that a large fraction of the total number of codes have their weight distribution close to the average. We apply the same technique for the stopping set distribution of binary regular LDPC ensembles. Again we show that a large fraction of total number of codes have their stopping set distribution close to the ensemble average. In the last part of this thesis we address the question of the existence of the EBP GEXIT function. The EBP GEXIT function plays a fundamental role in the asymptotic analysis of sparse graph codes. For transmission over the BEC using binary LDPC codes, the analytic properties of the EBP GEXIT function are relatively simple and well understood. The case of general BMS channel is much harder and even the existence of the curve is not known in general. We introduce some tools from non-linear analysis which can be useful to prove the existence of EXIT like curves in some cases. The main tool is the Krasnoselskii-Rabinowitz (KR) bifurcation theorem.

•Jan 1, 2008•12 citations

Asymptotic bit error probability of LDPC codes for the binary erasure channel with finite number of iterations

Ryuhei Mori, Kenta Kasai, Tomoharu Shibuya +1 more

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. Furthermore, a gap between the bit error probability after finite number of iterations for finite block length n and that for infinite block length is asymptotically α/n, where α denotes a speci..c constant determined by a degree distribution, a number of iterations and erasure probability. Our main result is to derive an ef..cient algorithm for calculating α for regular ensembles.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•4 citations

Finite-length analysis of turbo decoding on the binary erasure channel

Eirik Rosnes, Øyvind Ytrehus

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. In the first part we describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or until the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum size turbo stopping set which is also a subset of the set of erased positions. In the second part we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•4 citations

The Asymptotic Bit Error Probability of LDPC Codes for the Binary Erasure Channel with Finite Iteration Number

Ryuhei Mori, Kenta Kasai, Tomoharu Shibuya +1 more

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. The bit error probability for infinite block length is known by density evolution and it is well known that a difference between the bit error probability at finite iteration number for finite block length $n$ and for infinite block length is asymptotically $α/n$, where $α$ is a specific constant depending on the degree distribution, the iteration number and the erasure probability. Our main result is to derive an efficient algorithm for calculating $α$ for regular ensembles. The approximation using $α$ is accurate for $(2,r)$-regular ensembles even in small block length.

arXiv:0801.0931•Jan 7, 2008•0 citations

Analysis of decoding error probability for finite length LDPC codes

隆之 野崎

Low-density parity-check (LDPC) codes are linear codes defined by sparse parity check matrices.Due to the sparseness of the parity check matrices, LDPC codes are efficiently decoded by the belief propagation (BP) decoder.It is known that non-binary LDPC codes can outperform binary ones.However, the decoding complexity grows with the size of non-binary alphabets.Hence, there is a trade-off between performance and complexity.In this dissertation, we focus on both binary and non-binary LDPC codes.We analyze the decoding error probability for finite length LDPC codes under BP decoding.The curve of the decoding error probability for finite length LDPC codes, as a function of channel error probability, is divided into two regions called waterfall region and error floor region.We analyze the decoding error probability in the waterfall region for binary LDPC codes and in the error floor region for non-binary LDPC codes.The main results of this dissertation are summarized as follows:• We analyze the decoding erasure probabilities of waterfall regions for binary LDPC codes over binary erasure channels (BECs) without any assumptions by analytically solving the covariance evolution.• We propose a method to lower the decoding error rates in the error floors of non-binary LDPC codes defined over Galois field and general linear group transmitted over the BEC, the memoryless binary-input output-symmetric (MBIOS) channel and q-ary memoryless symmetric (q-MS) channel.Simulation results show that the decoding error rates of the codes designed by the proposed method outperform those of the codes designed by the conventional method proposed by Poulliat et al.• We give lower bounds of decoding error rates in the error floor regions for non-binary LDPC codes over the BEC, MBIOS channel and q-MS channel.Simulation results show that those lower bounds are tight.Moreover, we show that the decoding error rates for non-binary LDPC codes defined over general linear group have same decoding performance in the error floor regions with that for non-binary LDPC codes defined over Galois field.Furthermore, we show that this tight lower bound monotonically decreases, as the order of Galois field of non-binary LDPC code increases in the BEC and binary additive white Gaussian noise channel.iii • We derive the weight distribution of the decoding error patterns in the BP decoder for non-binary LDPC codes defined over general linear group transmitted over the BEC.

•Jan 1, 2012•0 citations
We consider transmission over the binary erasure channel (BEC) using non-binary LDPC codes. We generalize the concept of stopping sets to non-binary LDPC codes. We give a combinatorial characterization of decoding failures for non-binary LDPC codes decoded via Belief Propagation (BP). Using the density evolution analysis, we compute the asymptotic residual degree distribution for non-binary LDPC codes. In order to show that asymptotically almost every code in the non-binary LDPC ensemble has a rate equal to the design rate, we generalize the arguments of Measson, Montanari, and Urbanke to the non-binary setting. This generalization enables us to compute the conditional entropy of non-binary LDPC codes. We observe that the Maxwell construction of Measson, Montanari, and Urbanke relating the performance of MAP and BP decoding, holds in the setting of non-binary LDPC codes.
In this paper, the transmission over the binary erasure channel (BEC) using non-binary LDPC (NBLDPC) codes is considered. The concept of peeling decoder and stopping sets is generalized to NBLDPC codes. Using these generalizations, a combinatorial characterization of decoding failures of NBLDPC codes is given, under assumption that the Belief Propagation (BP) decoder is used. Then, the residual ensemble of codes resulted by the BP decoder is defined and the design rate and the expectation of total number of codewords of the residual ensemble are computed. The decoding failure criterion combined with the density evolution analysis helps us to compute the asymptotic residual degree distribution for NBLDPC codes. Our approach to compute the residual degree distribution on the check node side is not efficient as it is based on enumeration of all the possible connections on the check node side which satisfy the decoding failure criterion. So, the computation of the asymptotic check node side residual degree distribution and further part of our analysis is performed for NBLDPC codes over GF2mwithm= 2 . In order to show that asymptotically almost every code in such LDPC ensemble has a rate equal to the design rate, we generalize the argument of the Maxwell construction to NBLDPC codes, defined over GF22. It is also observed that, like in the binary setting, the Maxwell construction, relating the performance of MAP and BP decoding holds in this setting.
In the first part of this thesis we are interested in the asymptotic performance analysis of Non-Binary Low-Density Parity-Check (NBLDPC) codes over the Binary Erasure Channel (BEC) decoded via the suboptimal Belief Propagation (BP) decoder as well as the optimal Maximum-A-Posteriori (MAP) decoder. Previously, NBLDPC codes defined with respect to a finite field have been studied in the literature. Unfortunately, for these codes the asymptotic analysis of the BP decoder in terms of density evolution is cumbersome since the involved densities "live" in a high dimensional space. To alleviate this problem, we introduce ensembles defined with respect to the general linear group. For these ensembles the density evolution equations can be written in a compact form. We compute thresholds for different alphabet sizes for various NBLDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. We also conjecture the stability condition for NBLDPC ensembles defined with respect to finite fields over any binary memoryless symmetric channel. We then consider the performance of NBLDPC codes under MAP decoding when transmission takes place over the BEC. Towards this goal, we generalize the concepts of the peeling decoder and stopping sets to NBLDPC codes. Using these concepts, we give a combinatorial characterization of decoding failures for NBLDPC codes decoded via the BP decoder. We use the decoding failure criterion and the density evolution analysis to compute the asymptotic residual degree distribution for NBLDPC codes. The rate of this residual ensemble gives the conditional entropy of the NBLDPC code. To compute the rate of the residual ensemble we generalize the criterion of [1] to the non-binary setting, which, when satisfied, guarantees that almost every code in the ensemble has a rate equal to the design rate. We observe that the Maxwell construction of [1], relating the performance of MAP and BP decoding via the Extended BP GEXIT (EBP GEXIT [2]) function, holds in the setting of NBLDPC codes. The weight and stopping set distribution of a code are related to its performance under the MAP and the BP decoder respectively. We first concentrate on the weight distribution of regular NBLDPC ensembles. We derive the average weight distribution of regular NBLDPC ensembles. Using this, we derive the average of equivalent binary weight distribution of regular NBLDPC ensembles. We show that as the alphabet size becomes larger the equivalent binary weight distribution converges to the weight distribution of Gallager's random parity check ensemble. The average weight distribution of binary LDPC ensembles has been extensively studied in the literature. Much less is known about the probability distribution of this quantity. In particular, the question of the concentration of the weight distribution around the ensemble average has not been addressed. We compute the variance of the weight distribution of binary regular LDPC ensembles. Using this and the second moment method we obtain bounds on the probability that a randomly chosen code has its weight distribution close to the ensemble average. We show that a large fraction of the total number of codes have their weight distribution close to the average. We apply the same technique for the stopping set distribution of binary regular LDPC ensembles. Again we show that a large fraction of total number of codes have their stopping set distribution close to the ensemble average. In the last part of this thesis we address the question of the existence of the EBP GEXIT function. The EBP GEXIT function plays a fundamental role in the asymptotic analysis of sparse graph codes. For transmission over the BEC using binary LDPC codes, the analytic properties of the EBP GEXIT function are relatively simple and well understood. The case of general BMS channel is much harder and even the existence of the curve is not known in general. We introduce some tools from non-linear analysis which can be useful to prove the existence of EXIT like curves in some cases. The main tool is the Krasnoselskii-Rabinowitz (KR) bifurcation theorem.
We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. Furthermore, a gap between the bit error probability after finite number of iterations for finite block length n and that for infinite block length is asymptotically α/n, where α denotes a speci..c constant determined by a degree distribution, a number of iterations and erasure probability. Our main result is to derive an ef..cient algorithm for calculating α for regular ensembles.
This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. In the first part we describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or until the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum size turbo stopping set which is also a subset of the set of erased positions. In the second part we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results
We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. The bit error probability for infinite block length is known by density evolution and it is well known that a difference between the bit error probability at finite iteration number for finite block length nnn and for infinite block length is asymptotically α/nα/nα/n, where ααα is a specific constant depending on the degree distribution, the iteration number and the erasure probability. Our main result is to derive an efficient algorithm for calculating ααα for regular ensembles. The approximation using ααα is accurate for (2,r)(2,r)(2,r)-regular ensembles even in small block length.
Low-density parity-check (LDPC) codes are linear codes defined by sparse parity check matrices.Due to the sparseness of the parity check matrices, LDPC codes are efficiently decoded by the belief propagation (BP) decoder.It is known that non-binary LDPC codes can outperform binary ones.However, the decoding complexity grows with the size of non-binary alphabets.Hence, there is a trade-off between performance and complexity.In this dissertation, we focus on both binary and non-binary LDPC codes.We analyze the decoding error probability for finite length LDPC codes under BP decoding.The curve of the decoding error probability for finite length LDPC codes, as a function of channel error probability, is divided into two regions called waterfall region and error floor region.We analyze the decoding error probability in the waterfall region for binary LDPC codes and in the error floor region for non-binary LDPC codes.The main results of this dissertation are summarized as follows:• We analyze the decoding erasure probabilities of waterfall regions for binary LDPC codes over binary erasure channels (BECs) without any assumptions by analytically solving the covariance evolution.• We propose a method to lower the decoding error rates in the error floors of non-binary LDPC codes defined over Galois field and general linear group transmitted over the BEC, the memoryless binary-input output-symmetric (MBIOS) channel and q-ary memoryless symmetric (q-MS) channel.Simulation results show that the decoding error rates of the codes designed by the proposed method outperform those of the codes designed by the conventional method proposed by Poulliat et al.• We give lower bounds of decoding error rates in the error floor regions for non-binary LDPC codes over the BEC, MBIOS channel and q-MS channel.Simulation results show that those lower bounds are tight.Moreover, we show that the decoding error rates for non-binary LDPC codes defined over general linear group have same decoding performance in the error floor regions with that for non-binary LDPC codes defined over Galois field.Furthermore, we show that this tight lower bound monotonically decreases, as the order of Galois field of non-binary LDPC code increases in the BEC and binary additive white Gaussian noise channel.iii • We derive the weight distribution of the decoding error patterns in the BP decoder for non-binary LDPC codes defined over general linear group transmitted over the BEC.