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 Convention of Electrical and Electronics Engineers in Israel

Bounds on the thresholds of non-binary LDPC codes

Oron Levi, David Burshtein

Published Mar 1, 2008• 2 citations
Publisher

Abstract

LDPC codes over non-binary Galois fields were proposed for reliable transmission over arbitrary discrete memoryless channels and in particular for transmission in the bandwidth efficient regime. It was shown that some properties, originally derived for binary LDPC codes, extend to the appropriately defined non-binary ensemble. However, the extension of density evolution to this ensemble results in a prohibitive computational complexity. In this paper we analyze the performance by tracking the evolution of the Bhattacharya noise parameter associated with the decoding messages, and derive upper and lower bounds on its evolution. These bounds are then used to obtain upper and lower bounds on the asymptotic threshold required for reliable communication.

DOI
10.1109/eeei.2008.4736544

Related papers

Bounds on the Belief Propagation Threshold of Non-Binary LDPC Codes

Leonid Geller, David Burshtein

We consider low-density parity-check (LDPC) code ensembles over non-binary Galois fields when used for transmission over arbitrary discrete memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter, we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles.

IEEE Transactions on Information Theory•Mar 9, 2016•7 citations

Bounds on the belief propagation threshold of non-binary LDPC codes

Leonid Geller, David Burshtein

We consider LDPC code ensembles over non-binary Galois fields, when used for transmission over arbitrary memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles.

IEEE Information Theory Workshop (ITW)•Sep 1, 2012•1 citation

Density evolution, thresholds and the stability condition for non-binary LDPC codes

Vishwambhar Rathi, Rudiger L. Urbanke

The density evolution equations for non-binary low-density parity-check (LDPC) ensembles when transmission takes place over the binary erasure channel are derived. Ensembles defined with respect to the general linear group over the binary field are introduced. For these ensembles the density evolution equations can be written compactly. The density evolution for the general linear group helps in understanding the density evolution for codes defined with respect to finite fields. Thresholds are computed for different alphabet sizes for various LDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. The stability condition for non-binary LDPC ensembles over any binary memoryless symmetric channel is stated. Upper bounds on the MAP thresholds for various non-binary ensembles based on EXIT curves and the area theorem are given.

arXiv:cs/0511100•IEE Proceedings - Communications•Jan 1, 2005•101 citations

Bounds on the maximum-likelihood decoding error probability of low-density parity-check codes

G. Miller, David Burshtein

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

IEEE Transactions on Information Theory•Jan 1, 2001•157 citations

Bounds on the maximum likelihood decoding error probability of low density parity check codes

G. Miller, D. Burshtein

We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•7 citations

LDPC Codes Over the BEC: Bounds and Decoding Algorithms

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

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

IEEE Transactions on Communications•Nov 6, 2018•5 citations
LDPC codes over non-binary Galois fields were proposed for reliable transmission over arbitrary discrete memoryless channels and in particular for transmission in the bandwidth efficient regime. It was shown that some properties, originally derived for binary LDPC codes, extend to the appropriately defined non-binary ensemble. However, the extension of density evolution to this ensemble results in a prohibitive computational complexity. In this paper we analyze the performance by tracking the evolution of the Bhattacharya noise parameter associated with the decoding messages, and derive upper and lower bounds on its evolution. These bounds are then used to obtain upper and lower bounds on the asymptotic threshold required for reliable communication.
We consider low-density parity-check (LDPC) code ensembles over non-binary Galois fields when used for transmission over arbitrary discrete memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter, we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles.
We consider LDPC code ensembles over non-binary Galois fields, when used for transmission over arbitrary memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles.
The density evolution equations for non-binary low-density parity-check (LDPC) ensembles when transmission takes place over the binary erasure channel are derived. Ensembles defined with respect to the general linear group over the binary field are introduced. For these ensembles the density evolution equations can be written compactly. The density evolution for the general linear group helps in understanding the density evolution for codes defined with respect to finite fields. Thresholds are computed for different alphabet sizes for various LDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. The stability condition for non-binary LDPC ensembles over any binary memoryless symmetric channel is stated. Upper bounds on the MAP thresholds for various non-binary ensembles based on EXIT curves and the area theorem are given.
We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.
We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.