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

The Asymptotic Error Floor of LDPC Ensembles Under BP Decoding

Andrea Montanari A

Published Sep 27, 2006• 0 citations
OpenAlex

Abstract

We consider communication over binary memoryless symmetric channels using random elements from irregular low density parity check code (LDPC) ensembles, and belief propagation (BP) decoding.Under the assumption that the corresponding Tanner graph includes a non-vanishing fraction of degree 2 variable nodes, we determine the large blocklength behavior of the bit error rate for noise levels below threshold.More precisely, we show that the BP bit error rate is, asymptotically, F/n, where n is the blocklength and F an explicit constant.Surprisingly, this is the same behavior found for maximum likelihood (ML) decoding, implying that the BP and ML error floor are asymptotically equal.

Related papers

Asymptotic gaps between BP decoding and local-MAP decoding for low-density parity-check codes

Ryuhei Mori, Kenta Kasai, Tomoharu Shibuya +1 more

In this paper, we consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes. We consider MAP decoding not using a whole Tanner graph but only a neighborhood graph of fixed depth referred to as local-MAP decoding for deriving lower bounds of the error probability under message-passing decoding and bit-flipping decoding. The main result of this paper is to derive an asymptotic performance for regular ensembles under local-MAP decoding and to derive an asymptotic gap of the bit error probability between belief propagation (BP) and local-MAP decoding for irregular ensembles. Finally, we show the limit of the scaling parameter of these decodings when number of iterations tends to infinity.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•3 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.2204•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•2 citations

Performance of Belief Propagation for Decoding LDPC Codes in the Presence of Channel Estimation Error

Hamid Saeedi, Amir H. Banihashemi

In this paper, we investigate the performance of the belief propagation (BP) algorithm for decoding low-density parity-check codes over the additive white Gaussian noise channel when there is an incorrect estimate of the channel signal-to-noise ratio (SNR) (referred to as "SNR mismatch") at the decoder. At the extremes for over- and underestimation of SNR, the performance of BP tends to that of min-sum algorithm and the channel bit-error rate, respectively. Our results for regular codes indicate that the sensitivity to mismatch increases by increasing the variable-node degree and by decreasing the check-node degree. The effect of variable-node degree, however, appears to be more profound, such that at a given rate, the codes with the smallest variable and check degrees are more robust against SNR mismatch. For irregular codes, by comparing the thresholds of a few ensembles, we demonstrate that the ensemble which performs better in the absence of mismatch can perform worse in the presence of it. To obtain our asymptotic results, we propose a computationally efficient method based on the Gaussian approximation of density evolution in the presence of SNR mismatch. We also show that the asymptotic results are consistent with simulation results for codes with finite block lengths

IEEE Transactions on Communications•Jan 1, 2007•43 citations

On the universality of LDPC code ensembles under belief propagation and ML decoding

Boaz Shuval, Igal Sason

A universal design of low-density parity-check (LDPC) code ensembles which enables to operate reliably over various channels is of great interest. This paper considers the universality of LDPC code ensembles over sets of memoryless binary-input output-symmetric (MBIOS) channels, addressing their universality under belief-propagation (BP) and maximum-likelihood (ML) decoding. Based on the density evolution approach, closed-form, easy-to-calculate, analytical results related to the universality of LDPC code ensembles under BP decoding are derived. LP Bounds on the achievable rate of LDPC code ensembles over a set of equi-capacity channels are also derived. This paper considers the universality under ML decoding of properly selected regular LDPC code ensembles for the set of equi-capacity MBIOS channels. The full paper version related to this work [13] provides further results, full proofs, and additional discussions on the theorems.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 1, 2010•10 citations

Effects of Single-Cycle Structure on Iterative Decoding of Low-Density Parity-Check Codes

