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.
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.
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.
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.
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.