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 International Symposium on Information Theory (ISIT)

A Generalization of the Finite-Length Scaling Approach Beyond the BEC

Jeremie Ezri, Andrea Montanari A, Rudiger L. Urbanke

Published Jun 1, 2007• 18 citations
Publisher

Abstract

We want to extend the approximation of the error probability via a scaling approach from the BEC to general binary-input memoryless output-symmetric (BMS) channels. In particular, we consider such scaling laws for regular LDPC ensembles and message-passing (MP) decoders with a finite number of messages. We first show how to re-derive the scaling law for transmission over the BEC using an ";EXIT-like"; curve instead of the density evolution curve of the peeling decoder. The advantage of the new derivation is that the new expression of the scaling parameter a only contains quantities that can be meaningfully interpreted also for general message-passing algorithms. In particular, this expression only depends on the curvature of the EXIT-like curve as well as the variance of the messages, both taken at the critical channel parameter. We discuss how to compute these quantities for general MP algorithms and we evaluate the expressions for the specific cases of the Gallager algorithm A as well as the Decoder with Erasures and compare the resulting predictions on the error probability with simulation results.

DOI
10.1109/isit.2007.4557356

Related papers

Finite-Length Scaling For Gallager A

Jeremie Ezri, Andrea Montanari A, Rudiger L. Urbanke

We consider LDPC codes, transmission over the binary symmetric channel (BSC), and decoding using Gallager's algorithm A. For those ensembles whose threshold is determined by the behavior of the algorithm at the beginning of the decoding process we derive a scaling law. This scaling law has the same form as the scaling law which was established for the the case of transmission over the binary erasure channel (BEC). We show how the scaling parameters can be computed and point out some interesting open challenges.

Allerton Conference on Communication, Control, and Computing•Jan 1, 2006•3 citations

The slope scaling parameter for general channels, decoders, and ensembles

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

Scaling laws are a powerful way to analyze the performance of moderately sized iteratively decoded sparse graph codes. Our aim is to provide an easily usable finite-length optimization tool that is applicable to the wide variety of channels, blocklengths, error probability requirements, and decoders that one encounters for practical systems. The tool is aimed at non-experts in the field, who need to quickly find code designs that are comparable with the best known codes available today but do not have the luxury of spending months in doing so. In previous work we have shown how to compute scaling parameters for transmission over the binary erasure channel, as well as general channels and general quantized message-passing decoders when applied to regular ensembles. In this paper we show how to compute the message variance for a fixed number of iterations for irregular low-density parity-check ensembles. From these calculations the basic scaling parameter alpha can be deduced by determining the leading term of the limiting expression when the number of iterations tends to infinity and the channel parameter approaches the density evolution threshold.

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

Non-binary LDPC codes and EXIT like functions

Vishwambhar Rathi

