Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1702.04886

Polar codes with a stepped boundary

Ilya I. Dumer

Published Feb 16, 2017• 1 citation
arXivHTMLPDF

Abstract

We consider explicit polar constructions of blocklength $n\rightarrow\infty$ for the two extreme cases of code rates $R\rightarrow1$ and $R\rightarrow0.$ For code rates $R\rightarrow1,$ we design codes with complexity order of $n\log n$ in code construction, encoding, and decoding. These codes achieve the vanishing output bit error rates on the binary symmetric channels with any transition error probability $p\rightarrow 0$ and perform this task with a substantially smaller redundancy $(1-R)n$ than do other known high-rate codes, such as BCH codes or Reed-Muller (RM). We then extend our design to the low-rate codes that achieve the vanishing output error rates with the same complexity order of $n\log n$ and an asymptotically optimal code rate $R\rightarrow0$ for the case of $p\rightarrow1/2.$

DOI
10.48550/arxiv.1702.04886

Related papers

Polar codes with a stepped boundary

Ilya I. Dumer

We design polar codes of blocklength n→∞ and code rate R →1 that achieve the vanishing output error rates on the binary symmetric channels with transition error probability p → 0. These codes have a substantially smaller redundancy order (1 - R)n than do other known high-rate codes, such as Reed-Muller (RM) or BCH codes. The construction is explicit and has complexity of order nlog n. We also design asymptotically optimal low-rate codes that achieve the vanishing output error rates if p → 1/2.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•8 citations

Mixed polarized constructions

Ilya I. Dumer

We consider Plotkin-type constructions that perform a multi-step recursive decomposition of a given code into the shorter codes and are similar to polar and Reed-Muller (RM) codes. However, we end this decomposition process at the various short codes instead of the single information bits used as end nodes in polar design. We also employ maximum likelihood (ML) decoding of the end codes. Such a design can reduce the output error rates of polarised constructions on the moderate blocklengths. We also analyse the complexity-performance trade-offs in order to optimise code design.

International Journal of Information and Coding Theory•Jan 1, 2015•1 citation

On polylogarithmic decoding complexity for reed-muller codes

Ilya I. Dumer

For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•1 citation

Decoding of Reed-Muller codes with polylogarithmic complexity

Ilya I. Dumer

Code transmission is considered over a binary symmetric (BS) channel whose bit error probability is arbitrarily close to 1/2. New recursive decoding algorithms are designed for Reed-Muller (RM) codes of growing length 2m and fixed order r. The algorithms retrieve all information with a vanishing error probability and polylogarithmic complexity of order mr+1.

•Jan 5, 2004•2 citations

An Analytical Study of the Min-Sum Approximation for Polar Codes

Nir Chisnevski, Ido Tal, Shlomo Shitz Shamai

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$\mathcal{O}\left(N^{1.585}\right)$, 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}}(\lambda)$and$R_{\mathrm{U}}=R_{\mathrm{U}}(\lambda)$, where$\lambda(\cdot)$is the labeler of the channel outputs (essentially, a quantizer). For any$0<\beta<\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^{\beta}}$. 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.

arXiv:2501.13092•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•0 citations

Robust decoding schemes for polar coding over compound channels

Mine Alsan, Vincent Y. F. Tan

We consider the problem of designing robust and low complexity decoding schemes for polar coding over a given finite class of channels. We propose two schemes based on multiple runs of the polar successive cancellation decoder, where at each run a different metric adapted to a channel in the class is used in the decoder's decision procedure. The first scheme is a modified polar coding scheme which accommodates Cyclic Redundancy Check bits to help the decoder eliminate the estimates that do not pass the test. We show that this scheme achieves the symmetric capacity of the channel with a vanishing rate loss of O(1√N), where N is the blocklength of the code. The second scheme involves a polar decoding algorithm which implements a generalized likelihood ratio test. We show that over classes of channels which satisfy certain mild conditions, this scheme achieves the symmetric capacity of the channel. The analyses reveal that the decay of the error probability of both schemes is exponential in the square root of the blocklength, which is similar to the polar successive cancellation decoder operating with the knowledge of the true channel. Finally, we compare the schemes in terms of their performances and complexity, and discuss the extension to infinite classes of channels.

