IEEE International Symposium on Information Theory (ISIT)

Graph cover ensembles of non-binary protograph LDPC codes

D. Divsalar, Lara Dolecek

Published Jul 1, 2012• 13 citations

Abstract

This paper introduces a novel class of non-binary graph-based codes, built upon graph covers of non-binary protograph LDPC codes. This new ensemble is more restrictive than previously considered constructions, but in turn is much simpler to design and implement. The simplifications in design allow for the enumeration of codeword weight, trapping set size, stopping set size, and pseudo codeword weights, both as exact quantities in the finite-length regime and as corresponding growth rates in the asymptotic setting. The presented construction and the accompanying enumerations enhance the analytical toolbox of non-binary LDPC codes.

DOI: 10.1109/isit.2012.6283972

Related papers

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 TheoryApr 9, 201495 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, 20118 citations

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 TheoryJan 21, 2011101 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.

GlobecomNov 1, 200713 citations

Non-binary protograph-based LDPC codes for short block-lengths

Ben-Yue Chang, D. Divsalar, Lara Dolecek

This paper presents two complementary constructions of finite-length non-binary protograph-based codes with the focus on the short block-length regime. The first class is based on the existing approaches of applying the copy-and-permute operations to the constituent protograph with unweighted edges, followed by assigning non-binary scales to the edges of the derived graph. The second class is novel and is based on the so-called graph cover of a non-binary protograph: the original protograph has fixed edge scalings and copy-and-permute operations are applied to the edge-weighted protograph. The second class is arguably more restrictive, but in turn it offers simpler design and implementation. We provide design and construction of these non-binary codes for short block-lengths. Performance, cycle distribution and the minimum distance of the binary image of selected codes over AWGN is provided for information block-lengths as low as 64 bits.

IEEE Information Theory Workshop (ITW)Sep 1, 201236 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, 20130 citations