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)

Information-theoretic lower bounds on the bit error probability of codes on graphs

Igal Sason, Rudiger L. Urbanke

Published Jan 1, 2003• 4 citations
Publisher

Abstract

We present lower bounds on the bit error probability of binary linear block codes, and on the gap between the channel capacity and the rate of these codes for which reliable communica- tion is achievable. The results are valid for memo- ryless binary-input output-symmetric (MBIOS) chan- nels. The lower bounds provide a quantitative mea- sure for the number of cycles of bipartite graphs which represent good error-correcting codes. The tightness of the lower bounds is especially pronounced for the binary erasure channel (BEC); to this end, we analyze a sequence of ensembles of low-density parity-check (LDPC) codes which closely approach these bounds. I. Introduction If a linear block code can be represented by a cycle-free fac- tor graph which only includes variable nodes and parity-check nodes, then maximum-likelihood soft decision decoding can be performed with low complexity (1). Theorem 5 in (1) indicates that these graphs represent codes with very poor minimum distance. The bounds in (1) only refer to the minimum dis- tance of cycle-free codes, and in this work we derive lower bounds on the bit error probability and the gap to capacity for codes on graphs which are represented by bipartite graphs (with or without cycles). We derive in this work information- theoretic lower bounds on the bit error probability of a binary linear code used over MBIOS channels. The bounds are ex- pressed in terms of the density of an arbitrary parity-check matrix which represents the binary linear code (i.e., the num- ber of ones in the matrix normalized per information bit), and they are valid for codes whose bipartite graphs are with or without cycles. We introduce a quantitative measure for the cycles in a bipartite graph which represents a binary lin- ear code (where the graph only includes variable nodes and parity-check nodes). The bounds provide an interpretation for the tradeofi which exists between the bit error proba- bility and gap to capacity of an arbitrary LDPC code (i.e., its performance limitations), and the density of an arbitrary parity-check matrix which represents the code (where the lat- ter afiects the decoding complexity per information bit and per iteration, under a message-passing iterative decoding al- gorithm). We present in this work quantitative results which indicate that in order to approach the channel capacity with vanishing bit error probability, LDPC codes should not have too sparse parity-check matrices, as otherwise their inherent gap to capacity becomes large. In fact, we show that the density of any parity-check matrix and the fundamental num- ber of cycles of the graph which represents the code should increase at least like log 1 where designates the gap to ca- pacity under iterative message-passing decoding (see (2), (3)). The tightness of the lower bounds which are derived in this work (and whose validity is for any sequence of codes with 1 1.5 2 2.5 3 3.5 4 4.5

DOI
10.1109/isit.2003.1228283

Related papers

Parity-check density versus performance of binary linear block codes over memoryless symmetric channels

Igal Sason, Rudiger L. Urbanke

We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.

IEEE Transactions on Information Theory•Jun 23, 2003•121 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 Properties of Capacity-Approaching LDPC Code Ensembles

Igal Sason

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.

arXiv:0709.0599•IEEE Transactions on Information Theory•Jun 16, 2009•41 citations

Bounds on the maximum-likelihood decoding error probability of low-density parity-check codes

G. Miller, David Burshtein

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

IEEE Transactions on Information Theory•Jan 1, 2001•157 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

Bounds on the maximum likelihood decoding error probability of low density parity check codes

G. Miller, D. Burshtein

We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•7 citations
We present lower bounds on the bit error probability of binary linear block codes, and on the gap between the channel capacity and the rate of these codes for which reliable communica- tion is achievable. The results are valid for memo- ryless binary-input output-symmetric (MBIOS) chan- nels. The lower bounds provide a quantitative mea- sure for the number of cycles of bipartite graphs which represent good error-correcting codes. The tightness of the lower bounds is especially pronounced for the binary erasure channel (BEC); to this end, we analyze a sequence of ensembles of low-density parity-check (LDPC) codes which closely approach these bounds. I. Introduction If a linear block code can be represented by a cycle-free fac- tor graph which only includes variable nodes and parity-check nodes, then maximum-likelihood soft decision decoding can be performed with low complexity (1). Theorem 5 in (1) indicates that these graphs represent codes with very poor minimum distance. The bounds in (1) only refer to the minimum dis- tance of cycle-free codes, and in this work we derive lower bounds on the bit error probability and the gap to capacity for codes on graphs which are represented by bipartite graphs (with or without cycles). We derive in this work information- theoretic lower bounds on the bit error probability of a binary linear code used over MBIOS channels. The bounds are ex- pressed in terms of the density of an arbitrary parity-check matrix which represents the binary linear code (i.e., the num- ber of ones in the matrix normalized per information bit), and they are valid for codes whose bipartite graphs are with or without cycles. We introduce a quantitative measure for the cycles in a bipartite graph which represents a binary lin- ear code (where the graph only includes variable nodes and parity-check nodes). The bounds provide an interpretation for the tradeofi which exists between the bit error proba- bility and gap to capacity of an arbitrary LDPC code (i.e., its performance limitations), and the density of an arbitrary parity-check matrix which represents the code (where the lat- ter afiects the decoding complexity per information bit and per iteration, under a message-passing iterative decoding al- gorithm). We present in this work quantitative results which indicate that in order to approach the channel capacity with vanishing bit error probability, LDPC codes should not have too sparse parity-check matrices, as otherwise their inherent gap to capacity becomes large. In fact, we show that the density of any parity-check matrix and the fundamental num- ber of cycles of the graph which represents the code should increase at least like log 1 where designates the gap to ca- pacity under iterative message-passing decoding (see (2), (3)). The tightness of the lower bounds which are derived in this work (and whose validity is for any sequence of codes with 1 1.5 2 2.5 3 3.5 4 4.5
We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.
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.
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.
We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.
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).
We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.