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)

New sequences of capacity achieving LDPC code ensembles over the binary erasure channel

Hamid Saeedi, Amir H. Banihashemi

Published Jul 1, 2008• 8 citations
Publisher

Abstract

In this paper, we introduce new sequences (lambdan, rhon) of capacity achieving low-density parity-check (LDPC) code ensembles over the binary erasure channel (BEC). These sequences include the existing sequences by Shokrollahi as a special case. For a fixed code rate R, in the set of proposed sequences, Shokrollahipsilas sequences are superior to the rest of the set in that for any given value of n, their threshold is closer to the capacity upper bound 1 - R. For any given delta, 00, such that for any n > n0, the sequence (lambdan, rhon) requires a smaller maximum variable node degree as well as a smaller number of constituent variable node degrees to achieve a threshold within delta-neighborhood of the capacity upper bound 1 - R. Moreover, we prove that the check-regular subset of the proposed sequences are asymptotically quasi-optimal, i.e., their decoding complexity per iteration increases only logarithmically with the relative increase of the threshold. A stronger result on asymptotic optimality of some of the proposed sequences is also established.

DOI
10.1109/isit.2008.4595096

Related papers

New Sequences of Capacity Achieving LDPC Code Ensembles Over the Binary Erasure Channel

Hamid Saeedi, Amir H. Banihashemi

In this paper, new sequences$(\lambda ^{n},\rho ^{n})$of capacity achieving low-density parity-check (LDPC) code ensembles over the binary erasure channel (BEC) is introduced. These sequences include the existing sequences by Shokrollahias a special case. For a fixed code rate$R$, in the set of proposed sequences, Shokrollahi's sequences are superior to the rest of the set in that for any given value of$n$, their threshold is closer to the capacity upper bound$1- R$. For any given$\delta $,$0 < \delta < 1-R$, however, there are infinitely many sequences in the set that are superior to Shokrollahi's sequences in that for each of them, there exists an integer number$n_{0}$, such that for any$n > n_{0}$, the sequence$(\lambda ^{n},\rho ^{n})$requires a smaller maximum variable node degree as well as a smaller number of constituent variable node degrees to achieve a threshold within$\delta $-neighborhood of the capacity upper bound$1-R$. Moreover, it is proven that the check-regular subset of the proposed sequences are asymptotically quasi-optimal, i.e., their decoding complexity increases only logarithmically with the relative increase of the threshold. A stronger result on asymptotic optimality of some of the proposed sequences is also established.

IEEE Transactions on Information Theory•Nov 30, 2010•20 citations

On LDPC codes over symmetric channels

Hamid Saeedi, Hossein Pishro-Nik

In the past decade, there has been tremendous amount of research on the analysis and design of the Low-Density Parity-Check (LDPC) codes with belief propagation decoding over different types of Binary-Input Output-Symmetric Memoryless (BIOSM) channels. However, with the exception of the Binary Erasure Channel (BEC), analytical results on LDPC codes over such channels are limited and most results are based on numerical methods and optimization. In particular, systematic design of provably capacity achieving sequences of LDPC code ensembles over general class of BIOSM channels has remained a fundamental open problem. Such sequences have been designed only for the binary erasure channel (BEC). In this paper, we first prove some novel analytical properties of the LDPC code ensembles over BIOSM channels. In particular, we prove a result that generalizes the previously known stability condition over symmetric channels. This suggests that a modified version of the flatness condition, a property which has been shown to be critical for capacity achieving sequences over the BEC, can be used to devise capacity achieving sequences for general class of BIOSM channels. Based on this assumption, we propose a method which could result in the systematic design of such sequences over BIOSM channels. Numerical evidence is promising and provides a consistent convergence behavior to capacity over the considered BIOSM channels as the average check node degree increases.

IEEE Information Theory Workshop (ITW)•Jun 1, 2009•0 citations

On Convergence Speed of Capacity-Achieving Sequences for Erasure Channel

Min Lü

Oswald and Shokrollahi carried out a systematic study of capacity-achieving sequences of low-density parity-check (LDPC) codes for the binary erasure channel. Two quantities mu and Delta were suggested to measure the convergence speed of these sequences. They gave an upper bound of mu for a certain type of capacity-achieving sequences. In this correspondence, a lower bound of mu for this type of sequences is provided. It follows that, under a certain condition, the exact value of mu can be determined, which answers an open question posed by Oswald and Shokrollahi in their paper. If the condition is not satisfied the upper bound may not be tight. A counterexample is given.

IEEE Transactions on Information Theory•Mar 27, 2008•2 citations

Bounds on Achievable Rates of LDPC Codes Used Over the Binary Erasure Channel

