TL;DR
This paper introduces symbol-decision successive cancellation list (SCL) decoders for polar codes, which process data in M-bit chunks instead of individual bits. This novel approach significantly boosts decoding throughput and offers a better trade-off between performance and complexity compared to existing bit-decision decoders, making polar codes more viable for high-speed applications.
What Problem Does This Paper Address?
Polar codes are a powerful class of error-correcting codes known for their ability to achieve channel capacity. However, their practical decoding, particularly for shorter code lengths, has been a challenge. Traditional successive cancellation (SC) and successive cancellation list (SCL) decoders operate on a bit-by-bit basis. While effective, this serial processing limits their throughput, making them unsuitable for high-speed communication systems. Existing methods to improve speed often come with increased complexity or performance degradation. This paper aims to bridge this gap by proposing a symbol-decision approach that processes M bits at a time, aiming for higher throughput without sacrificing error performance.
Methods
The core innovation lies in the symbol-decision decoding strategy. Instead of processing one bit at a time, the proposed decoders treat M bits as a single symbol. Key techniques include:
- Symbol-Based Recursive Channel Combination: A novel recursive method is introduced to efficiently calculate symbol-wise channel transition probabilities. This is crucial for enabling symbol-level decisions and is shown to be more computationally efficient than combining bit-wise probabilities. It also allows for hardware resource sharing with bit-wise calculations.
- Two-Stage List Pruning Network: For the SCL decoder, which maintains a list of candidate codewords, a two-stage pruning network is proposed. This network efficiently selects the most reliable paths from a potentially massive number of candidates (2<sup>ML</sup>), offering a flexible trade-off between error performance and decoder complexity.
- Pre-computation Memory-Saving (PCMS) Technique: To address the significant memory requirements of SCL decoders, especially with larger list sizes, a PCMS technique is developed. This method reduces memory usage by pre-computing and storing intermediate messages, leading to a notable memory saving (up to 23% in their examples).
- Area-Efficient Architecture: The paper presents a hardware architecture for the symbol-decision SCL decoder. This architecture reuses processing units for both bit- and symbol-based calculations and employs two scheduling schemes to optimize hardware sharing and reduce area.
Datasets
Not discussed in the paper. The paper focuses on algorithmic and architectural design and evaluates performance using simulated polar codes.
Key Insights and Ideas
- Symbol-Level Decoding is Key to Throughput: The fundamental insight is that processing data in M-bit chunks, rather than individual bits, is a direct path to significantly increasing decoding throughput.
- Recursive Channel Combination is Efficient: The proposed recursive method for calculating symbol-wise channel probabilities is not only effective but also computationally advantageous, outperforming simpler methods of combining bit-wise probabilities.
- List Pruning is Essential for Scalability: As the number of candidate paths in SCL decoding grows exponentially with symbol size (2<sup>ML</sup>), an efficient pruning mechanism is vital. The two-stage approach offers a practical solution.
- Memory is a Bottleneck, PCMS is a Solution: The memory footprint of SCL decoders is a major hurdle. The PCMS technique effectively mitigates this by intelligently storing intermediate results.
- Trade-offs are Manageable: The proposed methods allow for explicit control over the trade-offs between decoding speed, error performance, and hardware complexity, making the decoders adaptable to different application requirements.
Key Results
- Improved Area Efficiency: The symbol-decision SCL decoders consistently outperform existing state-of-the-art SCL decoders in terms of area efficiency. For example, their 4-bit symbol-decision SCL decoder achieved an area efficiency 1.51 times higher than a comparable bit-decision decoder.
- Higher Throughput: The symbol-decision approach leads to substantial throughput gains. For instance, a 4-bit symbol-decision SCL decoder achieved 259.2 Mb/s/mm², significantly higher than previous designs.
- Comparable Error Performance: For moderate symbol sizes (M=2, 4), the symbol-decision decoders achieve error performance comparable to their bit-decision counterparts. For larger symbol sizes (M=8), they even show slight improvements in Frame Error Rate (FER).
- Latency Reduction: The symbol-decision approach, combined with efficient architectures and scheduling, leads to reduced decoding latency. For example, an SDSCL-8 decoder with specific parameters achieved a latency of 1288 clock cycles.
- Memory Savings: The PCMS technique demonstrated significant memory savings, reducing the LL storage by 23% for a (1024, 4) polar code.
Limitations and Future Work
- Idealized Speed-Up Claims: The paper critiques claims of linear speed-up (M times faster) from prior work, arguing that practical implementations require extra cycles for channel probability calculation and list pruning, making such ideal speed-ups unrealistic.
- Performance Degradation with Aggressive Pruning: While the two-stage list pruning network offers complexity reduction, using a smaller parameter 'q' (for pruning) can lead to a slight performance degradation (e.g., 0.25 dB FER loss).
- LLR vs. LL Messages: The current designs use Log-Likelihood (LL) messages. The authors note that using Log-Likelihood Ratio (LLR) messages could further improve area efficiency due to reduced memory requirements.
- Impracticality for Very Large Symbols: For extremely large symbol sizes (e.g., M ≥ 16), building practical list pruning networks becomes challenging due to the exponential growth in candidate paths, potentially leading to huge hardware requirements and latency.
- Future Work: The paper suggests exploring LLR messages for even better area efficiency and acknowledges the need for further investigation into the optimal balance between symbol size, pruning parameters, and hardware complexity for various applications.
Summary updated