Abstract
Polar codes are essential for modern communication, yet their construction for non-binary channels remains computationally intensive. This paper introduces a novel upgrading algorithm that achieves the theoretically optimal power law error scaling for $q$-ary input channels. By decomposing the $q$-ary problem into a series of binary decisions and employing an efficient greedy-split approach, the proposed method significantly improves both approximation accuracy and computational speed compared to existing state-of-the-art techniques.
Introduction
Polar codes, a cornerstone of 5G technology, are celebrated for their ability to achieve channel capacity. However, the practical implementation of polar codes for non-binary and non-symmetric channels is hindered by the exponential growth of the output alphabet size during the construction of synthetic channels. To manage this complexity, researchers employ channel approximation techniques, specifically "upgrading" and "degrading" approximations, to bound the error probability. While efficient solutions exist for binary-input channels, achieving a tight approximation with a favorable "power law" for non-binary inputs has remained a significant challenge.
The Channel Approximation Challenge
In the construction of polar codes, a channel $W$ with a massive output alphabet is replaced by a quantized version $Q$ with a fixed, smaller alphabet size $L$. An "upgrading" approximation ensures that the quantized channel is functionally "better" than the original, providing a lower bound on the error probability. This is crucial for identifying reliable bit-channels during code construction. Previous methods for $q$-ary inputs either suffered from poor error scaling or prohibitive computational costs.
Methodology: One-Hot Decomposition
The core innovation of this work is the "one-hot" decomposition strategy. Rather than addressing the $q$-ary problem directly, the authors treat the $q$-ary input as a sequence of $q-1$ binary decisions. This allows the complex channel to be broken down into $q-1$ binary-input channels.
As shown in Figure 1, the process involves:
- Decomposition: Breaking the $q$-ary channel into $q-1$ binary components using auxiliary variables $Z_i$.
- Greedy-Split: Applying an enhanced version of the Tal-Vardy greedy-split algorithm to each binary channel to maximize mutual information within a fixed alphabet budget $\Lambda$.
- Recombination: Merging the binary results back into a single $q$-ary upgraded channel through functions $f_i$.
- Efficient Marginalization: Utilizing the inherent mathematical sparsity of the joint distribution to compute the final channel without exponential complexity.
Key Results and Theoretical Insights
The primary theoretical contribution is the proof that this algorithm achieves the optimal power law. The approximation error scales as $O(L^{-2/(|X|-1)})$, where $|X|$ is the input alphabet size. This represents the fastest possible convergence rate for channel quantization.
Empirical evaluations on "hard" synthetic channels and practical polar code scenarios confirm these findings. In log-log plots of error versus alphabet size, the one-hot upgrading algorithm demonstrates a significantly steeper slope than previous benchmarks. Furthermore, in code construction tests, the algorithm identified 68 high-reliability indices for a specific non-symmetric distribution, whereas the previous standard identified only 8.
Conclusion
This research provides a robust and efficient framework for constructing polar codes over non-binary channels. By reducing the $q$-ary problem to a series of binary approximations, the authors achieve optimal scaling and practical efficiency. While the complexity includes a $2^{q-1}$ term, making it most suitable for small to moderate input alphabets, it remains the first method to reach the theoretical limit of approximation accuracy for non-binary inputs.
Summary updated