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 Information Theory Workshop (ITW)

On upper bounds for the achievable rates of LDPC codes

Noam Presman, Simon N. Litsyn

Published Jan 1, 2009• 0 citations
Publisher

Abstract

Upper bounds on the mutual entropy of syndrome components of low-density parity-check (LDPC) codes are developed. Using these bounds, an upper bound is derived on the rates of LDPC codes for which reliable communication over a memoryless binary-input symmetric-output (MBIOS) channel is achievable. This bound improves on the earlier known bounds due to Gallager, Burshtein et al., and Weichmann-Sason.

DOI
10.1109/itw.2009.5351232

Related papers

Upper bounds on the rate of LDPC codes

David Burshtein, Michael Krivelevich, Simon N. Litsyn +1 more

We derive upper bounds on the rate of low-density parity-check (LDPC) codes for which reliable communication is achievable. We first generalize Gallager's (1963) bound to a general binary-input symmetric-output channel. We then proceed to derive tighter bounds. We also derive upper bounds on the rate as a function of the minimum distance of the code. We consider both individual codes and ensembles of codes.

IEEE Transactions on Information Theory•Sep 1, 2002•89 citations

On Achievable Rates and Complexity of LDPC Codes for Parallel Channels with Application to Puncturing

Igal Sason, Gil Wiechman

This paper considers the achievable rates and decoding complexity of low-density parity-check (LDPC) codes over statistically independent parallel channels. The paper starts with the derivation of bounds on the conditional entropy of the transmitted codeword given the received sequence at the output of the parallel channels; the component channels are considered to be memoryless, binary-input, and output-symmetric (MBIOS). These results serve for the derivation of an upper bound on the achievable rates of ensembles of LDPC codes under optimal maximum-likelihood (ML) decoding when their transmission takes place over parallel MBIOS channels. The paper relies on the latter bound for obtaining upper bounds on the achievable rates of ensembles of randomly and intentionally punctured LDPC codes over MBIOS channels. The paper also provides a lower bound on the decoding complexity (per iteration) of ensembles of LDPC codes under message-passing iterative decoding over parallel MBIOS channels; the bound is given in terms of the gap between the rate of these codes for which reliable communication is achievable and the channel capacity. The paper presents a diagram which shows interconnections between the theorems introduced in this paper and some other previously reported results. The setting which serves for the derivation of the bounds on the achievable rates and decoding complexity is general, and the bounds can be applied to other scenarios which can be treated as different forms of communication over parallel channels.

arXiv:cs/0508072•Aug 16, 2005•5 citations

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 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 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 Achievable Rates and Complexity of LDPC Codes for Parallel Channels: Information-Theoretic Bounds and Applications

Igal Sason, Gil Wiechman

The paper presents bounds on the achievable rates and the decoding complexity per iteration of low-density parity-check (LDPC) codes. It is assumed that the communication of these codes takes place over statistically independent parallel channels where these channels are memoryless, binary-input and output-symmetric. The bounds are applied to punctured LDPC codes. A diagram concludes our discussion by showing interconnections between the theorems in this paper and some previously reported results

arXiv:cs/0512076•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•1 citation
Upper bounds on the mutual entropy of syndrome components of low-density parity-check (LDPC) codes are developed. Using these bounds, an upper bound is derived on the rates of LDPC codes for which reliable communication over a memoryless binary-input symmetric-output (MBIOS) channel is achievable. This bound improves on the earlier known bounds due to Gallager, Burshtein et al., and Weichmann-Sason.
This paper considers the achievable rates and decoding complexity of low-density parity-check (LDPC) codes over statistically independent parallel channels. The paper starts with the derivation of bounds on the conditional entropy of the transmitted codeword given the received sequence at the output of the parallel channels; the component channels are considered to be memoryless, binary-input, and output-symmetric (MBIOS). These results serve for the derivation of an upper bound on the achievable rates of ensembles of LDPC codes under optimal maximum-likelihood (ML) decoding when their transmission takes place over parallel MBIOS channels. The paper relies on the latter bound for obtaining upper bounds on the achievable rates of ensembles of randomly and intentionally punctured LDPC codes over MBIOS channels. The paper also provides a lower bound on the decoding complexity (per iteration) of ensembles of LDPC codes under message-passing iterative decoding over parallel MBIOS channels; the bound is given in terms of the gap between the rate of these codes for which reliable communication is achievable and the channel capacity. The paper presents a diagram which shows interconnections between the theorems introduced in this paper and some other previously reported results. The setting which serves for the derivation of the bounds on the achievable rates and decoding complexity is general, and the bounds can be applied to other scenarios which can be treated as different forms of communication over parallel channels.
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.
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 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.
The paper presents bounds on the achievable rates and the decoding complexity per iteration of low-density parity-check (LDPC) codes. It is assumed that the communication of these codes takes place over statistically independent parallel channels where these channels are memoryless, binary-input and output-symmetric. The bounds are applied to punctured LDPC codes. A diagram concludes our discussion by showing interconnections between the theorems in this paper and some previously reported results