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 Transactions on Information Theory

Enumerators for Protograph-Based Ensembles of LDPC and Generalized LDPC Codes

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

Published Jan 21, 2011• 101 citations
Publisher

Abstract

Protograph-based LDPC and generalized LDPC (G-LDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. The design of such “protograph-based codes” relies on what is effectively a computer-based search. As such, following Gallager, it is prudent to restrict the search to a “good ensemble,” for example, an ensemble whose minimum distance grows linearly with codeword length. A good ensemble can also mean one with good stopping set, trapping set, or pseudocodeword properties. In this paper, ensemble codeword weight enumerators for finite-length LDPC and G-LDPC codes based on protographs were derived, and then the asymptotic case was considered. The asymptotic results allow us to determine whether or not the typical relative minimum distance in the ensemble grows linearly with codeword length. Then, the codeword weight enumerator technique is adapted to yield ensemble stopping set, trapping set, and pseudocodeword enumerators for protograph LDPC and G-LDPC codes. In this case, the asymptotic results allow us to determine whether or not the typical relative smallest stopping set size, trapping set size, and pseudoweight grows linearly with codeword length. Trapping set enumerators for G-LDPC code ensembles represent a more complex problem which we do not consider here.

DOI
10.1109/tit.2010.2094819

Related papers

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 generalized LDPC codes: Enumerators, design, and applications

Shadi Abu‐Surra

Among the recent advances in the area of low-density parity-check (LDPC) codes, protograph-based LDPC codes have the advantages of a simple design procedure and highly structured encoders and decoders. These advantages can also be exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. In this dissertation we provide analytical tools which aid the design of protograph-based LDPC and G-LDPC codes. Specifically, we propose a method for computing the codeword-weight enumerators for finite-length protograph-based G-LDPC code ensembles, and then we consider the asymptotic case when the block-length goes to infinity. These results help the designer identify good ensembles of protograph-based G-LDPC codes in the minimum distance sense (i.e., ensembles which have minimum distances grow linearly with code length). Furthermore, good code ensembles can be characterized by good stopping set, trapping set, or pseudocodeword properties, which assist in the design of G-LDPC codes with low floors. We leverage our method for computing codeword-weight enumerators to compute stopping-set, and pseudocodeword enumerators for the finite-length and the asymptotic ensembles of protograph-based G-LDPC codes. Moreover, we introduce a method for computing trapping set enumerators for finite-length (and asymptotic) protograph-based LDPC code ensembles. Trapping set enumerators for G-LDPC codes represents a more complex problem which we do not consider here. Inspired by our method for computing trapping set enumerators for protograph-based LDPC code ensembles, we developed an algorithm for estimating the trapping set enumerators for a specific LDPC code given its parity-check matrix. We used this algorithm to enumerate trapping sets for several LDPC codes from communication standards. Finally, we study coded-modulation schemes with LDPC codes and pulse position modulation (LDPC-PPM) over the free-space optical channel. We present three different decoding schemes and compare their performances. In addition, we developed a new density evolution tool for use in the design of LDPC codes with good performances over this channel.

•Jan 1, 2009•1 citation

Ensemble Pseudocodeword Weight Enumerators for Protograph-Based Generalized LDPC Codes

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

Recently, pseudocodewords of Tanner graphs of LDPC codes have been used to explain the behavior of iterative decoders for these codes. In this paper, finite-length pseudocodeword weight enumerators for protograph-based generalized-LDPC code ensembles are obtained. Then asymptotic results are derived from the finite-length results by letting the block length go to infinity. The asymptotic results allow us to determine whether or not the typical minimum pseudocodeword weight grows linearly with codeword length. We give examples with Hamming component codes.

Globecom•Nov 1, 2009•1 citation

Stopping-Set Enumerator Approximations for Finite-Length Protograph LDPC Codes

Kaiann Fu, Achilleas Anastasopoulos

Asymptotic analysis of low-density parity-check (LDPC) code weight and stopping-set enumerators, for codewords and stopping sets which grow linearly with codelength, has aided in designing codes with linear minimum distance and low error floors. However, the analysis cannot capture the behavior of codewords and stopping sets that grow sublinearly with codelength. Thus, it is unclear how well the analysis describes behavior for finite codelengths, particularly for short codes. In this paper, we provide another perspective on protograph-based and standard LDPC ensemble enumerators, based on analysis of stopping sets with sublinear growth, which brings new insight into sublinear stopping-set behavior, protograph structure, and preceding. Using approximations to the stopping-set enumerators, we show that for stopping sets that grow at most logarithmically with codelength, the enumerators follow a polynomial relationship with codelength, unlike the exponential relationship for linearly- growing stopping sets. Further, we analyze for what stopping-set sizes and codelengths the approximations apply.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•11 citations

Asymptotic ensemble enumerators for protograph-based generalized LDPC codes: Computational complexity

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

In earlier work, we presented a method for finding ensemble weight enumerator for protograph-based generalized LDPC (G-LDPC) codes, and leveraged this method to find ensemble stopping set enumerator and ensemble trapping set enumerator. The method is conceptually simple, but when the dimensionality of the constraint nodes (number of their code-words) grows, it becomes difficult to handle the computational complexity, which rise while evaluating these enumerators. To deal with this difficulty, we posed a conjecture, which greatly reduce the computational complexity. Trails to proof this conjecture showed that the proof is a challenging problem. Also, proving it will strengthen the theory of enumerating protograph-based G-LDPC code ensembles. Which in turn helps in predicating the average performances for codes drawn from these ensembles. In Section II we present a review of our method for finding finite and asymptotic weight enumerators for protograph-based G-LDPC code ensembles. Then, we present the conjecture in Section III with some examples.

Information Theory and Applications Workshop (ITA)•Jan 1, 2008•6 citations
Protograph-based LDPC and generalized LDPC (G-LDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. The design of such “protograph-based codes” relies on what is effectively a computer-based search. As such, following Gallager, it is prudent to restrict the search to a “good ensemble,” for example, an ensemble whose minimum distance grows linearly with codeword length. A good ensemble can also mean one with good stopping set, trapping set, or pseudocodeword properties. In this paper, ensemble codeword weight enumerators for finite-length LDPC and G-LDPC codes based on protographs were derived, and then the asymptotic case was considered. The asymptotic results allow us to determine whether or not the typical relative minimum distance in the ensemble grows linearly with codeword length. Then, the codeword weight enumerator technique is adapted to yield ensemble stopping set, trapping set, and pseudocodeword enumerators for protograph LDPC and G-LDPC codes. In this case, the asymptotic results allow us to determine whether or not the typical relative smallest stopping set size, trapping set size, and pseudoweight grows linearly with codeword length. Trapping set enumerators for G-LDPC code ensembles represent a more complex problem which we do not consider here.
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.
Among the recent advances in the area of low-density parity-check (LDPC) codes, protograph-based LDPC codes have the advantages of a simple design procedure and highly structured encoders and decoders. These advantages can also be exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. In this dissertation we provide analytical tools which aid the design of protograph-based LDPC and G-LDPC codes. Specifically, we propose a method for computing the codeword-weight enumerators for finite-length protograph-based G-LDPC code ensembles, and then we consider the asymptotic case when the block-length goes to infinity. These results help the designer identify good ensembles of protograph-based G-LDPC codes in the minimum distance sense (i.e., ensembles which have minimum distances grow linearly with code length). Furthermore, good code ensembles can be characterized by good stopping set, trapping set, or pseudocodeword properties, which assist in the design of G-LDPC codes with low floors. We leverage our method for computing codeword-weight enumerators to compute stopping-set, and pseudocodeword enumerators for the finite-length and the asymptotic ensembles of protograph-based G-LDPC codes. Moreover, we introduce a method for computing trapping set enumerators for finite-length (and asymptotic) protograph-based LDPC code ensembles. Trapping set enumerators for G-LDPC codes represents a more complex problem which we do not consider here. Inspired by our method for computing trapping set enumerators for protograph-based LDPC code ensembles, we developed an algorithm for estimating the trapping set enumerators for a specific LDPC code given its parity-check matrix. We used this algorithm to enumerate trapping sets for several LDPC codes from communication standards. Finally, we study coded-modulation schemes with LDPC codes and pulse position modulation (LDPC-PPM) over the free-space optical channel. We present three different decoding schemes and compare their performances. In addition, we developed a new density evolution tool for use in the design of LDPC codes with good performances over this channel.
Recently, pseudocodewords of Tanner graphs of LDPC codes have been used to explain the behavior of iterative decoders for these codes. In this paper, finite-length pseudocodeword weight enumerators for protograph-based generalized-LDPC code ensembles are obtained. Then asymptotic results are derived from the finite-length results by letting the block length go to infinity. The asymptotic results allow us to determine whether or not the typical minimum pseudocodeword weight grows linearly with codeword length. We give examples with Hamming component codes.
Asymptotic analysis of low-density parity-check (LDPC) code weight and stopping-set enumerators, for codewords and stopping sets which grow linearly with codelength, has aided in designing codes with linear minimum distance and low error floors. However, the analysis cannot capture the behavior of codewords and stopping sets that grow sublinearly with codelength. Thus, it is unclear how well the analysis describes behavior for finite codelengths, particularly for short codes. In this paper, we provide another perspective on protograph-based and standard LDPC ensemble enumerators, based on analysis of stopping sets with sublinear growth, which brings new insight into sublinear stopping-set behavior, protograph structure, and preceding. Using approximations to the stopping-set enumerators, we show that for stopping sets that grow at most logarithmically with codelength, the enumerators follow a polynomial relationship with codelength, unlike the exponential relationship for linearly- growing stopping sets. Further, we analyze for what stopping-set sizes and codelengths the approximations apply.
In earlier work, we presented a method for finding ensemble weight enumerator for protograph-based generalized LDPC (G-LDPC) codes, and leveraged this method to find ensemble stopping set enumerator and ensemble trapping set enumerator. The method is conceptually simple, but when the dimensionality of the constraint nodes (number of their code-words) grows, it becomes difficult to handle the computational complexity, which rise while evaluating these enumerators. To deal with this difficulty, we posed a conjecture, which greatly reduce the computational complexity. Trails to proof this conjecture showed that the proof is a challenging problem. Also, proving it will strengthen the theory of enumerating protograph-based G-LDPC code ensembles. Which in turn helps in predicating the average performances for codes drawn from these ensembles. In Section II we present a review of our method for finding finite and asymptotic weight enumerators for protograph-based G-LDPC code ensembles. Then, we present the conjecture in Section III with some examples.