On the Message Passing Efficiency of Polar and Low-Density Parity-Check Decoders

Dawei Yin, Yuan Li, Xianbin Wang, Jiajie Tong, Huazi Zhang, Jun Wang, Guanghui Wang, Jun Chen, Guiying Yan, Zhiming Ma, Wen Tong2022 · arXiv

Abstract: This study focuses on the efficiency of message-passing-based decoding algorithms for polar and low-density parity-check (LDPC) codes. Both successive cancellation (SC) and belief propagation (BP) decoding algorithms are studied in the message-passing framework. Counter-intuitively, SC decoding demonstrates the highest decoding efficiency, although it was considered a weak decoder in terms of error-correction performance. We analyze the complexity-performance tradeoff to dynamically track the decoding efficiency, where the complexity is measured by the number of messages passed (NMP), and the performance is measured by the statistical distance to the maximum a posteriori (MAP) estimate. This study offers a new insight into the contribution of each message passed in decoding, and compares various decoding algorithms on a message-by-message level. The analysis corroborates recent results on terabits-per-second polar SC decoders, and might shed light on better scheduling strategies.

Introduction

In the pursuit of 6G and Terabit-per-second (Tbps) throughput, the efficiency of channel decoders has become as critical as their raw error-correction performance. Traditional metrics like Signal-to-Noise Ratio (SNR) versus Bit Error Rate (BER) often fail to capture the computational "cost" of decoding. This paper addresses this gap by introducing a fine-grained framework to measure decoding efficiency, tracking the "Gap to Maximum A Posteriori" (GAP) against the "Number of Messages Passed" (NMP).

Methods and Framework

The researchers propose a two-dimensional paradigm to evaluate decoders independently of specific hardware implementations:

  • Complexity (X-axis): Measured by the Number of Messages Passed (NMP). This counts every individual message exchanged between variable and check nodes on a factor graph.
  • Performance (Y-axis): Measured by the Gap to Maximum A Posteriori (GAP). Utilizing Bethe free energy from statistical physics, this metric calculates how far an intermediate decoding state is from the theoretically optimal MAP result.

The study evaluates standard 5G New Radio (NR) Polar and LDPC codes under Additive White Gaussian Noise (AWGN) with BPSK modulation. The structural differences in their factor graphs, shown in Figure 4, are fundamental to their message-passing efficiency.

Factor graph representations for LDPC (left) and Polar (right) codes, highlighting the structural differences that impact message-passing efficiency.

Key Insights and Ideas

  • The SC Efficiency Paradox: Successive Cancellation (SC) for Polar codes emerges as the most efficient strategy. Despite having lower error-correction limits than Belief Propagation (BP), it reaches its maximum potential much faster and with far fewer messages. This explains the high throughput achieved by recent hardware implementations of SC decoders.
  • Polar BP’s Inefficiency: Running BP on a Polar factor graph is the least efficient method analyzed. Because the Polar factor graph is significantly denser than the sparse graph of LDPC, it requires orders of magnitude more messages to converge.
  • Scheduling is Everything: The order of message passing (scheduling policy) drastically alters efficiency. For LDPC codes, Layered BP is significantly more efficient than Flooding BP because it propagates information through the graph more effectively per message passed.

Key Results

The complexity-performance tradeoff is quantitatively demonstrated through 3D analysis of BER, complexity, and SNR. As shown in Figure 1, the efficiency of Polar SC and LDPC Layered BP can be tracked dynamically.

3D visualization of the Bit Error Rate (BER) performance relative to decoding complexity (NMP) and SNR for LDPC and Polar SC decoders.

For a Polar code of length $N=256$, Polar BP requires nearly 100 times more messages than Polar SC to reach a similar performance state. While LDPC BP is more efficient than Polar BP due to graph sparsity, it still lags behind the sheer efficiency of Polar SC. These insights led to the development of Successive-Searching BP (SSBP), a new scheduling algorithm for LDPC that achieves faster reductions in both GAP and Block Error Rate (BLER) compared to standard 5G scheduling.

Limitations and Future Work

While the GAP metric provides a powerful tool for analysis, it has limitations in the finite-length regime where MAP decoding is not error-free, which can lead to negative GAP values. Furthermore, the NMP metric does not easily translate to non-message-passing decoders such as Successive Cancellation List (SCL) or Ordered Statistics Decoders (OSD). Future work remains to establish a theoretical "speed limit" for decoding efficiency, analogous to the Shannon capacity for throughput.

Summary updated

Abstract

This study focuses on the efficiency of message-passing-based decoding algorithms for polar and low-density parity-check (LDPC) codes. Both successive cancellation (SC) and belief propagation (BP) decoding algorithms are studied {in} the message-passing framework. Counter-intuitively, SC decoding demonstrates the highest decoding efficiency, although it was considered a weak decoder {in terms of} error-correction performance. We analyze the complexity-performance tradeoff to dynamically track the decoding efficiency, where the complexity is measured by the number of messages passed (NMP), and the performance is measured by the statistical distance to the maximum a posteriori (MAP) estimate. This study offers a new insight into the contribution of each message passed in decoding, and compares various decoding algorithms on a message-by-message level. The analysis corroborates recent results on terabits-per-second polar SC decoders, and might shed light on better scheduling strategies.
BibTeX
@inproceedings{yin2022message,
  author = {Dawei Yin and Yuan Li and Xianbin Wang and Jiajie Tong and Huazi Zhang and Jun Wang and Guanghui Wang and Jun Chen and Guiying Yan and Zhiming Ma and Wen Tong},
  title = {{On the Message Passing Efficiency of Polar and Low-Density Parity-Check Decoders}},
  booktitle = {2022},
  year = {2022},
}
Figure