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)

Scaling behavior of convolutional LDPC ensembles over the BEC

Pablo M. Olmos, Rudiger L. Urbanke

Published Jul 1, 2011• 30 citations
Publisher

Abstract

We study the scaling behavior of coupled sparse graph codes over the binary erasure channel. In particular, let 2L+1 be the length of the coupled chain, let M be the number of variables in each of the 2L+1 local copies, let ℓ be the number of iterations, let Pbdenote the bit error probability, and let ∈ denote the channel parameter. We are interested in how these quantities scale when we let the blocklength (2L + 1)M tend to infinity. Based on empirical evidence we show that the threshold saturation phenomenon is rather stable with respect to the scaling of the various parameters and we formulate some general rules of thumb which can serve as a guide for the design of coding systems based on coupled graphs.

DOI
10.1109/isit.2011.6033863

Related papers

Scaling Behavior of Convolutional LDPC Ensembles over the BEC

Pablo M. Olmos, Rudiger L. Urbanke

We study the scaling behavior of coupled sparse graph codes over the binary erasure channel. In particular, let 2L+1 be the length of the coupled chain, let M be the number of variables in each of the 2L + 1 local copies, let l be the number of iterations, let Pb denote the bit error probability, and let ε denote the channel parameter. We are interested in how these quantities scale when we let the blocklength (2L + 1)M tend to infinity. Based on empirical evidence we show that the threshold saturation phenomenon is rather stable with respect to the scaling of the various parameters and we formulate some general rules of thumb which can serve as a guide for the design of coding systems based on coupled graphs.

arXiv:1107.2229•Jul 12, 2011•4 citations

Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform So Well over the BEC

Shrinivas Kudekar, Thomas J. Richardson, Rudiger L. Urbanke

Convolutional low-density parity-check (LDPC) ensembles, introduced by Felström and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing functions of the average degree. Several variations on the basic theme have been proposed to date, all of which share the good performance characteristics of convolutional LDPC ensembles. We describe the fundamental mechanism that explains why “convolutional-like” or “spatially coupled” codes perform so well. In essence, the spatial coupling of individual codes increases the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum a posteriori (MAP) threshold of the underlying ensemble. For this reason, we call this phenomenon “threshold saturation.” This gives an entirely new way of approaching capacity. One significant advantage of this construction is that one can create capacity-approaching ensembles with an error correcting radius that is increasing in the blocklength. Although we prove the “threshold saturation” only for a specific ensemble and for the binary erasure channel (BEC), empirically the phenomenon occurs for a wide class of ensembles and channels. More generally, we conjecture that for a large range of graphical systems a similar saturation of the “dynamical” threshold occurs once individual components are coupled sufficiently strongly. This might give rise to improved algorithms and new techniques for analysis.

arXiv:1001.1826•IEEE Transactions on Information Theory•Jan 21, 2011•703 citations

Bounds on the Number of Iterations for Turbo-Like Ensembles Over the Binary Erasure Channel

Igal Sason, Gil Wiechman

This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check codes and variations of repeat-accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-2 variable nodes, the target bit erasure probability and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).

IEEE Transactions on Information Theory•May 19, 2009•16 citations

A closed-form scaling law for convolutional LDPC codes over the BEC

Pablo M. Olmos, Rudiger L. Urbanke

We propose a scaling law for the error probability of convolutional LDPC ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well with data derived from simulations over a wide range of parameters.

IEEE Information Theory Workshop (ITW)•Sep 1, 2013•9 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

Bounds on the Number of Iterations for Turbo-Like Ensembles over the Binary Erasure Channe

Igal Sason, Gil Wiechman

This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check codes and variations of repeat-accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-2 variable nodes, the target bit erasure probability and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).

arXiv:0711.1056•Nov 7, 2007•1 citation
We study the scaling behavior of coupled sparse graph codes over the binary erasure channel. In particular, let 2L+1 be the length of the coupled chain, let M be the number of variables in each of the 2L+1 local copies, let ℓ be the number of iterations, let Pbdenote the bit error probability, and let ∈ denote the channel parameter. We are interested in how these quantities scale when we let the blocklength (2L + 1)M tend to infinity. Based on empirical evidence we show that the threshold saturation phenomenon is rather stable with respect to the scaling of the various parameters and we formulate some general rules of thumb which can serve as a guide for the design of coding systems based on coupled graphs.
We study the scaling behavior of coupled sparse graph codes over the binary erasure channel. In particular, let 2L+1 be the length of the coupled chain, let M be the number of variables in each of the 2L + 1 local copies, let l be the number of iterations, let Pb denote the bit error probability, and let ε denote the channel parameter. We are interested in how these quantities scale when we let the blocklength (2L + 1)M tend to infinity. Based on empirical evidence we show that the threshold saturation phenomenon is rather stable with respect to the scaling of the various parameters and we formulate some general rules of thumb which can serve as a guide for the design of coding systems based on coupled graphs.
Convolutional low-density parity-check (LDPC) ensembles, introduced by Felström and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing functions of the average degree. Several variations on the basic theme have been proposed to date, all of which share the good performance characteristics of convolutional LDPC ensembles. We describe the fundamental mechanism that explains why “convolutional-like” or “spatially coupled” codes perform so well. In essence, the spatial coupling of individual codes increases the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum a posteriori (MAP) threshold of the underlying ensemble. For this reason, we call this phenomenon “threshold saturation.” This gives an entirely new way of approaching capacity. One significant advantage of this construction is that one can create capacity-approaching ensembles with an error correcting radius that is increasing in the blocklength. Although we prove the “threshold saturation” only for a specific ensemble and for the binary erasure channel (BEC), empirically the phenomenon occurs for a wide class of ensembles and channels. More generally, we conjecture that for a large range of graphical systems a similar saturation of the “dynamical” threshold occurs once individual components are coupled sufficiently strongly. This might give rise to improved algorithms and new techniques for analysis.
This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check codes and variations of repeat-accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-2 variable nodes, the target bit erasure probability and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).
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.
This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check codes and variations of repeat-accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-2 variable nodes, the target bit erasure probability and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).