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 Transactions on Information Theory

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

Vishwambhar Rathi, Iryna Andriyanova

Published Mar 15, 2011• 10 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2011.2110930

Related papers

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

Conditional entropy of non-binary LDPC codes over the BEC

Vishwambhar Rathi

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.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•14 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

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

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

Turbo Decoding on the Binary Erasure Channel: Finite-Length Analysis and Turbo Stopping Sets

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 decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms ofstopping sets. 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 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-sizeturbo stopping setwhich is also a subset of the set of erased positions. Furthermore, 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. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garelloet al.in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code.

arXiv:cs/0602072•IEEE Transactions on Information Theory•Nov 1, 2007•27 citations
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 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.
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.
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. 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 decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms ofstopping sets. 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 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-sizeturbo stopping setwhich is also a subset of the set of erased positions. Furthermore, 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. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garelloet al.in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code.