Spatially Coupled Generalized LDPC Codes: Asymptotic Analysis and Finite Length Scaling

David G. M. Mitchell, Pablo M. Olmos, Michael Lentmaier, Daniel J. Costello Jr.

Abstract

Generalized low-density parity-check (GLDPC) codes are a class of LDPC codes in which the standard single parity check (SPC) constraints are replaced by constraints defined by a linear block code. These stronger constraints typically result in improved error floor performance, due to better minimum distance and trapping set properties, at a cost of some increased decoding complexity. In this paper, we study spatially coupled generalized low-density parity-check (SC-GLDPC) codes and present a comprehensive analysis of these codes, including: (1) an iterative decoding threshold analysis demonstrating capacity approaching thresholds via the threshold saturation effect; (2) an asymptotic analysis of the minimum distance properties demonstrating that the ensembles are asymptotically good; and (3) an analysis of the finite-length scaling behavior based on a peeling decoder (PD) operating on a binary erasure channel (BEC).

Introduction

In channel coding, designers often face a fundamental trade-off between the waterfall region (the signal quality threshold where the code begins to function) and the error floor (performance at high signal-to-noise ratios). Standard Low-Density Parity-Check (LDPC) codes utilize simple Single Parity Check (SPC) constraints. While efficient, regular LDPC codes often exhibit mediocre thresholds, whereas irregular LDPC codes achieve excellent thresholds but suffer from high error floors due to the presence of low-degree nodes.

Generalized LDPC (GLDPC) codes address this by replacing SPC nodes with more powerful linear block codes, such as Hamming codes. This significantly lowers the error floor but typically degrades the iterative decoding threshold. This research explores Spatial Coupling (SC)—a technique of "weaving" code blocks together over time—as a mechanism to recover these lost thresholds for GLDPC codes without sacrificing their superior distance properties.

Methods

The authors utilize a protograph-based construction to design SC-GLDPC ensembles. The construction relies on Edge Spreading, a technique that transforms a block GLDPC protograph into a convolutional-like spatially coupled structure by distributing edges across multiple time slots.

Protograph of a spatially coupled GLDPC (SC-GLDPC) code ensemble showing the convolutional-like structure across time slots.

To evaluate these designs, the study employs:

  • Density Evolution (DE): To analyze asymptotic iterative decoding thresholds over the Binary Erasure Channel (BEC).
  • Asymptotic Weight Enumerators: To prove the ensembles are "asymptotically good," meaning their minimum distance increases linearly with code length ($n$).
  • Generalized Peeling Decoder (GPD): An extension of the standard peeling decoder used to derive scaling laws that predict block error rates based on the "decoding wave" effect.

Key Insights

  • Threshold Saturation: Numerical analysis confirms that SC-GLDPC codes exhibit threshold saturation. The iterative Belief Propagation (BP) decoder's threshold for the coupled code "saturates" to the optimal Maximum A Posteriori (MAP) threshold of the underlying uncoupled block code.
  • Decoding Waves: In finite-length scenarios, decoding in SC-GLDPC codes proceeds as a "wave" initiated from the boundaries where constraints are stronger due to termination. This behavior makes the codes more robust to local erasure clusters than standard block codes.
  • The Best of Both Worlds: By coupling GLDPC codes, the researchers achieve the high-speed waterfall performance of capacity-approaching codes alongside the robust error floor of codes with high minimum distance.

Results

The analysis demonstrates that SC-GLDPC codes significantly outperform their uncoupled counterparts. For a (2,7)-regular GLDPC code using Hamming constraints, spatial coupling improved the BP threshold from 0.756 to 0.856, nearly reaching the theoretical MAP limit of 0.857.

BP EXIT function for a GLDPC ensemble, illustrating the gap between BP and MAP thresholds that spatial coupling helps to close via threshold saturation.

Furthermore, spectral shape functions confirm that these codes maintain a positive minimum distance growth rate ($\delta_{min} > 0$), ensuring long-term reliability. Finite-length scaling analysis also showed that SC-GLDPC codes converge to their asymptotic thresholds faster than uncoupled GLDPC codes as the lifting factor increases.

Limitations and Future Work

While promising, the current analysis primarily focuses on the Binary Erasure Channel (BEC). Extending these mathematical proofs to more complex channels, such as Additive White Gaussian Noise (AWGN), remains a challenge. Additionally, while iterative decoding is linear, generalized constraints add a constant complexity factor. Future research may focus on optimizing sliding window decoders to mitigate the latency inherent in the convolutional structure of spatially coupled codes.

Summary updated

Abstract

Generalized low-density parity-check (GLDPC) codes are a class of LDPC codes in which the standard single parity check (SPC) constraints are replaced by constraints defined by a linear block code. These stronger constraints typically result in improved error floor performance, due to better minimum distance and trapping set properties, at a cost of some increased decoding complexity. In this paper, we study spatially coupled generalized low-density parity-check (SC-GLDPC) codes and present a comprehensive analysis of these codes, including: (1) an iterative decoding threshold analysis of SC-GLDPC code ensembles demonstrating capacity approaching thresholds via the threshold saturation effect; (2) an asymptotic analysis of the minimum distance and free distance properties of SC-GLDPC code ensembles, demonstrating that the ensembles are asymptotically good; and (3) an analysis of the finite-length scaling behavior of both GLDPC block codes and SC-GLDPC codes based on a peeling decoder (PD) operating on a binary erasure channel (BEC). Results are compared to GLDPC block codes, and the advantages and disadvantages of SC-GLDPC codes are discussed.
BibTeX
@article{mitchell2021spatially,
  author = {David G. M. Mitchell and Pablo M. Olmos and Michael Lentmaier and Daniel J. Costello Jr.},
  title = {{Spatially Coupled Generalized LDPC Codes: Asymptotic Analysis and Finite Length Scaling}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=m1551pk0Da},
}
Figure