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

arXiv:cs/0610052 · IEEE Transactions on Information Theory

Finite-Dimensional Bounds on ${\BBZ}_m$ and Binary LDPC Codes With Belief Propagation Decoders

Chih-Chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

Published Jan 1, 2007• 29 citations
arXivHTMLPDF

Abstract

This paper focuses on finite-dimensional upper and lower bounds on decodable thresholds of Zopfmand binary low-density parity-check (LDPC) codes, assuming belief propagation decoding on memoryless channels. A concrete framework is presented, admitting systematic searches for new bounds. Two noise measures are considered: the Bhattacharyya noise parameter and the soft bit value for a maximum a posteriori probability (MAP) decoder on the uncoded channel. For ZopfmLDPC codes, an iterative m-dimensional bound is derived for m-ary-input/symmetric-output channels, which gives a sufficient stability condition for ZopfmLDPC codes and is complemented by a matched necessary stability condition introduced herein. Applications to coded modulation and to codes with nonequiprobably distributed codewords are also discussed. For binary codes, two new lower bounds are provided for symmetric channels, including a two-dimensional iterative bound and a one-dimensional noniterative bound, the latter of which is the best known bound that is tight for binary-symmetric channels (BSCs), and is a strict improvement over the existing bound derived by the channel degradation argument. By adopting the reverse channel perspective, upper and lower bounds on the decodable Bhattacharyya noise parameter are derived for nonsymmetric channels, which coincides with the existing bound for symmetric channels

DOI
10.1109/tit.2006.887085

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•6 citations

Bounds on the performance of belief propagation decoding

David Burshtein, G. Miller

We consider Gallager's (1963) soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular LDPC codes.

IEEE Transactions on Information Theory•Jan 1, 2002•39 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

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

Iterative Decoding Performance Bounds for LDPC Codes on Noisy Channels

Chun-Hao Hsu, Achilleas Anastasopoulos

The asymptotic iterative decoding performances of low-density parity-check (LDPC) codes using min-sum (MS) and sum-product (SP) decoding algorithms on memoryless binary-input output-symmetric (MBIOS) channels are analyzed in this paper. For MS decoding, the analysis is done by upper bounding the bit error probability of the root bit of a tree code by the sequence error probability of a subcode of the tree code assuming the transmission of the all-zero codeword. The result is a recursive upper bound on the bit error probability after each iteration. For SP decoding, we derive a recursively determined lower bound on the bit error probability after each iteration. This recursive lower bound recovers the density evolution equation of LDPC codes on the binary erasure channel (BEC) with inequalities satisfied with equalities. A significant implication of this result is that the performance of LDPC codes under SP decoding on the BEC is an upper bound of the performance on all MBIOS channels with the same uncoded bit error probability. All results hold for the more general multi-edge type LDPC codes.

arXiv:cs/0607020•Jul 6, 2006•1 citation

Bounds on the performance of belief propagation decoding

D. Burshtein, G. Miller

We consider Gallager's (1963) soft decoding (belief propagation) algorithm for decoding low density parity check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as robustness to the initial values of the messages. Our results apply both to regular and irregular LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 13, 2002•2 citations
This paper focuses on finite-dimensional upper and lower bounds on decodable thresholds of Zopfmand binary low-density parity-check (LDPC) codes, assuming belief propagation decoding on memoryless channels. A concrete framework is presented, admitting systematic searches for new bounds. Two noise measures are considered: the Bhattacharyya noise parameter and the soft bit value for a maximum a posteriori probability (MAP) decoder on the uncoded channel. For ZopfmLDPC codes, an iterative m-dimensional bound is derived for m-ary-input/symmetric-output channels, which gives a sufficient stability condition for ZopfmLDPC codes and is complemented by a matched necessary stability condition introduced herein. Applications to coded modulation and to codes with nonequiprobably distributed codewords are also discussed. For binary codes, two new lower bounds are provided for symmetric channels, including a two-dimensional iterative bound and a one-dimensional noniterative bound, the latter of which is the best known bound that is tight for binary-symmetric channels (BSCs), and is a strict improvement over the existing bound derived by the channel degradation argument. By adopting the reverse channel perspective, upper and lower bounds on the decodable Bhattacharyya noise parameter are derived for nonsymmetric channels, which coincides with the existing bound for symmetric channels
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 Gallager's (1963) soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular 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.
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 asymptotic iterative decoding performances of low-density parity-check (LDPC) codes using min-sum (MS) and sum-product (SP) decoding algorithms on memoryless binary-input output-symmetric (MBIOS) channels are analyzed in this paper. For MS decoding, the analysis is done by upper bounding the bit error probability of the root bit of a tree code by the sequence error probability of a subcode of the tree code assuming the transmission of the all-zero codeword. The result is a recursive upper bound on the bit error probability after each iteration. For SP decoding, we derive a recursively determined lower bound on the bit error probability after each iteration. This recursive lower bound recovers the density evolution equation of LDPC codes on the binary erasure channel (BEC) with inequalities satisfied with equalities. A significant implication of this result is that the performance of LDPC codes under SP decoding on the BEC is an upper bound of the performance on all MBIOS channels with the same uncoded bit error probability. All results hold for the more general multi-edge type LDPC codes.
We consider Gallager's (1963) soft decoding (belief propagation) algorithm for decoding low density parity check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as robustness to the initial values of the messages. Our results apply both to regular and irregular LDPC codes.