Successive Cancellation Priority Decoding of Polar Codes

Di Guan, Kai Niu, Chao Dong, Ping ZhangIEEE Access 2019 · DOI

Abstract

Polar codes are a cornerstone of 5G communications, providing the first provable method to achieve channel capacity. However, achieving high accuracy at short-to-medium code lengths typically requires Successive Cancellation List (SCL) decoding, which is computationally intensive due to its breadth-first search nature. This paper introduces Successive Cancellation Priority (SCP) decoding, a priority-first alternative. SCP is mathematically equivalent to SCL in error performance but significantly reduces average time complexity by avoiding redundant path calculations. The proposed decoder utilizes a trellis structure for efficient memory management and a Quantized Priority Queue (QPQ) to streamline path selection.

Introduction

Since their introduction by Erdal Arıkan in 2009, polar codes have become vital for modern wireless standards. While Successive Cancellation (SC) decoding is efficient for long codes, it performs poorly on the short-to-medium lengths common in 5G. Successive Cancellation List (SCL) decoding improves performance by tracking $L$ candidate paths, but its breadth-first approach results in high computational overhead, calculating metrics for all paths even when many are unlikely to be correct. Alternative "Stack" decoders (SCS) reduce time but suffer from high memory requirements. SCP decoding is proposed as a "middle way," offering the accuracy of SCL with the efficiency of a targeted search.

Methodology

The Successive Cancellation Priority (SCP) decoder is built upon two primary architectural components: a priority-first search mechanism and a trellis-based data structure.

Priority-First Search and the Quantized Priority Queue

Unlike the breadth-first search of SCL, SCP employs a priority-first search. It utilizes a priority queue to always extend the most reliable candidate path first. To optimize hardware implementation, the authors introduced the Quantized Priority Queue (QPQ). Standard priority queues require $O(PN)$ sorting operations for insertions. The QPQ uses uniform quantization of path metrics combined with a circular buffer to convert these comparisons into $O(1)$ indexing operations.

Priority-First Search Tree and Queue

Trellis Structure and Memory Management

To avoid the memory explosion typical of Stack decoding, SCP uses a trellis structure to store intermediate Log-Likelihood Ratio (LLR) and Hard Decision (HD) data. This allows the decoder to backtrack and retrieve necessary information for path extension without needing to store every possible path in its entirety.

Trellis Structure for Memory Efficiency

Evaluation and Results

The SCP algorithm was evaluated using simulated Binary-Input Additive White Gaussian Noise (BI-AWGN) channels with polar codes of length $N=1024$ and rate $R=0.5$, constructed via the Gaussian Approximation method.

Key findings include:

  • Functional Equivalence: Numerical simulations confirm that the Block Error Rate (BLER) of SCP is identical to SCL, proving that SCP identifies the same optimal path without approximation loss.
  • SNR-Adaptive Complexity: SCP's complexity scales with signal quality. In high Signal-to-Noise Ratio (SNR) regimes (above 3.0 dB), the average complexity drops significantly, approaching that of basic SC decoding, whereas SCL complexity remains constant.
  • Efficiency Gains: The QPQ eliminates the need for sorting comparisons, providing a massive reduction in logic operations for path selection, particularly as the search width $P$ increases.

Conclusion

SCP decoding offers a compelling alternative to SCL for polar codes, providing identical error correction performance with significantly lower average computational complexity. While the priority-first approach introduces variable decoding latency—a potential challenge for jitter-sensitive hardware—the integration of a trellis structure and the QPQ makes it a highly efficient solution for 5G communication systems. Future work will focus on full FPGA/ASIC implementation and optimizing quantization parameters to maintain performance across diverse channel conditions.

Summary updated

BibTeX
@article{guan2019successive,
  author = {Di Guan and Kai Niu and Chao Dong and Ping Zhang},
  title = {{Successive Cancellation Priority Decoding of Polar Codes}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2890838},
}
Figure