Ohad Barak, David Burshtein, Meir Feder

We derive upper bounds on the maximum achievable rate of low-density parity-check (LDPC) codes used over the binary erasure channel (BEC) under Gallager's decoding algorithm, given their right-degree distribution. We demonstrate the bounds on the ensemble of right-regular LDPC codes and compare them with an explicit left-degree distribution constructed from the given right degree.

IEEE Transactions on Information Theory•Sep 28, 2004•20 citations

Results on the Improved Decoding Algorithm for Low-Density Parity-Check Codes Over the Binary Erasure Channel

Badri N. Vellambi, Faramarz Fekri

In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates

IEEE Transactions on Information Theory•Apr 1, 2007•24 citations

LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +2 more

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

IEEE Transactions on Communications•Nov 6, 2018•5 citations
In this paper, we introduce new sequences (lambdan, rhon) of capacity achieving low-density parity-check (LDPC) code ensembles over the binary erasure channel (BEC). These sequences include the existing sequences by Shokrollahi as a special case. For a fixed code rate R, in the set of proposed sequences, Shokrollahipsilas sequences are superior to the rest of the set in that for any given value of n, their threshold is closer to the capacity upper bound 1 - R. For any given delta, 00, such that for any n > n0, the sequence (lambdan, rhon) requires a smaller maximum variable node degree as well as a smaller number of constituent variable node degrees to achieve a threshold within delta-neighborhood of the capacity upper bound 1 - R. Moreover, we prove that the check-regular subset of the proposed sequences are asymptotically quasi-optimal, i.e., their decoding complexity per iteration increases only logarithmically with the relative increase of the threshold. A stronger result on asymptotic optimality of some of the proposed sequences is also established.
In this paper, new sequences(λn,ρn)(\lambda ^{n},\rho ^{n})(λn,ρn)of capacity achieving low-density parity-check (LDPC) code ensembles over the binary erasure channel (BEC) is introduced. These sequences include the existing sequences by Shokrollahias a special case. For a fixed code rateRRR, in the set of proposed sequences, Shokrollahi's sequences are superior to the rest of the set in that for any given value ofnnn, their threshold is closer to the capacity upper bound1−R1- R1−R. For any given$\delta $,0<δ<1−R0 < \delta < 1-R0<δ<1−R, however, there are infinitely many sequences in the set that are superior to Shokrollahi's sequences in that for each of them, there exists an integer numbern0n_{0}n0​, such that for anyn>n0n > n_{0}n>n0​, the sequence(λn,ρn)(\lambda ^{n},\rho ^{n})(λn,ρn)requires a smaller maximum variable node degree as well as a smaller number of constituent variable node degrees to achieve a threshold within$\delta $-neighborhood of the capacity upper bound1−R1-R1−R. Moreover, it is proven that the check-regular subset of the proposed sequences are asymptotically quasi-optimal, i.e., their decoding complexity increases only logarithmically with the relative increase of the threshold. A stronger result on asymptotic optimality of some of the proposed sequences is also established.
In the past decade, there has been tremendous amount of research on the analysis and design of the Low-Density Parity-Check (LDPC) codes with belief propagation decoding over different types of Binary-Input Output-Symmetric Memoryless (BIOSM) channels. However, with the exception of the Binary Erasure Channel (BEC), analytical results on LDPC codes over such channels are limited and most results are based on numerical methods and optimization. In particular, systematic design of provably capacity achieving sequences of LDPC code ensembles over general class of BIOSM channels has remained a fundamental open problem. Such sequences have been designed only for the binary erasure channel (BEC). In this paper, we first prove some novel analytical properties of the LDPC code ensembles over BIOSM channels. In particular, we prove a result that generalizes the previously known stability condition over symmetric channels. This suggests that a modified version of the flatness condition, a property which has been shown to be critical for capacity achieving sequences over the BEC, can be used to devise capacity achieving sequences for general class of BIOSM channels. Based on this assumption, we propose a method which could result in the systematic design of such sequences over BIOSM channels. Numerical evidence is promising and provides a consistent convergence behavior to capacity over the considered BIOSM channels as the average check node degree increases.
Oswald and Shokrollahi carried out a systematic study of capacity-achieving sequences of low-density parity-check (LDPC) codes for the binary erasure channel. Two quantities mu and Delta were suggested to measure the convergence speed of these sequences. They gave an upper bound of mu for a certain type of capacity-achieving sequences. In this correspondence, a lower bound of mu for this type of sequences is provided. It follows that, under a certain condition, the exact value of mu can be determined, which answers an open question posed by Oswald and Shokrollahi in their paper. If the condition is not satisfied the upper bound may not be tight. A counterexample is given.
In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.