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/0410019

Finite-Length Scaling and Finite-Length Shift for Low-Density Parity-Check Codes

Amraoui, Abdelaziz, Andrea Montanari A, Richardson, Tom, Rudiger L. Urbanke

Published Oct 10, 2004• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.cs/0410019

Related papers

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

T. Richrdson, Amin Shokrollahi, Rudiger L. Urbanke

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•50 citations

Computing the threshold shift for general channels

Jeremie Ezri, Andrea Montanari A, Sewoong Oh +1 more

The ‘threshold’ of a code ensemble can be defined as the noise level at which the block error probability curve crosses 1/2. For ensembles of low-density parity check codes used over the binary erasure channel, the behavior of the threshold for large blocklengths is known in detail. It is characterized by an asymptotic threshold value, and a finite-blocklength shift parameter. Here we present a new method for computing the shift parameter that can be applied to general binary memoryless symmetric channels, and general message passing algorithms. We check that the new approach recovers the known parameters for erasure correction.

None•Jan 1, 2008•0 citations

Computing the threshold shift for general channels

Jeremie Ezri, Rudiger L. Urbanke, Andrea Montanari A +1 more

The ‘threshold’ of a code ensemble can be defined as the noise level at which the block error probability curve crosses 1/2. For ensembles of low-density parity check codes used over the binary erasure channel, the behavior of the threshold for large blocklengths is known in detail. It is characterized by an asymptotic threshold value, and a finite-blocklength shift parameter. Here we present a new method for computing the shift parameter that can be applied to general binary memoryless symmetric channels, and general message passing algorithms. We check that the new approach recovers the known parameters for erasure correction.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•5 citations

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

Finite Length Analysis of Low-Density Parity-Check Codes over the Binary Erasure Channel

C. Di, D. Proietti, E. Telatar +2 more

In this paper we are concerned with the finite length analysis of low-density paritycheck codes when used over the binary erasure channel.The main result is an exact expression for the average bit and block erasure probability for a given regular ensemble of low-density parity-check codes when decoded iteratively.We also present what we consider to be the most important open problems in this area.

•Oct 3, 2001•0 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
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 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.
The ‘threshold’ of a code ensemble can be defined as the noise level at which the block error probability curve crosses 1/2. For ensembles of low-density parity check codes used over the binary erasure channel, the behavior of the threshold for large blocklengths is known in detail. It is characterized by an asymptotic threshold value, and a finite-blocklength shift parameter. Here we present a new method for computing the shift parameter that can be applied to general binary memoryless symmetric channels, and general message passing algorithms. We check that the new approach recovers the known parameters for erasure correction.
The ‘threshold’ of a code ensemble can be defined as the noise level at which the block error probability curve crosses 1/2. For ensembles of low-density parity check codes used over the binary erasure channel, the behavior of the threshold for large blocklengths is known in detail. It is characterized by an asymptotic threshold value, and a finite-blocklength shift parameter. Here we present a new method for computing the shift parameter that can be applied to general binary memoryless symmetric channels, and general message passing algorithms. We check that the new approach recovers the known parameters for erasure correction.
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 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.