TL;DR
This paper introduces a novel "Successive Permutation" (SP) decoding scheme for Reed-Muller (RM) and polar codes. SP dynamically selects optimal factor graph permutations during decoding, significantly improving error correction performance for low-complexity successive-cancellation (SC) and SC-List (SCL) decoders without increasing memory requirements.
What Problem Does This Paper Address?
Modern wireless communication standards, like 5G, demand efficient channel coding schemes, particularly for short code lengths. Polar codes, chosen for 5G control channels, and Reed-Muller (RM) codes are known for their capacity-achieving potential. However, standard low-complexity decoding algorithms like Successive-Cancellation (SC) struggle to achieve satisfactory error correction performance, especially at shorter lengths. While more advanced techniques like SC-List (SCL) and even MAP decoding offer better performance, they come with increased complexity or are computationally intractable. Existing methods to improve performance using factor graph permutations often lead to prohibitively high decoding complexity due to the sheer number of possible permutations. This paper aims to bridge this gap by offering a way to leverage these permutations for better error correction without a significant computational overhead.
Methods
The core contribution is the Successive Permutation (SP) scheme. Instead of exhaustively trying all possible factor graph permutations (which can be astronomically numerous), SP intelligently selects permutations "on the fly" during the decoding process.
Here's how it works:
- Factor Graph Permutations: Both RM and polar codes can be represented using factor graphs. Permuting the "layers" or "bit indices" within these factor graphs creates different representations of the same code. The paper first establishes that the number of such permutations is much larger than previously thought (exceeding $n!$ for a code of length $2^n$).
- Successive Permutation (SP): The SP scheme operates layer by layer. At each layer, it evaluates a set of candidate permutations (specifically, cyclic shifts) and selects the one that yields the "most reliable" intermediate LLR (Log-Likelihood Ratio) values. This reliability is measured by the sum of absolute LLR values.
- Integration with SC/SCL: For SC decoding, SP is applied directly. For SCL decoding, SP is applied to each of the L parallel SC decoders within the SCL framework.
- RM vs. Polar Code Handling: A key insight is that permutations affect RM codes differently than polar codes. For RM codes, permutations don't alter the fundamental structure of information and frozen bits, leading to direct benefits. For polar codes, which are optimized for specific channels, applying SP to all sub-codes can be detrimental. Therefore, the paper proposes applying SP only to the RM sub-codes within a polar code structure, preserving the overall polar code's channel-optimized nature.
Datasets
Not discussed in the paper. The evaluation is based on simulated channel conditions (AWGN) and specific code parameters.
Key Insights and Ideas
- Vast Permutation Space: The paper highlights that the number of factor graph permutations for RM and polar codes is significantly larger than the $n!$ previously considered, stemming from permutations within sub-codes at each layer.
- "On-the-Fly" Optimization: The SP scheme's brilliance lies in its ability to dynamically discover beneficial permutations during decoding, avoiding the need to pre-compute or store all possibilities. This makes it practical.
- Differential Impact on RM and Polar Codes: The finding that permutations directly benefit RM codes (due to their structure) but require careful handling for polar codes (to avoid performance degradation) is crucial for practical application. This leads to a hybrid approach for polar codes.
- Memory Efficiency: A significant advantage is that SP does not increase the memory footprint of the decoders, a common drawback of permutation-based methods.
Key Results
The paper demonstrates significant performance improvements for both RM and polar codes using the SP scheme:
- RM Codes: For RM(128, 64) codes at a target Frame Error Rate (FER) of $10^{-4}$, SP provides up to 0.5 dB improvement for both SC (SPSC) and SCL (SPSCL) decoding. SPSCL(16) gets within 0.05 dB of the MAP lower bound.
- Polar Codes: For P(128, 64) codes (with an 11-bit CRC and constructed for 6 dB SNR), SP offers up to 0.1 dB improvement for SC (SPSC) and SCL (SPSCL) decoding at a target FER of $10^{-4}$. This improvement is smaller due to the selective application of SP to RM sub-codes.
Limitations and Future Work
- Complexity Overhead: While SP avoids the memory overhead of full permutation decoding, it does introduce some computational complexity. The paper mentions this adds a factor of $n$ to the SC complexity, which is still manageable for practical code lengths.
- Polar Code Construction Dependence: The effectiveness of SP for polar codes is shown to be dependent on the code's construction, specifically how many RM sub-codes it contains. Future work could explore more sophisticated methods for selecting which sub-codes to permute or how to adapt SP for polar codes constructed with different criteria.
- Channel Dependence: The paper focuses on AWGN channels. Extending the SP scheme to other channel models (e.g., fading channels) would be a valuable future direction.
- Generalization: Investigating the applicability of SP to other types of codes that also have factor graph representations could be a promising avenue.
Summary updated