Ryuhei Mori, Toshiyuki Tanaka, Kenta Kasai +1 more

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as the blocklength tends to infinity, and the limit is obtained via density evolution. The finite-blocklength correction behaves like α(ε,t)/n+Θ(n-2) as the blocklengthntends to infinity where α(ε,t) denotes a specific constant determined by the code ensemble considered, the numbertof iterations, and the erasure probability ε of the BEC. In this paper, we derive a set of recursive formulas which allows the evaluation of the constant α(ε,t) for standard irregular ensembles. The dominant difference α(ε,t)/ncan be considered as effects of cycle-free and single-cycle structures of local graphs. Furthermore, it is confirmed via numerical simulations that estimation of the bit error probability using α(ε,t) is accurate even for small blocklengths.

arXiv:1010.0333•IEEE Transactions on Information Theory•Sep 15, 2012•2 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
We consider communication over binary memoryless symmetric channels using random elements from irregular low density parity check code (LDPC) ensembles, and belief propagation (BP) decoding.Under the assumption that the corresponding Tanner graph includes a non-vanishing fraction of degree 2 variable nodes, we determine the large blocklength behavior of the bit error rate for noise levels below threshold.More precisely, we show that the BP bit error rate is, asymptotically, F/n, where n is the blocklength and F an explicit constant.Surprisingly, this is the same behavior found for maximum likelihood (ML) decoding, implying that the BP and ML error floor are asymptotically equal.
In this paper, we consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes. We consider MAP decoding not using a whole Tanner graph but only a neighborhood graph of fixed depth referred to as local-MAP decoding for deriving lower bounds of the error probability under message-passing decoding and bit-flipping decoding. The main result of this paper is to derive an asymptotic performance for regular ensembles under local-MAP decoding and to derive an asymptotic gap of the bit error probability between belief propagation (BP) and local-MAP decoding for irregular ensembles. Finally, we show the limit of the scaling parameter of these decodings when number of iterations tends to infinity.
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.
In this paper, we investigate the performance of the belief propagation (BP) algorithm for decoding low-density parity-check codes over the additive white Gaussian noise channel when there is an incorrect estimate of the channel signal-to-noise ratio (SNR) (referred to as "SNR mismatch") at the decoder. At the extremes for over- and underestimation of SNR, the performance of BP tends to that of min-sum algorithm and the channel bit-error rate, respectively. Our results for regular codes indicate that the sensitivity to mismatch increases by increasing the variable-node degree and by decreasing the check-node degree. The effect of variable-node degree, however, appears to be more profound, such that at a given rate, the codes with the smallest variable and check degrees are more robust against SNR mismatch. For irregular codes, by comparing the thresholds of a few ensembles, we demonstrate that the ensemble which performs better in the absence of mismatch can perform worse in the presence of it. To obtain our asymptotic results, we propose a computationally efficient method based on the Gaussian approximation of density evolution in the presence of SNR mismatch. We also show that the asymptotic results are consistent with simulation results for codes with finite block lengths
A universal design of low-density parity-check (LDPC) code ensembles which enables to operate reliably over various channels is of great interest. This paper considers the universality of LDPC code ensembles over sets of memoryless binary-input output-symmetric (MBIOS) channels, addressing their universality under belief-propagation (BP) and maximum-likelihood (ML) decoding. Based on the density evolution approach, closed-form, easy-to-calculate, analytical results related to the universality of LDPC code ensembles under BP decoding are derived. LP Bounds on the achievable rate of LDPC code ensembles over a set of equi-capacity channels are also derived. This paper considers the universality under ML decoding of properly selected regular LDPC code ensembles for the set of equi-capacity MBIOS channels. The full paper version related to this work [13] provides further results, full proofs, and additional discussions on the theorems.
We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as the blocklength tends to infinity, and the limit is obtained via density evolution. The finite-blocklength correction behaves like α(ε,t)/n+Θ(n-2) as the blocklengthntends to infinity where α(ε,t) denotes a specific constant determined by the code ensemble considered, the numbertof iterations, and the erasure probability ε of the BEC. In this paper, we derive a set of recursive formulas which allows the evaluation of the constant α(ε,t) for standard irregular ensembles. The dominant difference α(ε,t)/ncan be considered as effects of cycle-free and single-cycle structures of local graphs. Furthermore, it is confirmed via numerical simulations that estimation of the bit error probability using α(ε,t) is accurate even for small blocklengths.
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.