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:0709.0599 · IEEE Transactions on Information Theory

On Universal Properties of Capacity-Approaching LDPC Code Ensembles

Igal Sason

Published Jun 16, 2009• 41 citations
arXivHTMLPDF

Abstract

This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity, and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any suboptimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered.

DOI
10.1109/tit.2009.2021305

Related papers

On Universal Properties of the Degree Distributions and Cycles of Capacity-Approaching LDPC Ensembles

Igal Sason

This paper provides some universal information-theoretic bounds related to the degree distributions and the average cardinality of the fundamental system of cycles of low-density parity-check (LDPC) ensembles. The transmission of these ensembles is assumed to take place over an arbitrary memoryless binary-input output-symmetric (MBIOS) channel, and the bounds are expressed in terms of the gap between the design rates of these ensembles and the channel capacity. Some of these bounds hold under maximum-likelihood decoding (and hence, they also hold under any sub-optimal decoding algorithm) whereas the others hold particularly under the sum-product iterative decoding algorithm. The tightness of some of these bounds is exemplified numerically for capacity-approaching LDPC ensembles under iterative decoding; the bounds are reasonably tight for general MBIOS channels, and are tightened for the binary erasure channel where the tightness in the latter case is also demonstrated analytically.

•Sep 5, 2007•0 citations

On Universal LDPC Code Ensembles Over Memoryless Symmetric Channels

Igal Sason, Boaz Shuval

A design of robust error-correcting codes that achieve reliable communication over various channels is of great theoretical and practical interest. Such codes are termed universal. This paper considers the universality of low-density parity-check (LDPC) code ensembles over families of memoryless binary-input output-symmetric (MBIOS) channels. Universality is considered both under belief-propagation (BP) and maximum-likelihood (ML) decoding. For the BP decoding case, we derive a density-evolution-based analytical method for designing LDPC code ensembles that are universal over various families of MBIOS channels. We also derive a necessary condition for universality of LDPC code ensembles under BP decoding; this condition is used to provide bounds on the universally achievable fraction of capacity. These results enable us to provide conditions for reliable/unreliable communications under BP decoding that are based on the Bhattacharyya parameter of the channel. For the ML decoding case, we prove that properly selected regular LDPC code ensembles are universally capacity-achieving for the set of equi-capacity MBIOS channels and extend this result to punctured regular LDPC code ensembles.

IEEE Transactions on Information Theory•Aug 1, 2011•20 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

On the fundamental system of cycles in the bipartite graphs of LDPC code ensembles

Igal Sason

This work introduces an information-theoretic lower bound on the number of fundamental cycles for bipartite graphs of low-density parity-check (LDPC) code ensembles. This information-theoretic bound is expressed in terms of the achievable gap to capacity when the transmission of the code ensemble takes place over a memoryless binary-input output-symmetric (MBIOS) channel. The bound shows quantitatively the necessity of cycles in bipartite graphs which represent good LDPC code ensembles. More explicitly, it shows that the number of fundamental cycles should grow at least like log 1/epsiv where epsiv designates the gap in rate to capacity, hence, it is unbounded as the gap to capacity vanishes. For the derivation of this bound, a new information-theoretic lower bound on the average right degree, which also behaves like log 1/epsiv, is derived. The interested reader is referred to the full paper version.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•1 citation

ON UNIVERSAL LDPC CODES OVER MEMORYLESS SYMMETRIC CHANNELS

Igal Sason, Boaz Shuval

A design of robust error-correcting codes that achieve reli able communication over various channels is of great theoretical and practical interest. Such codes are termed universal. This paper considers the universality of lowdensity parity-check (LDPC) code ensembles over families of memoryless binary-input output-symmetric (MBIOS) channels. Universality is considered both under belief-pr opagation (BP) and maximum-likelihood (ML) decoding. For the BP decoding case, we derive a density-evolution-based analytical method for designing LDPC code ensembles that are universal over various families of MBIOS channels. We also derive a necessary condition for universality of LDPC code ensembles under BP decoding; this condition is used to provide bounds on the universally achievable fraction of capacity. These results enable us to provide conditions for reliable / unreliable communications under BP decoding that are based on the Bhattacharyya parameter of the channel. For the ML decoding case, we prove that properly selected regular LDPC code ensembles are universally capacity-achieving for the set of equicapacity MBIOS channels and extend this result to punctured regular LDPC code ensembles. Index Terms Belief propagation (BP), Bhattacharyya parameter (B-parameter), density evolution (DE), linear programming (LP) bounds, low-density parity-check (LDPC) codes, maximum-likelihood (ML), memoryless binary-input outputsymmetric (MBIOS) channels, stability.

•Jan 1, 2011•1 citation

On universal LDPC code ensembles

Igal Sason, Boaz Shuval