In the first part of this thesis we are interested in the asymptotic performance analysis of Non-Binary Low-Density Parity-Check (NBLDPC) codes over the Binary Erasure Channel (BEC) decoded via the suboptimal Belief Propagation (BP) decoder as well as the optimal Maximum-A-Posteriori (MAP) decoder. Previously, NBLDPC codes defined with respect to a finite field have been studied in the literature. Unfortunately, for these codes the asymptotic analysis of the BP decoder in terms of density evolution is cumbersome since the involved densities "live" in a high dimensional space. To alleviate this problem, we introduce ensembles defined with respect to the general linear group. For these ensembles the density evolution equations can be written in a compact form. We compute thresholds for different alphabet sizes for various NBLDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. We also conjecture the stability condition for NBLDPC ensembles defined with respect to finite fields over any binary memoryless symmetric channel. We then consider the performance of NBLDPC codes under MAP decoding when transmission takes place over the BEC. Towards this goal, we generalize the concepts of the peeling decoder and stopping sets to NBLDPC codes. Using these concepts, we give a combinatorial characterization of decoding failures for NBLDPC codes decoded via the BP decoder. We use the decoding failure criterion and the density evolution analysis to compute the asymptotic residual degree distribution for NBLDPC codes. The rate of this residual ensemble gives the conditional entropy of the NBLDPC code. To compute the rate of the residual ensemble we generalize the criterion of [1] to the non-binary setting, which, when satisfied, guarantees that almost every code in the ensemble has a rate equal to the design rate. We observe that the Maxwell construction of [1], relating the performance of MAP and BP decoding via the Extended BP GEXIT (EBP GEXIT [2]) function, holds in the setting of NBLDPC codes. The weight and stopping set distribution of a code are related to its performance under the MAP and the BP decoder respectively. We first concentrate on the weight distribution of regular NBLDPC ensembles. We derive the average weight distribution of regular NBLDPC ensembles. Using this, we derive the average of equivalent binary weight distribution of regular NBLDPC ensembles. We show that as the alphabet size becomes larger the equivalent binary weight distribution converges to the weight distribution of Gallager's random parity check ensemble. The average weight distribution of binary LDPC ensembles has been extensively studied in the literature. Much less is known about the probability distribution of this quantity. In particular, the question of the concentration of the weight distribution around the ensemble average has not been addressed. We compute the variance of the weight distribution of binary regular LDPC ensembles. Using this and the second moment method we obtain bounds on the probability that a randomly chosen code has its weight distribution close to the ensemble average. We show that a large fraction of the total number of codes have their weight distribution close to the average. We apply the same technique for the stopping set distribution of binary regular LDPC ensembles. Again we show that a large fraction of total number of codes have their stopping set distribution close to the ensemble average. In the last part of this thesis we address the question of the existence of the EBP GEXIT function. The EBP GEXIT function plays a fundamental role in the asymptotic analysis of sparse graph codes. For transmission over the BEC using binary LDPC codes, the analytic properties of the EBP GEXIT function are relatively simple and well understood. The case of general BMS channel is much harder and even the existence of the curve is not known in general. We introduce some tools from non-linear analysis which can be useful to prove the existence of EXIT like curves in some cases. The main tool is the Krasnoselskii-Rabinowitz (KR) bifurcation theorem.

•Jan 1, 2008•12 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

The capacity of low-density parity-check codes under message-passing decoding

Tom Richardson, Rudiger L. Urbanke

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.

