Successive Cancellation Decoding of Single Parity-Check Product Codes: Analysis and Improved Decoding

Mustafa Cemil Coskun, Gianluigi Liva, Alexandre Graell i Amat, Michael Lentmaier, Henry D. Pfister

TL;DR

This paper reveals that classic Single Parity-Check (SPC) product codes can be mathematically framed as a special case of multi-kernel polar codes. By applying Successive Cancellation (SC) and List (SCL) decoding—techniques originally designed for polar codes—the authors demonstrate significant performance gains over traditional decoding methods, even outperforming 5G-standard LDPC codes in short-blocklength regimes.

What Problem Does This Paper Address?

Product codes, introduced by Elias in 1954, are a foundational class of error-correcting codes built by arranging bits in a multi-dimensional array and ensuring every row and column satisfies a parity check. While they are robust and easy to implement, traditional decoding methods like Belief Propagation (BP) or Elias’s original serial decoding often fall short of optimal performance for short-to-moderate blocklengths.

The authors aim to bridge the gap between classic product codes and modern polar coding theory. They seek to determine if the recursive, likelihood-based decoding structures that make polar codes so efficient can be adapted to improve the reliability of SPC product codes.

Methods

The paper introduces several novel theoretical and algorithmic bridges:

  1. The Multi-Kernel Polar Connection: The authors prove that the generator matrix of an $m$-dimensional SPC product code is equivalent to a multi-kernel polar transform where specific bits are "frozen" (set to zero).
  2. Successive Cancellation (SC) Decoding: They adapt the SC algorithm to product codes. Instead of decoding component codes independently or iteratively (like BP), SC decodes bits one by one, using the decisions of previous bits to improve the likelihood estimates of the current one.
  3. Successive Cancellation List (SCL) Decoding: To further improve performance, they implement SCL decoding, which maintains a list of $L$ likely candidate paths.
  4. CRC Concatenation: Borrowing a trick from 5G polar codes, they concatenate the product code with a high-rate outer Cyclic Redundancy Check (CRC). The CRC is used at the end of the SCL process to pick the correct codeword from the list.
  5. Distance Spectrum Analysis: The authors derive new closed-form expressions for the weight enumerators (the distribution of codeword weights) for these codes, allowing them to calculate theoretical performance bounds (like Poltyrev’s Tangential-Sphere Bound).

Datasets

As a theoretical communications paper, this work does not use external datasets. Instead, it evaluates performance through rigorous Monte Carlo simulations over standard channel models:

  • Binary Erasure Channel (BEC): Used for proving fundamental theorems about decoding success.
  • Binary-Input Additive White Gaussian Noise (B-AWGN) Channel: Used to simulate real-world wireless conditions.

Key Insights and Ideas

  • SC > Elias: The authors prove that on the Binary Erasure Channel, SC decoding is guaranteed to perform at least as well as, and often better than, Elias’s original 1954 decoding algorithm.
  • The "Frozen Bit" Perspective: By viewing product codes through the lens of polar coding, the "structure" of the product code is essentially redefined as a specific pattern of frozen bits in a larger polar-like transform.
  • The Asymptotic Trap: Interestingly, the authors find that while these codes are great for short blocks, they aren't necessarily "capacity-achieving" in the same way standard polar codes are. For certain infinite sequences of SPC product codes, the SC decoding threshold actually drops to zero as the number of dimensions increases.
  • List Decoding is the Equalizer: For short blocks (e.g., length 125), SCL decoding with a small list size ($L=8$) allows the code to perform very close to the theoretical Maximum Likelihood (ML) limit, which BP decoding cannot achieve.

Key Results

  • Proximity to Limits: Examples of concatenated SPC product codes were shown to perform within 0.7 dB of the Random Coding Union (RCU) bound—a benchmark for the absolute limits of channel coding at finite lengths.
  • Beating 5G Standards: In specific short-blocklength scenarios, the SCL-decoded SPC product code outperformed the 5G-NR LDPC code (Base Graph 2) by approximately 0.6 dB.
  • BP vs. SCL: For a (125, 64) code, SCL decoding with a list of 4 was sufficient to significantly outperform Belief Propagation (BP) decoding with 100 iterations.

Limitations and Future Work

  • Complexity vs. Dimension: While the SC/SCL approach is efficient, the analysis primarily focuses on Single Parity-Check (SPC) components. Extending this to more complex component codes (like Hamming codes) is mentioned but not explored in the same depth.
  • Asymptotic Performance: The finding that the SC threshold vanishes for certain infinite-dimensional SPC codes suggests that these specific constructions are best suited for "short and fat" dimensions rather than "infinitely deep" ones.
  • Interleaver Optimization: The authors note that further gains could be achieved by optimizing the interleaver between the CRC and the product code, which was not the focus of this specific study.

Summary updated

Abstract

A product code with single parity-check component codes can be described via the tools of a multi-kernel polar code, where the rows of the generator matrix are chosen according to the constraints imposed by the product code construction. Following this observation, successive cancellation decoding of such codes is introduced. In particular, the error probability of single parity-check product codes over binary memoryless symmetric channels under successive cancellation decoding is characterized. A bridge with the analysis of product codes introduced by Elias is also established for the binary erasure channel. Successive cancellation list decoding of single parity-check product codes is then described. For the provided example, simulations over the binary input additive white Gaussian channel show that successive cancellation list decoding outperforms belief propagation decoding applied to the code graph. Finally, the performance of the concatenation of a product code with a high-rate outer code is investigated via distance spectrum analysis. Examples of concatenations performing within 0.7 dB from the random coding union bound are provided.
BibTeX
@article{coskun2023successive,
  author = {Mustafa Cemil Coskun and Gianluigi Liva and Alexandre Graell i Amat and Michael Lentmaier and Henry D. Pfister},
  title = {{Successive Cancellation Decoding of Single Parity-Check Product Codes: Analysis and Improved Decoding}},
  journal = {IEEE Trans. Information Theory},
  year = {2023},
  doi = {10.1109/tit.2022.3207802},
}

Loading related content...

Figure