Construction of Protograph-Based Partially Doped Generalized LDPC Codes

Jaewha Kim, Jae-Won Kim, Heeyoul Kwak, Jong-Seon No

TL;DR

This paper introduces a novel "partial doping" technique for constructing generalized low-density parity-check (GLDPC) codes, offering greater flexibility and improved performance over existing methods. By selectively "doping" individual variable nodes, these new Partially Doped GLDPC (PD-GLDPC) codes achieve better error correction capabilities and a more desirable trade-off between code rate and minimum distance, particularly for medium to high code rates.

What Problem Does This Paper Address?

Traditional generalized low-density parity-check (GLDPC) codes, especially those based on protographs, offer excellent error correction performance. However, their construction, particularly the "doping" process (replacing single parity-check nodes with more complex generalized constraint nodes), has limitations. The conventional doping technique has a fixed "granularity," meaning it affects a group of variable nodes dictated by the component code's parameters. This inflexibility restricts the ability to finely tune code design for specific performance goals, especially for higher code rates where achieving a good balance between error correction and data rate is crucial. Furthermore, the optimization and analysis of these codes can be computationally intensive.

Methods

The core innovation is the partial doping technique. Unlike conventional methods that dope entire check nodes, this approach allows for the selective "doping" of individual variable nodes after the protograph has been "lifted" (expanded into a larger graph). This means that a generalized constraint (GC) node can be connected to a subset of the lifted variable nodes originating from a single protograph variable node, effectively reducing the doping granularity to one.

Key aspects of their approach include:

  • Partial Doping: GC nodes are applied to specific variable nodes, offering finer control over code structure.
  • Protograph EXIT (PEXIT) Analysis: This standard technique is adapted for the PD-GLDPC codes. A key advantage highlighted is that the PEXIT analysis for PD-GLDPC codes is more accurate than for conventional doped GLDPC codes because the mutual information is derived from a single protograph variable node, not an average over multiple.
  • Minimum Distance Growth Condition: The authors propose and prove a condition that guarantees the linear growth of the minimum distance with code length, which is crucial for avoiding error floors.
  • Optimization Algorithms: They employ differential evolution and protograph construction algorithms (like PEG) to optimize the code design, balancing performance metrics like the error floor and coding gain.
  • Puncturing: To compensate for the rate loss introduced by doping, a puncturing technique is applied to the doped variable nodes, which is shown to be less detrimental to performance due to the localized protection offered by partial doping.

Datasets

Not discussed in the paper. The paper focuses on code construction and theoretical analysis, with performance evaluated through simulations on the Binary Erasure Channel (BEC).

Key Insights and Ideas

  • Granularity Matters: Reducing the doping granularity from the component code's constraint length to a single variable node provides significantly more design freedom and allows for more sophisticated code optimization.
  • Localized Protection: Partial doping provides protection to specific variable nodes, making the performance impact of puncturing (used to recover code rate) less severe.
  • Improved PEXIT Accuracy: The PEXIT analysis for PD-GLDPC codes is more accurate due to the direct link between GC nodes and single protograph variable nodes, simplifying optimization.
  • Balancing Degree-2 VNs: The paper emphasizes the importance of balancing the number of degree-2 variable nodes (which improve asymptotic performance) with the need for a typical minimum distance (which prevents error floors). Partial doping is shown to be an effective tool for achieving this balance.

Key Results

  • Outperformance: Optimized PD-GLDPC codes demonstrate superior performance compared to conventional GLDPC codes and competitive performance against state-of-the-art protograph-based LDPC codes on the Binary Erasure Channel (BEC).
  • Coding Gain: For a low doping ratio (0.02439), the proposed PD-GLDPC codes achieve a coding gain of 0.0079 over optimized GLDPC codes with a higher doping ratio (0.4).
  • Reduced Complexity: The average VN degree of the optimized PD-GLDPC codes is lower than that of comparable state-of-the-art protograph LDPC codes, suggesting potential for reduced decoding complexity.
  • No Error Floor: The proposed codes exhibit a desirable waterfall performance and avoid the error floor phenomenon up to frame error rates of 10⁻⁴.
  • Linear Minimum Distance Growth: The proposed condition for typical minimum distance guarantees that the minimum distance grows linearly with the code length, crucial for large codes.

Limitations and Future Work

  • Focus on BEC: The current work primarily focuses on the Binary Erasure Channel (BEC). Future work could explore performance over other channel models, such as additive white Gaussian noise (AWGN).
  • Component Codes: The paper primarily uses Hamming codes as component codes. Investigating the use of other component codes could yield further improvements.
  • Generalizing Partial Doping: The authors suggest exploring more generalized partial doping strategies, such as doping over multiple protograph VNs or doping only a portion of a protograph VN.
  • Degree-1 VNs: Future research could also investigate the use of protographs with degree-1 VNs.

Summary updated

Abstract

A generalized low-density parity-check (GLDPC) code is a class of codes, where single parity check nodes in a conventional low-density parity-check (LDPC) code are replaced by linear codes with higher parity check constraints. In this paper, we introduce a new method of constructing GLDPC codes by inserting the generalized check nodes for partial doping. While the conventional protograph GLDPC code dopes the protograph check nodes by replacing them with the generalized check nodes, a new GLDPC code is constructed by adding the generalized check nodes and partially doping the selected variable nodes to possess higher degrees of freedom, called a partially doped GLDPC (PD-GLDPC) code. The proposed PD-GLDPC codes can make it possible to do more accurate extrinsic information transfer (EXIT) analysis and the doping granularity can become finer in terms of the protograph than the conventional GLDPC code. We also propose the constraint for the typical minimum distance of PD-GLDPC codes and prove that the PD-GLDPC codes satisfying this condition have the linear minimum distance growth property. Furthermore, we obtain the threshold optimized protograph for both regular and irregular ensembles of the proposed PD-GLDPC codes over the binary erasure channel (BEC). Specifically, we propose the construction algorithms for both regular and irregular protograph-based PD-GLDPC codes that enable the construction of GLDPC codes with higher rates than the conventional ones. The block error rate performance of the proposed PD-GLDPC code shows that it has a reasonably good waterfall performance with low error floor and outperforms other LDPC codes for the same code rate, code length, and degree distribution.
BibTeX
@article{kim2022construction,
  author = {Jaewha Kim and Jae-Won Kim and Heeyoul Kwak and Jong-Seon No},
  title = {{Construction of Protograph-Based Partially Doped Generalized LDPC Codes}},
  journal = {IEEE Access},
  year = {2022},
  doi = {10.1109/access.2022.3204317},
}
Figure