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)

Ensemble analysis of pseudocodewords of protograph-based non-binary LDPC codes

D. Divsalar, Lara Dolecek

Published Oct 1, 2011• 3 citations
Publisher

Abstract

This paper presents a method for evaluating pseudocodeword weight enumerators of nonbinary LDPC codes built out of protographs. The ensemble enumerators are evaluated for both the finite-length and infinite-length regimes. Results of this type can be particularly useful for designing structured non-binary LDPC codes with good properties under message passing or linear programming decoding.

DOI
10.1109/itw.2011.6089475

Related papers

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

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

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

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.

IEEE Transactions on Information Theory•Jan 21, 2011•101 citations

Non-Binary Protograph-Based LDPC Codes: Enumerators, Analysis, and Designs

Lara Dolecek, D. Divsalar, Yizeng Sun +1 more

This paper provides a comprehensive analysis of nonbinary low-density parity check (LDPC) codes built out of protographs. We consider both random and constrained edge-weight labeling, and refer to the former as the unconstrained nonbinary protograph-based LDPC codes (U-NBPB codes) and to the latter as the constrained nonbinary protograph-based LDPC codes (C-NBPB codes). Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codewords, trapping sets, stopping sets, and pseudocodewords are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. An EXIT chart tool for computing the iterative decoding thresholds of protograph-based LDPC codes is presented, followed by several examples of finite-length U-NBPB and C-NBPB codes with high performance. Throughout this paper, we provide accompanying examples, which demonstrate the advantage of nonbinary protograph-based LDPC codes over their binary counterparts and over random constructions. The results presented in this paper advance the analytical toolbox of nonbinary graph-based codes.

IEEE Transactions on Information Theory•Apr 9, 2014•95 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

Enumerators for protograph-based ensembles of nonbinary LDPC codes

D. Divsalar, Lara Dolecek

This paper considers the ensemble enumerators of protograph-based nonbinary (PB NB) LDPC codes. Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codeword weight, trapping set size and stopping set size are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. Our results can provide useful analytical tools for a range of communication and storage applications employing nonbinary LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•8 citations

Non-Binary Protograph-Based LDPC Codes: Analysis, Enumerators and Designs

Yizeng Sun

Non-binary LDPC codes can outperform binary LDPC codes using sum-product algorithm with higher computation complexity. Non-binary LDPC codes based on protographs have the advantage of simple hardware architecture. In the first part of this thesis, we will use EXIT chart analysis to compute the thresholds of different protographs over GF(q). Based on threshold computation, some non-binary protograph-based LDPC codes are designed and their frame error rates are compared with binary LDPC codes. For maximum-likelihood decoder, weight enumerator can predict frame error rate of an LDPC code. In the second part of this thesis, we calculate weight enumerators of protograph-based non-binary LDPC code ensembles both for finite length case and asymptotic case. In addition, the trapping set and stopping set enumerators are presented.

•Jan 1, 2013•0 citations
This paper presents a method for evaluating pseudocodeword weight enumerators of nonbinary LDPC codes built out of protographs. The ensemble enumerators are evaluated for both the finite-length and infinite-length regimes. Results of this type can be particularly useful for designing structured non-binary LDPC codes with good properties under message passing or linear programming decoding.
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.
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.
This paper provides a comprehensive analysis of nonbinary low-density parity check (LDPC) codes built out of protographs. We consider both random and constrained edge-weight labeling, and refer to the former as the unconstrained nonbinary protograph-based LDPC codes (U-NBPB codes) and to the latter as the constrained nonbinary protograph-based LDPC codes (C-NBPB codes). Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codewords, trapping sets, stopping sets, and pseudocodewords are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. An EXIT chart tool for computing the iterative decoding thresholds of protograph-based LDPC codes is presented, followed by several examples of finite-length U-NBPB and C-NBPB codes with high performance. Throughout this paper, we provide accompanying examples, which demonstrate the advantage of nonbinary protograph-based LDPC codes over their binary counterparts and over random constructions. The results presented in this paper advance the analytical toolbox of nonbinary graph-based codes.
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.
This paper considers the ensemble enumerators of protograph-based nonbinary (PB NB) LDPC codes. Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codeword weight, trapping set size and stopping set size are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. Our results can provide useful analytical tools for a range of communication and storage applications employing nonbinary LDPC codes.
Non-binary LDPC codes can outperform binary LDPC codes using sum-product algorithm with higher computation complexity. Non-binary LDPC codes based on protographs have the advantage of simple hardware architecture. In the first part of this thesis, we will use EXIT chart analysis to compute the thresholds of different protographs over GF(q). Based on threshold computation, some non-binary protograph-based LDPC codes are designed and their frame error rates are compared with binary LDPC codes. For maximum-likelihood decoder, weight enumerator can predict frame error rate of an LDPC code. In the second part of this thesis, we calculate weight enumerators of protograph-based non-binary LDPC code ensembles both for finite length case and asymptotic case. In addition, the trapping set and stopping set enumerators are presented.