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

Abstract

A product code with single parity-check (SPC) 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 (SC) decoding of such codes is introduced. In particular, the error probability of SPC product codes over binary memoryless symmetric channels under SC 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 (SCL) decoding of SPC product codes is then described. For the provided example, simulations over the binary input additive white Gaussian channel show that SCL 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.

Introduction

Product codes, introduced by Elias in 1954, are a foundational class of error-correcting codes constructed by arranging data in a multi-dimensional array where every row and column satisfies a parity check. While robust and conceptually simple, traditional decoding methods—such as Belief Propagation (BP) or Elias’s original serial decoding—often fail to reach optimal performance in the short-to-moderate blocklength regimes critical for modern low-latency communications.

This research bridges the gap between classic product codes and modern polar coding theory. By framing Single Parity-Check (SPC) product codes as a special case of multi-kernel polar codes, the authors demonstrate that recursive, likelihood-based decoding structures can significantly improve reliability.

The Multi-Kernel Polar Connection

The core theoretical contribution of this work is the proof 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). In this view, the inherent structure of the product code is redefined as a specific pattern of frozen bits within a larger, polar-like recursive transform.

Extracted figure from page 4 of Successive Cancellation Decoding of Single Parity-Check Product Codes: Analysis and Improved Decoding

As shown in Figure 1, the encoder $G^{[m]}$ is built recursively. This perspective allows the application of Successive Cancellation (SC) and Successive Cancellation List (SCL) decoding—techniques that have made polar codes a standard in 5G—to the domain of product codes.

Decoding Strategies

Successive Cancellation (SC) Decoding

Unlike traditional BP, which iterates over a graph, SC decoding processes bits sequentially. For each bit $u_i$, the decoder calculates a likelihood based on the channel outputs $y$ and the hard decisions made for all preceding bits $u_1, \dots, u_{i-1}$. This sequential dependency allows the decoder to use the "decisions" of previous bits to improve the likelihood estimates of the current one.

Successive cancellation decoding step for bit $u_3$, utilizing channel observations and previously decoded bits.

Figure 4 illustrates a single decoding step for bit $u_3$. The authors prove that on the Binary Erasure Channel (BEC), SC decoding is guaranteed to perform at least as well as, and often better than, Elias’s original 1954 decoding algorithm.

Successive Cancellation List (SCL) Decoding and CRC Concatenation

To further push performance toward the theoretical limits, the authors implement SCL decoding. This algorithm maintains a list of $L$ likely candidate paths through the decoding tree. To select the correct codeword from this list, the product code is concatenated with a high-rate outer Cyclic Redundancy Check (CRC). This "CRC-aided" approach, borrowed from 5G polar code standards, serves as a powerful equalizer for short blocklengths.

Key Results and Performance Analysis

The paper evaluates these methods through rigorous Monte Carlo simulations over Binary Erasure Channels (BEC) and Binary-Input Additive White Gaussian Noise (B-AWGN) channels. Key findings include:

  • Proximity to Theoretical Limits: Concatenated SPC product codes were shown to perform within 0.7 dB of the Random Coding Union (RCU) bound, the benchmark for absolute channel coding limits at finite lengths.
  • Outperforming 5G Standards: In specific short-blocklength scenarios (e.g., length 125), the SCL-decoded SPC product code outperformed the 5G-NR LDPC code (Base Graph 2) by approximately 0.6 dB.
  • SCL vs. BP: For a (125, 64) code, SCL decoding with a small list size ($L=4$) significantly outperformed BP decoding even after 100 iterations.

Conclusion and Future Work

While these codes excel in short-blocklength regimes, the authors note an "asymptotic trap": for certain infinite sequences of SPC product codes, the SC decoding threshold drops to zero as dimensions increase. This suggests that SPC product codes are best suited for "short and fat" dimensions rather than infinitely deep ones.

Future research may extend this multi-kernel polar framework to more complex component codes, such as Hamming codes, and further optimize the interleaver between the CRC and the product code to unlock additional coding gains.

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},
}
Figure