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

IEEE International Symposium on Information Theory (ISIT)

Polar codes with a stepped boundary

Ilya I. Dumer

Published Jun 1, 2017• 8 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2017.8007002

Related papers

Polar codes with a stepped boundary

Ilya I. Dumer

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.$

arXiv:1702.04886•Feb 16, 2017•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

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

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

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

Preserving the Minimum Distance of Polar-Like Codes while Increasing the Information Length

Samet Gelincik, Philippe Mary, Anne Savard +1 more

Reed Muller (RM) codes are known for their good minimum distance. One can use their structure to construct polar-like codes with good distance properties by choosing the information set as the rows of the polarization matrix with the highest Hamming weight, instead of the most reliable synthetic channels. However, the information length options of RM codes are quite limited due to their specific structure. In this work, we present sufficient conditions to increase the information length by at least one bit for some underlying RM codes and in order to obtain pre-transformed polar-like codes with the same minimum distance than lower rate codes. Moreover, our findings are combined with the method presented in [1] to further reduce the number of minimum weight codewords. Numerical results show that the designed codes perform close to the meta-converse bound at short blocklengths and better than the polarized adjusted convolutional polar codes with the same parameters.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•2 citations
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 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.
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
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.
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.
Reed Muller (RM) codes are known for their good minimum distance. One can use their structure to construct polar-like codes with good distance properties by choosing the information set as the rows of the polarization matrix with the highest Hamming weight, instead of the most reliable synthetic channels. However, the information length options of RM codes are quite limited due to their specific structure. In this work, we present sufficient conditions to increase the information length by at least one bit for some underlying RM codes and in order to obtain pre-transformed polar-like codes with the same minimum distance than lower rate codes. Moreover, our findings are combined with the method presented in [1] to further reduce the number of minimum weight codewords. Numerical results show that the designed codes perform close to the meta-converse bound at short blocklengths and better than the polarized adjusted convolutional polar codes with the same parameters.