A universal design of low-density parity-check (LDPC) code ensembles which enables to operate reliably over various channels is of great theoretical and practical interest. This paper considers the universality of LDPC code ensembles over multitude memoryless binary-input output-symmetric (MBIOS) channels, addressing their universality under belief-propagation (BP) decoding. Based on the density evolution approach, analytical results related to the universality of LDPC code ensembles under BP decoding are derived; these results are expressed in closed form, and are easy to calculate. The full paper version related to this work provides further results, full proofs, additional discussions on the theorems, and it also considers the universality issue under ML decoding.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•4 citations
This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity, and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any suboptimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered.
This paper provides some universal information-theoretic bounds related to the degree distributions and the average cardinality of the fundamental system of cycles of low-density parity-check (LDPC) ensembles. The transmission of these ensembles is assumed to take place over an arbitrary memoryless binary-input output-symmetric (MBIOS) channel, and the bounds are expressed in terms of the gap between the design rates of these ensembles and the channel capacity. Some of these bounds hold under maximum-likelihood decoding (and hence, they also hold under any sub-optimal decoding algorithm) whereas the others hold particularly under the sum-product iterative decoding algorithm. The tightness of some of these bounds is exemplified numerically for capacity-approaching LDPC ensembles under iterative decoding; the bounds are reasonably tight for general MBIOS channels, and are tightened for the binary erasure channel where the tightness in the latter case is also demonstrated analytically.
A design of robust error-correcting codes that achieve reliable communication over various channels is of great theoretical and practical interest. Such codes are termed universal. This paper considers the universality of low-density parity-check (LDPC) code ensembles over families of memoryless binary-input output-symmetric (MBIOS) channels. Universality is considered both under belief-propagation (BP) and maximum-likelihood (ML) decoding. For the BP decoding case, we derive a density-evolution-based analytical method for designing LDPC code ensembles that are universal over various families of MBIOS channels. We also derive a necessary condition for universality of LDPC code ensembles under BP decoding; this condition is used to provide bounds on the universally achievable fraction of capacity. These results enable us to provide conditions for reliable/unreliable communications under BP decoding that are based on the Bhattacharyya parameter of the channel. For the ML decoding case, we prove that properly selected regular LDPC code ensembles are universally capacity-achieving for the set of equi-capacity MBIOS channels and extend this result to punctured regular LDPC code ensembles.
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.
This work introduces an information-theoretic lower bound on the number of fundamental cycles for bipartite graphs of low-density parity-check (LDPC) code ensembles. This information-theoretic bound is expressed in terms of the achievable gap to capacity when the transmission of the code ensemble takes place over a memoryless binary-input output-symmetric (MBIOS) channel. The bound shows quantitatively the necessity of cycles in bipartite graphs which represent good LDPC code ensembles. More explicitly, it shows that the number of fundamental cycles should grow at least like log 1/epsiv where epsiv designates the gap in rate to capacity, hence, it is unbounded as the gap to capacity vanishes. For the derivation of this bound, a new information-theoretic lower bound on the average right degree, which also behaves like log 1/epsiv, is derived. The interested reader is referred to the full paper version.
A design of robust error-correcting codes that achieve reli able communication over various channels is of great theoretical and practical interest. Such codes are termed universal. This paper considers the universality of lowdensity parity-check (LDPC) code ensembles over families of memoryless binary-input output-symmetric (MBIOS) channels. Universality is considered both under belief-pr opagation (BP) and maximum-likelihood (ML) decoding. For the BP decoding case, we derive a density-evolution-based analytical method for designing LDPC code ensembles that are universal over various families of MBIOS channels. We also derive a necessary condition for universality of LDPC code ensembles under BP decoding; this condition is used to provide bounds on the universally achievable fraction of capacity. These results enable us to provide conditions for reliable / unreliable communications under BP decoding that are based on the Bhattacharyya parameter of the channel. For the ML decoding case, we prove that properly selected regular LDPC code ensembles are universally capacity-achieving for the set of equicapacity MBIOS channels and extend this result to punctured regular LDPC code ensembles. Index Terms Belief propagation (BP), Bhattacharyya parameter (B-parameter), density evolution (DE), linear programming (LP) bounds, low-density parity-check (LDPC) codes, maximum-likelihood (ML), memoryless binary-input outputsymmetric (MBIOS) channels, stability.
A universal design of low-density parity-check (LDPC) code ensembles which enables to operate reliably over various channels is of great theoretical and practical interest. This paper considers the universality of LDPC code ensembles over multitude memoryless binary-input output-symmetric (MBIOS) channels, addressing their universality under belief-propagation (BP) decoding. Based on the density evolution approach, analytical results related to the universality of LDPC code ensembles under BP decoding are derived; these results are expressed in closed form, and are easy to calculate. The full paper version related to this work provides further results, full proofs, additional discussions on the theorems, and it also considers the universality issue under ML decoding.