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)

Ensemble Weight Enumerators for Protograph LDPC Codes

D. Divsalar

Published Jul 1, 2006• 67 citations
Publisher

Abstract

Recently, LDPC codes with projected graph, or protograph structures have been proposed. In this paper, finite length ensemble weight enumerators for LDPC codes with protograph structures are obtained. Asymptotic results are derived as the block size goes to infinity. In particular, we are interested in obtaining ensemble average weight enumerators for protograph LDPC codes which have typical minimum distance that grows linearly with block size. As with irregular ensembles, linear minimum distance property is sensitive to the proportion of degree-2 variable nodes. In this paper, the derived results on ensemble weight enumerators show that linear minimum distance condition on degree distribution of unstructured irregular LDPC codes is a sufficient but not a necessary condition for protograph LDPC codes

DOI
10.1109/isit.2006.262129

Related papers

On the typical minimum distance of protograph-based generalized LDPC codes

Shadi Abu‐Surra, D. Divsalar, W.E. Ryan

Protograph-based generalized LDPC (GLDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. Recently, a technique for computing ensemble weight enumerators for GLDPC codes has been published. In the current paper, we investigate the existence of typical minimum distance for protograph-based GLDPC codes. That is, we first upper bound the ensemble weight enumerators for finite-length GLDPC codes based on protographs, and then we consider the sum of weight enumerators. The results allow us to determine whether or not the typical minimum distance in the ensemble grows linearly with codeword length. We provide conditions on the connections of degree-2 variable nodes to constraint nodes (short block codes) to have typical minimum distance. These conditions are related to the minimum distances of the constraint nodes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•2 citations

Ensemble Enumerators for Protograph-Based Generalized LDPC Codes

Shadi Abu‐Surra, W.E. Ryan, D. Divsalar

Protograph-based LDPC codes have the advantages of a simple design (or search) procedure and highly structured encoders and decoders. These advantages have also been exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. Recently, a technique for computing ensemble weight enumerators and stopping set enumerators for protograph-based LDPC codes has been published. In the current paper, we extend those results to protograph-based G-LDPC codes. That is, we first derive ensemble weight and stopping set enumerators for finite-length G-LDPC codes based on protographs, and then we consider the asymptotic case. In the weight enumerator case, the asymptotic results allow us to determine whether or not the typical minimum distance in the ensemble grows linearly with codeword length. In the stopping set enumerator case, the asymptotic results allows us to determine whether or not the typical smallest stopping set size grows linearly with codeword length.

Globecom•Nov 1, 2007•13 citations

Ensemble Weight Enumerators for Protograph-Based Generalized LDPC Codes

Shadi Abu‐Surra, W.E. Ryan, D. Divsalar

Protograph-based LDPC codes have the advantages of a simple design (or search) procedure and highly structured encoders and decoders. These advantages have also been exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. Recently, a technique for computing ensemble weight enumerators for protograph-based LDPC codes has been published. In the current paper, we extend those results to protograph-based G-LDPC codes. That is, we first derive ensemble weight enumerators for finite-length G-LDPC codes based on protographs, and then we consider the asymptotic case. The asymptotic results allow us to determine whether or not the typical minimum distance in the ensemble grows linearly with codeword length.

Information Theory and Applications Workshop (ITA)•Jan 1, 2007•10 citations

Protograph based LDPC codes with minimum distance linearly growing with block size

D. Divsalar, C. Jones, Samuel J. Dolinar +1 more

We propose several LDPC code constructions that simultaneously achieve good threshold and error floor performance. Minimum distance is shown to grow linearly with block size (similar to regular codes of variable degree at least 3) by considering ensemble average weight enumerators. Our constructions are based on projected graph, or protograph, structures that support high-speed decoder implementations. As with irregular ensembles, our constructions are sensitive to the proportion of degree-2 variable nodes. A code with too few such nodes tends to have an iterative decoding threshold that is far from the capacity threshold. A code with too many such nodes tends to not exhibit a minimum distance that grows linearly in block length. In this paper we also show that preceding can be used to lower the threshold of regular LDPC codes. The decoding thresholds of the proposed codes, which have linearly increasing minimum distance in block size, outperform that of regular LDPC codes. Furthermore, a family of low to high rate codes, with thresholds that adhere closely to their respective channel capacity thresholds, is presented. Simulation results for a few example codes show that the proposed codes have low error floors as well as good threshold SNR performance.

Globecom•Jan 1, 2005•120 citations

On the typical minimum distance of protograph-based non-binary LDPC codes

D. Divsalar, Lara Dolecek

This paper proves the existence of the typical minimum distance for certain ensembles of the protograph-based nonbinary (PB NB) LDPC codes with degree-2 variable nodes. Using recently obtained ensemble weight enumerators for the PB NB LDPC codes, we show that asymptotically in the code length N, the entries in the weight enumerators up to some weight d* = δ* N (δ* >; 0) vanish under certain conditions on degree-2 nodes. As a consequence, the probability that the code minimum distance is less than d* goes to zero as the code length goes to infinity. Results of this type advance the understanding of structured non-binary LDPC codes.

Information Theory and Applications Workshop (ITA)•Feb 1, 2012•8 citations

On the existence of typical minimum distance for protograph-based LDPC codes

Shadi Abu‐Surra, D. Divsalar, W.E. Ryan

In this paper we prove that, for a certain class of protograph-based LDPC codes with degree-two variable nodes, a typical minimum distance exists. We obtain a tight bound on the sum of weight enumerators, up to some weight d*, for the ensemble of finite-length protograph LDPC codes. Then we prove that this sum goes to zero as the block length goes to infinity. Finally, we prove that Pr(d < d*) goes to zero as the block length goes to infinity. This typical minimum distance exists if degree-two nodes have certain connections to the check nodes. This is also important in practice since it identifies a certain class of protograph LDPC codes that have typical minimum distances.

Information Theory and Applications Workshop (ITA)•Jan 1, 2010•33 citations
Recently, LDPC codes with projected graph, or protograph structures have been proposed. In this paper, finite length ensemble weight enumerators for LDPC codes with protograph structures are obtained. Asymptotic results are derived as the block size goes to infinity. In particular, we are interested in obtaining ensemble average weight enumerators for protograph LDPC codes which have typical minimum distance that grows linearly with block size. As with irregular ensembles, linear minimum distance property is sensitive to the proportion of degree-2 variable nodes. In this paper, the derived results on ensemble weight enumerators show that linear minimum distance condition on degree distribution of unstructured irregular LDPC codes is a sufficient but not a necessary condition for protograph LDPC codes
Protograph-based generalized LDPC (GLDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. Recently, a technique for computing ensemble weight enumerators for GLDPC codes has been published. In the current paper, we investigate the existence of typical minimum distance for protograph-based GLDPC codes. That is, we first upper bound the ensemble weight enumerators for finite-length GLDPC codes based on protographs, and then we consider the sum of weight enumerators. The results allow us to determine whether or not the typical minimum distance in the ensemble grows linearly with codeword length. We provide conditions on the connections of degree-2 variable nodes to constraint nodes (short block codes) to have typical minimum distance. These conditions are related to the minimum distances of the constraint nodes.
Protograph-based LDPC codes have the advantages of a simple design (or search) procedure and highly structured encoders and decoders. These advantages have also been exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. Recently, a technique for computing ensemble weight enumerators and stopping set enumerators for protograph-based LDPC codes has been published. In the current paper, we extend those results to protograph-based G-LDPC codes. That is, we first derive ensemble weight and stopping set enumerators for finite-length G-LDPC codes based on protographs, and then we consider the asymptotic case. In the weight enumerator case, the asymptotic results allow us to determine whether or not the typical minimum distance in the ensemble grows linearly with codeword length. In the stopping set enumerator case, the asymptotic results allows us to determine whether or not the typical smallest stopping set size grows linearly with codeword length.
Protograph-based LDPC codes have the advantages of a simple design (or search) procedure and highly structured encoders and decoders. These advantages have also been exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. Recently, a technique for computing ensemble weight enumerators for protograph-based LDPC codes has been published. In the current paper, we extend those results to protograph-based G-LDPC codes. That is, we first derive ensemble weight enumerators for finite-length G-LDPC codes based on protographs, and then we consider the asymptotic case. The asymptotic results allow us to determine whether or not the typical minimum distance in the ensemble grows linearly with codeword length.
We propose several LDPC code constructions that simultaneously achieve good threshold and error floor performance. Minimum distance is shown to grow linearly with block size (similar to regular codes of variable degree at least 3) by considering ensemble average weight enumerators. Our constructions are based on projected graph, or protograph, structures that support high-speed decoder implementations. As with irregular ensembles, our constructions are sensitive to the proportion of degree-2 variable nodes. A code with too few such nodes tends to have an iterative decoding threshold that is far from the capacity threshold. A code with too many such nodes tends to not exhibit a minimum distance that grows linearly in block length. In this paper we also show that preceding can be used to lower the threshold of regular LDPC codes. The decoding thresholds of the proposed codes, which have linearly increasing minimum distance in block size, outperform that of regular LDPC codes. Furthermore, a family of low to high rate codes, with thresholds that adhere closely to their respective channel capacity thresholds, is presented. Simulation results for a few example codes show that the proposed codes have low error floors as well as good threshold SNR performance.
This paper proves the existence of the typical minimum distance for certain ensembles of the protograph-based nonbinary (PB NB) LDPC codes with degree-2 variable nodes. Using recently obtained ensemble weight enumerators for the PB NB LDPC codes, we show that asymptotically in the code length N, the entries in the weight enumerators up to some weight d* = δ* N (δ* >; 0) vanish under certain conditions on degree-2 nodes. As a consequence, the probability that the code minimum distance is less than d* goes to zero as the code length goes to infinity. Results of this type advance the understanding of structured non-binary LDPC codes.
In this paper we prove that, for a certain class of protograph-based LDPC codes with degree-two variable nodes, a typical minimum distance exists. We obtain a tight bound on the sum of weight enumerators, up to some weight d*, for the ensemble of finite-length protograph LDPC codes. Then we prove that this sum goes to zero as the block length goes to infinity. Finally, we prove that Pr(d < d*) goes to zero as the block length goes to infinity. This typical minimum distance exists if degree-two nodes have certain connections to the check nodes. This is also important in practice since it identifies a certain class of protograph LDPC codes that have typical minimum distances.