A Probabilistic Peeling Decoder to Efficiently Analyze Generalized LDPC Codes Over the BEC

Abstract

In this paper, we analyze the tradeoff between coding rate and asymptotic performance of a class of generalized low-density parity-check (GLDPC) codes constructed by including a certain fraction of generalized constraint (GC) nodes in the graph. The rate of the GLDPC ensemble is bounded using classical results on linear block codes, namely Hamming bound and Varshamov bound. We also study the impact of the decoding method used at GC nodes. To incorporate both bounded-distance (BD) and Maximum Likelihood (ML) decoding at GC nodes into our analysis without resorting on multi-edge type of degree distributions (DDs), we propose the probabilistic peeling decoding (P-PD) algorithm, which models the decoding step at every GC node as an instance of a Bernoulli random variable with a successful decoding probability that depends on both the GC block code as well as its decoding algorithm. The P-PD asymptotic performance over the BEC can be efficiently predicted using standard techniques for LDPC codes such as density evolution (DE) or the differential equation method. Furthermore, for a class of GLDPC ensembles, we demonstrate that the simulated P-PD performance accurately predicts the actual performance of the GLPDC code under ML decoding at GC nodes. We illustrate our analysis for GLDPC code ensembles with regular and irregular DDs. In all cases, we show that a large fraction of GC nodes is required to reduce the original gap to capacity, but the optimal fraction is strictly smaller than one. We then consider techniques to further reduce the gap to capacity by means of random puncturing, and the inclusion of a certain fraction of generalized variable nodes in the graph.

arXiv commentSubmitted to IEEE Transactions on Information Theory, August 2017

References in corpus (7)

• Maxwell Construction: The Hidden Bridge between Iterative and Maximum a Posteriori Decoding
• A Scaling Law to Predict the Finite-Length Performance of Spatially-Coupled LDPC Codes
• On the Minimum Distance of Generalized Spatially Coupled LDPC Codes
• Design of LDPC Code Ensembles with Fast Convergence Properties
• Spectral Shape of Doubly-Generalized LDPC Codes: Efficient and Exact Evaluation
• Approaching Capacity at High-Rates with Iterative Hard-Decision Decoding
• Generalized Stability Condition for Generalized and Doubly-Generalized LDPC Codes

Cited by in corpus (3)

• Spatially Coupled Generalized LDPC Codes: Asymptotic Analysis and Finite Length Scaling
• Construction of Protograph-Based Partially Doped Generalized LDPC Codes
• Sparse Signatures with Forward Error Correction Coding for Non-Orthogonal Massive Access