Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.13092 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910855309819904 |
|---|---|
| author | Chisnevski, Nir Tal, Ido Shamai, Shlomo |
| author_facet | Chisnevski, Nir Tal, Ido Shamai, Shlomo |
| contents | The min-sum approximation is widely used in the decoding of polar codes. Although it is a numerical approximation, hardly any penalties are incurred in practice. We give a theoretical justification for this. We consider the common case of a binary-input, memoryless, and symmetric channel, decoded using successive cancellation and the min-sum approximation. Under mild assumptions, we show the following. For the finite length case, we show how to exactly calculate the error probabilities of all synthetic (bit) channels in time $O(N^{1.585})$, where $N$ is the codeword length. This implies a code construction algorithm with the above complexity. For the asymptotic case, we develop two rate thresholds, denoted $R_{\mathrm{L}} = R_{\mathrm{L}}(λ)$ and $R_{\mathrm{U}} =R_{\mathrm{U}}(λ)$, where $λ(\cdot)$ is the labeler of the channel outputs (essentially, a quantizer). For any $0 < β< \frac{1}{2}$ and any code rate $R < R_{\mathrm{L}}$, there exists a family of polar codes with growing lengths such that their rates are at least $R$ and their error probabilities are at most $2^{-N^β}$. That is, strong polarization continues to hold under the min-sum approximation. Conversely, for code rates exceeding $R_{\mathrm{U}}$, the error probability approaches $1$ as the code-length increases, irrespective of which bits are frozen. We show that $0 < R_{\mathrm{L}} \leq R_{\mathrm{U}} \leq C$, where $C$ is the channel capacity. The last inequality is often strict, in which case the ramification of using the min-sum approximation is that we can no longer achieve capacity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13092 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Analytical Study of the Min-Sum Approximation for Polar Codes Chisnevski, Nir Tal, Ido Shamai, Shlomo Information Theory The min-sum approximation is widely used in the decoding of polar codes. Although it is a numerical approximation, hardly any penalties are incurred in practice. We give a theoretical justification for this. We consider the common case of a binary-input, memoryless, and symmetric channel, decoded using successive cancellation and the min-sum approximation. Under mild assumptions, we show the following. For the finite length case, we show how to exactly calculate the error probabilities of all synthetic (bit) channels in time $O(N^{1.585})$, where $N$ is the codeword length. This implies a code construction algorithm with the above complexity. For the asymptotic case, we develop two rate thresholds, denoted $R_{\mathrm{L}} = R_{\mathrm{L}}(λ)$ and $R_{\mathrm{U}} =R_{\mathrm{U}}(λ)$, where $λ(\cdot)$ is the labeler of the channel outputs (essentially, a quantizer). For any $0 < β< \frac{1}{2}$ and any code rate $R < R_{\mathrm{L}}$, there exists a family of polar codes with growing lengths such that their rates are at least $R$ and their error probabilities are at most $2^{-N^β}$. That is, strong polarization continues to hold under the min-sum approximation. Conversely, for code rates exceeding $R_{\mathrm{U}}$, the error probability approaches $1$ as the code-length increases, irrespective of which bits are frozen. We show that $0 < R_{\mathrm{L}} \leq R_{\mathrm{U}} \leq C$, where $C$ is the channel capacity. The last inequality is often strict, in which case the ramification of using the min-sum approximation is that we can no longer achieve capacity. |
| title | An Analytical Study of the Min-Sum Approximation for Polar Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2501.13092 |