IEEE Information Theory Workshop (ITW)•Nov 1, 2017•0 citations
We consider explicit polar constructions of blocklength n→∞n\rightarrow\inftyn→∞ for the two extreme cases of code rates R→1R\rightarrow1R→1 and R→0.R\rightarrow0.R→0. For code rates R→1,R\rightarrow1,R→1, we design codes with complexity order of nlog⁡nn\log nnlogn in code construction, encoding, and decoding. These codes achieve the vanishing output bit error rates on the binary symmetric channels with any transition error probability p→0p\rightarrow 0p→0 and perform this task with a substantially smaller redundancy (1−R)n(1-R)n(1−R)n than do other known high-rate codes, such as BCH codes or Reed-Muller (RM). We then extend our design to the low-rate codes that achieve the vanishing output error rates with the same complexity order of nlog⁡nn\log nnlogn and an asymptotically optimal code rate R→0R\rightarrow0R→0 for the case of p→1/2.p\rightarrow1/2.p→1/2.
We design polar codes of blocklength n→∞ and code rate R →1 that achieve the vanishing output error rates on the binary symmetric channels with transition error probability p → 0. These codes have a substantially smaller redundancy order (1 - R)n than do other known high-rate codes, such as Reed-Muller (RM) or BCH codes. The construction is explicit and has complexity of order nlog n. We also design asymptotically optimal low-rate codes that achieve the vanishing output error rates if p → 1/2.
We consider Plotkin-type constructions that perform a multi-step recursive decomposition of a given code into the shorter codes and are similar to polar and Reed-Muller (RM) codes. However, we end this decomposition process at the various short codes instead of the single information bits used as end nodes in polar design. We also employ maximum likelihood (ML) decoding of the end codes. Such a design can reduce the output error rates of polarised constructions on the moderate blocklengths. We also analyse the complexity-performance trade-offs in order to optimise code design.
For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2
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 timeO(N1.585)\mathcal{O}\left(N^{1.585}\right)O(N1.585), whereNNNis the codeword length. This implies a code construction algorithm with the above complexity. For the asymptotic case, we develop two rate thresholds, denotedRL=RL(λ)R_{\mathrm{L}}=R_{\mathrm{L}}(\lambda)RL​=RL​(λ)andRU=RU(λ)R_{\mathrm{U}}=R_{\mathrm{U}}(\lambda)RU​=RU​(λ), whereλ(⋅)\lambda(\cdot)λ(⋅)is the labeler of the channel outputs (essentially, a quantizer). For any0<β<120<\beta<\frac{1}{2}0<β<21​and any code rateR<RLR<R_{\mathrm{L}}R<RL​, there exists a family of polar codes with growing lengths such that their rates are at leastRRRand their error probabilities are at most2−Nβ2^{-N^{\beta}}2−Nβ. That is, strong polarization continues to hold under the min-sum approximation. Conversely, for code rates exceedingRUR_{\mathrm{U}}RU​, the error probability approaches 1 as the code-length increases, irrespective of which bits are frozen. We show that0<RL≤RU≤C0<R_{\mathrm{L}} \leq R_{\mathrm{U}} \leq C0<RL​≤RU​≤C, whereCCCis 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.
We consider the problem of designing robust and low complexity decoding schemes for polar coding over a given finite class of channels. We propose two schemes based on multiple runs of the polar successive cancellation decoder, where at each run a different metric adapted to a channel in the class is used in the decoder's decision procedure. The first scheme is a modified polar coding scheme which accommodates Cyclic Redundancy Check bits to help the decoder eliminate the estimates that do not pass the test. We show that this scheme achieves the symmetric capacity of the channel with a vanishing rate loss of O(1√N), where N is the blocklength of the code. The second scheme involves a polar decoding algorithm which implements a generalized likelihood ratio test. We show that over classes of channels which satisfy certain mild conditions, this scheme achieves the symmetric capacity of the channel. The analyses reveal that the decay of the error probability of both schemes is exponential in the square root of the blocklength, which is similar to the polar successive cancellation decoder operating with the knowledge of the true channel. Finally, we compare the schemes in terms of their performances and complexity, and discuss the extension to infinite classes of channels.