© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

IEEE International Symposium on Information Theory (ISIT)

Finite-length analysis of various low-density parity-check ensembles for the binary erasure channel

T. Richrdson, Amin Shokrollahi, Rudiger L. Urbanke

Published Jun 25, 2003• 50 citations

Abstract

We investigate the average erasure probability of the belief propagation algorithm over the binary erasure channel (BEC) for various finite-length low-density parity-check (LDPC) ensembles. In particular, we give tight upper bounds on the "error floor", i.e., on the contribution to the erasure probability stemming from relatively small deficiencies in the graph. We also define and analyse "expurgated" ensembles and give upper bounds on the error floor of "typical" codes. Finally, we show that typical codes of properly chosen ensembles have an erasure correcting radius which grows linearly in the block length. The presented method provides valuable insight into how finite-length codes should be designed. Although the standard ensemble can achieve capacity on the BEC, the construction of good finite-length codes requires careful control of the structure of the degree two variable nodes. In this paper, we investigate the standard ensemble, the Poisson ensemble, an ensemble in which degree two nodes are added in a cycle, and an ensemble in which different degree two variable nodes have distinct neighboring check nodes.

DOI: 10.1109/isit.2002.1023273

Related papers

Finite-length analysis of low-density parity-check codes on the binary erasure channel

Changyan Di, D. Proietti, I. Emre Telatar +2 more

In this paper, we are concerned with the finite-length analysis of low-density parity-check (LDPC) codes when used over the binary erasure channel (BEC). The main result is an expression for the exact average bit and block erasure probability for a given regular ensemble of LDPC codes when decoded iteratively. We also give expressions for upper bounds on the average bit and block erasure probability for regular LDPC ensembles and the standard random ensemble under maximum-likelihood (ML) decoding. Finally, we present what we consider to be the most important open problems in this area.

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

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 Scaling and Finite-Length Shift for Low-Density Parity-Check Codes

Amraoui, Abdelaziz, Andrea Montanari A, Richardson, Tom +1 more

Consider communication over the binary erasure channel BEC using random low-density parity-check codes with finite-blocklength n from `standard' ensembles. We show that large error events is conveniently described within a scaling theory, and explain how to estimate heuristically their effect. Among other quantities, we consider the finite length threshold e(n), defined by requiring a block error probability P_B = 1/2. For ensembles with minimum variable degree larger than two, the following expression is argued to hold e(n) = e -e_1 n^{-2/3} +Θ(n^{-1}) with a calculable shift} parameter e_1>0.

arXiv:cs/0410019•Oct 10, 2004•6 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

We investigate the average erasure probability of the belief propagation algorithm over the binary erasure channel (BEC) for various finite-length low-density parity-check (LDPC) ensembles. In particular, we give tight upper bounds on the "error floor", i.e., on the contribution to the erasure probability stemming from relatively small deficiencies in the graph. We also define and analyse "expurgated" ensembles and give upper bounds on the error floor of "typical" codes. Finally, we show that typical codes of properly chosen ensembles have an erasure correcting radius which grows linearly in the block length. The presented method provides valuable insight into how finite-length codes should be designed. Although the standard ensemble can achieve capacity on the BEC, the construction of good finite-length codes requires careful control of the structure of the degree two variable nodes. In this paper, we investigate the standard ensemble, the Poisson ensemble, an ensemble in which degree two nodes are added in a cycle, and an ensemble in which different degree two variable nodes have distinct neighboring check nodes.

In this paper, we are concerned with the finite-length analysis of low-density parity-check (LDPC) codes when used over the binary erasure channel (BEC). The main result is an expression for the exact average bit and block erasure probability for a given regular ensemble of LDPC codes when decoded iteratively. We also give expressions for upper bounds on the average bit and block erasure probability for regular LDPC ensembles and the standard random ensemble under maximum-likelihood (ML) decoding. Finally, we present what we consider to be the most important open problems in this area.

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.

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.

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.

Consider communication over the binary erasure channel BEC using random low-density parity-check codes with finite-blocklength n from `standard' ensembles. We show that large error events is conveniently described within a scaling theory, and explain how to estimate heuristically their effect. Among other quantities, we consider the finite length threshold e(n), defined by requiring a block error probability P_B = 1/2. For ensembles with minimum variable degree larger than two, the following expression is argued to hold e(n) = e -e_1 n^{-2/3} +Θ(n^{-1}) with a calculable shift} parameter e_1>0.

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.