IEEE Transactions on Information Theory•Jan 1, 2001•3,067 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
We want to extend the approximation of the error probability via a scaling approach from the BEC to general binary-input memoryless output-symmetric (BMS) channels. In particular, we consider such scaling laws for regular LDPC ensembles and message-passing (MP) decoders with a finite number of messages. We first show how to re-derive the scaling law for transmission over the BEC using an ";EXIT-like"; curve instead of the density evolution curve of the peeling decoder. The advantage of the new derivation is that the new expression of the scaling parameter a only contains quantities that can be meaningfully interpreted also for general message-passing algorithms. In particular, this expression only depends on the curvature of the EXIT-like curve as well as the variance of the messages, both taken at the critical channel parameter. We discuss how to compute these quantities for general MP algorithms and we evaluate the expressions for the specific cases of the Gallager algorithm A as well as the Decoder with Erasures and compare the resulting predictions on the error probability with simulation results.
We consider LDPC codes, transmission over the binary symmetric channel (BSC), and decoding using Gallager's algorithm A. For those ensembles whose threshold is determined by the behavior of the algorithm at the beginning of the decoding process we derive a scaling law. This scaling law has the same form as the scaling law which was established for the the case of transmission over the binary erasure channel (BEC). We show how the scaling parameters can be computed and point out some interesting open challenges.
Scaling laws are a powerful way to analyze the performance of moderately sized iteratively decoded sparse graph codes. Our aim is to provide an easily usable finite-length optimization tool that is applicable to the wide variety of channels, blocklengths, error probability requirements, and decoders that one encounters for practical systems. The tool is aimed at non-experts in the field, who need to quickly find code designs that are comparable with the best known codes available today but do not have the luxury of spending months in doing so. In previous work we have shown how to compute scaling parameters for transmission over the binary erasure channel, as well as general channels and general quantized message-passing decoders when applied to regular ensembles. In this paper we show how to compute the message variance for a fixed number of iterations for irregular low-density parity-check ensembles. From these calculations the basic scaling parameter alpha can be deduced by determining the leading term of the limiting expression when the number of iterations tends to infinity and the channel parameter approaches the density evolution threshold.
In the first part of this thesis we are interested in the asymptotic performance analysis of Non-Binary Low-Density Parity-Check (NBLDPC) codes over the Binary Erasure Channel (BEC) decoded via the suboptimal Belief Propagation (BP) decoder as well as the optimal Maximum-A-Posteriori (MAP) decoder. Previously, NBLDPC codes defined with respect to a finite field have been studied in the literature. Unfortunately, for these codes the asymptotic analysis of the BP decoder in terms of density evolution is cumbersome since the involved densities "live" in a high dimensional space. To alleviate this problem, we introduce ensembles defined with respect to the general linear group. For these ensembles the density evolution equations can be written in a compact form. We compute thresholds for different alphabet sizes for various NBLDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. We also conjecture the stability condition for NBLDPC ensembles defined with respect to finite fields over any binary memoryless symmetric channel. We then consider the performance of NBLDPC codes under MAP decoding when transmission takes place over the BEC. Towards this goal, we generalize the concepts of the peeling decoder and stopping sets to NBLDPC codes. Using these concepts, we give a combinatorial characterization of decoding failures for NBLDPC codes decoded via the BP decoder. We use the decoding failure criterion and the density evolution analysis to compute the asymptotic residual degree distribution for NBLDPC codes. The rate of this residual ensemble gives the conditional entropy of the NBLDPC code. To compute the rate of the residual ensemble we generalize the criterion of [1] to the non-binary setting, which, when satisfied, guarantees that almost every code in the ensemble has a rate equal to the design rate. We observe that the Maxwell construction of [1], relating the performance of MAP and BP decoding via the Extended BP GEXIT (EBP GEXIT [2]) function, holds in the setting of NBLDPC codes. The weight and stopping set distribution of a code are related to its performance under the MAP and the BP decoder respectively. We first concentrate on the weight distribution of regular NBLDPC ensembles. We derive the average weight distribution of regular NBLDPC ensembles. Using this, we derive the average of equivalent binary weight distribution of regular NBLDPC ensembles. We show that as the alphabet size becomes larger the equivalent binary weight distribution converges to the weight distribution of Gallager's random parity check ensemble. The average weight distribution of binary LDPC ensembles has been extensively studied in the literature. Much less is known about the probability distribution of this quantity. In particular, the question of the concentration of the weight distribution around the ensemble average has not been addressed. We compute the variance of the weight distribution of binary regular LDPC ensembles. Using this and the second moment method we obtain bounds on the probability that a randomly chosen code has its weight distribution close to the ensemble average. We show that a large fraction of the total number of codes have their weight distribution close to the average. We apply the same technique for the stopping set distribution of binary regular LDPC ensembles. Again we show that a large fraction of total number of codes have their stopping set distribution close to the ensemble average. In the last part of this thesis we address the question of the existence of the EBP GEXIT function. The EBP GEXIT function plays a fundamental role in the asymptotic analysis of sparse graph codes. For transmission over the BEC using binary LDPC codes, the analytic properties of the EBP GEXIT function are relatively simple and well understood. The case of general BMS channel is much harder and even the existence of the curve is not known in general. We introduce some tools from non-linear analysis which can be useful to prove the existence of EXIT like curves in some cases. The main tool is the Krasnoselskii-Rabinowitz (KR) bifurcation theorem.
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.
We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.
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.