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

Allerton Conference on Communication, Control, and Computing

Analysis of bipartite graph codes on the binary erasure channel

Arya Mazumdar

Published Jan 1, 2007• 1 citation
OpenAlex

Abstract

We derive density evolution equations for codes on bipartite graphs (BG codes) for the binary erasure channel (BEC).We study the cases of local codes being introduced on only one side of the graph (Generalized LDPC codes) as well as on both sides.Each local code is assumed to correct up to a number of erasures one less than its distance.We define and enumerate stopping sets for BG codes, which serves an important tool for analysis of decoding thresholds on the BEC.

Related papers

Non binary LDPC codes over the binary erasure channel: Density evolution analysis

Valentin Savin

In this paper we present a thorough analysis of non binary LDPC codes over the binary erasure channel. First, the decoding of non binary LDPC codes is investigated. The proposed algorithm performs ldquoon-the flyrdquo decoding, i.e. it starts decoding as soon as the first symbols are received, which generalizes the erasure decoding of binary LDPC codes. Next, we evaluate the asymptotical performance of ensembles of non binary LDPC codes, by using the density evolution method. Density evolution equations are derived by taking into consideration both the irregularity of the bipartite graph and the probability distribution of the graph edge labels. Finally, infinite-length performance of some ensembles of non binary LDPC codes for different edge label distributions are shown.

arXiv:0810.4404•International Symposium on Applied Sciences in Biomedical and Communication Technologies•Oct 1, 2008•19 citations

Binary linear-time erasure decoding for non-binary LDPC codes

Valentin Savin

In this paper, we first introduce the extended binary representation of non-binary codes, which corresponds to a covering graph of the bipartite graph associated with the non-binary code. Then we show that non-binary codewords correspond to binary codewords of the extended representation that further satisfy some simplex-constraint: that is, bits lying over the same symbol-node of the non-binary graph must form a codeword of a simplex code. Applied to the binary erasure channel (BEC), this description leads to a binary erasure decoding algorithm of non-binary LDPC codes, whose complexity depends linearly on the cardinality of the alphabet. We also give insights into the structure of stopping sets for non-binary LDPC codes, and discuss several aspects related to upper-layer FEC applications.

arXiv:0910.1922•IEEE Information Theory Workshop (ITW)•Jan 1, 2009•14 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•23 citations

Coset graphs for low-density parity check codes: performance on the binary erasure channel

Josef Lauri, Cen Jung Tjhai

The authors show that a popular way of constructing quasi-cyclic low-density parity check (LDPC) codes is a special case of a construction which is common in graph theory and group theory. It is shown that a generalisation of this construction as coset graphs produces (dv, dc)-regular LDPC codes that have an advantage in terms of the minimum stopping set size compared to quasi-cyclic LDPC codes. A (dv, dc)-regular quasi-cyclic LDPC code cannot have minimum stopping set size larger than (dv+1)!. However, by using coset graphs, a (3, 5)-regular LDPC code with minimum stopping set size of 28 and a (3, 4)-regular LDPC code with minimum stopping set size larger than 32 have been obtained. In addition, the idea of coset graphs also provides a compact algebraic way of describing bipartite graph and the associated parity-check matrix of an LDPC code. Simulation results of iterative decoding of the coset graphs LDPC codes over the binary erasure channel show that some of the codes converge well and based on the truncated stopping set distributions of the codes, which are exhaustively and efficiently enumerated, the error-floor of the codes at low probability of erasure is estimated.

IET Communications•Mar 25, 2011•0 citations

Exact erasure channel density evolution for protograph-based generalized LDPC codes

Michael Lentmaier, Marcos B. S. Tavares, Gerhard Paul Fettweis

We derive explicit density evolution equations for protograph-based generalized LDPC codes on the binary erasure channel. They are obtained from an analysis of multi-dimensional input/output transfer functions of the component decoders. Belief propagation decoding with optimal component APP decoders is considered. Based on the resulting transfer functions, a threshold analysis is performed for some protograph examples.

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

Generalized LDPC codes and generalized stopping sets

N. Miladinovic, M.P.C. Fossorier

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.

IEEE Transactions on Communications•Feb 1, 2008•49 citations
We derive density evolution equations for codes on bipartite graphs (BG codes) for the binary erasure channel (BEC).We study the cases of local codes being introduced on only one side of the graph (Generalized LDPC codes) as well as on both sides.Each local code is assumed to correct up to a number of erasures one less than its distance.We define and enumerate stopping sets for BG codes, which serves an important tool for analysis of decoding thresholds on the BEC.
In this paper we present a thorough analysis of non binary LDPC codes over the binary erasure channel. First, the decoding of non binary LDPC codes is investigated. The proposed algorithm performs ldquoon-the flyrdquo decoding, i.e. it starts decoding as soon as the first symbols are received, which generalizes the erasure decoding of binary LDPC codes. Next, we evaluate the asymptotical performance of ensembles of non binary LDPC codes, by using the density evolution method. Density evolution equations are derived by taking into consideration both the irregularity of the bipartite graph and the probability distribution of the graph edge labels. Finally, infinite-length performance of some ensembles of non binary LDPC codes for different edge label distributions are shown.
In this paper, we first introduce the extended binary representation of non-binary codes, which corresponds to a covering graph of the bipartite graph associated with the non-binary code. Then we show that non-binary codewords correspond to binary codewords of the extended representation that further satisfy some simplex-constraint: that is, bits lying over the same symbol-node of the non-binary graph must form a codeword of a simplex code. Applied to the binary erasure channel (BEC), this description leads to a binary erasure decoding algorithm of non-binary LDPC codes, whose complexity depends linearly on the cardinality of the alphabet. We also give insights into the structure of stopping sets for non-binary LDPC codes, and discuss several aspects related to upper-layer FEC applications.
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 authors show that a popular way of constructing quasi-cyclic low-density parity check (LDPC) codes is a special case of a construction which is common in graph theory and group theory. It is shown that a generalisation of this construction as coset graphs produces (dv, dc)-regular LDPC codes that have an advantage in terms of the minimum stopping set size compared to quasi-cyclic LDPC codes. A (dv, dc)-regular quasi-cyclic LDPC code cannot have minimum stopping set size larger than (dv+1)!. However, by using coset graphs, a (3, 5)-regular LDPC code with minimum stopping set size of 28 and a (3, 4)-regular LDPC code with minimum stopping set size larger than 32 have been obtained. In addition, the idea of coset graphs also provides a compact algebraic way of describing bipartite graph and the associated parity-check matrix of an LDPC code. Simulation results of iterative decoding of the coset graphs LDPC codes over the binary erasure channel show that some of the codes converge well and based on the truncated stopping set distributions of the codes, which are exhaustively and efficiently enumerated, the error-floor of the codes at low probability of erasure is estimated.
A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.