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

International Journal of Information and Coding Theory

Mixed polarized constructions

Ilya I. Dumer

Published Jan 1, 2015• 1 citation
Publisher

Abstract

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.

DOI
10.1504/ijicot.2015.072611

Related papers

Recursive decoding of Reed-Muller codes

Ilya I. Dumer, Kirill Shabunov

We use the Plotkin (u,u+v)-construction for general Reed-Muller codes (m,r) and relegate decoding to the two constituent RM codes. First, we use the better protected code (m-1,r-1) to find a subblock v. Then we proceed with the block u from the code (m-l,r). We repeat this recursion on both halves and recalculate the reliabilities of the received symbols. In the end, we perform maximum likelihood decoding on the biorthogonal codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•20 citations

Multi-Step Structure of Reed-Muller Codes

Junyu Ren, Guanghui Wang, Guiying Yan

Currently, many low-complexity decoding algorithms for Reed-Muller (RM) codes utilize the Plotkin structure of RM codes to decompose them into shorter RM subcodes for decoding. This study reveals a key relationship among RM subcodes, demonstrating that specific subcodes can generate all subcodes. Furthermore, we identify conditions where subcodes are inherently free of 4-cycles and 6-cycles structures. Building upon these insights, we modified existing well-known algorithms for RM codes, achieving similar error-correction performance with significantly lower complexity by requiring fewer subcode decodings.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

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

Recursive Decoding of Reed-Muller Codes Starting With the Higher-Rate Constituent Code

Mikhail Kamenev

Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length$(\leq 256)$RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length$2^{m}$and order$m-3$with reasonable complexity.

arXiv:2101.11328•IEEE Transactions on Information Theory•Jul 29, 2022•5 citations

Recursive decoding of Reed-Muller codes

Ilya I. Dumer

New soft- and hard decision decoding algorithms are presented for general Reed-Muller codes $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ of length $2^{m}$ and distance $2^{m-r}$. We use Plotkin $(u,u+v)$ construction and decompose code $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ onto subblocks $u\in\left\{\genfrac{}{}{0pt}{}{m-1}{r}\right\} $ and $v\in\left\{\genfrac{}{}{0pt}{}{m-1}{r-1}\right\} .$ In decoding, we first try to find a subblock $v$ from the better protected code and then proceed with the block $u$. The likelihoods of the received symbols are recalculated in a way similar to belief propagation. Thus, decoding is relegated to the two constituent codes. We repeat this recursion and execute decoding only at the end nodes $\left\{\genfrac{}{}{0pt}{}{j}{1}\right\} $ and $\left\{\genfrac{}{}{0pt}{}{j}{j-1}\right\} $. The overall complexity has low order of $n\log n.$ It is shown that this decoding substantially outperforms other algorithms of polynomial complexity known for RM codes. In particular, for medium and high code rates, the algorithm corrects most error patterns of weight $d\ln d/2.$

arXiv:1703.05303•Mar 14, 2017•7 citations

Soft-decision decoding of Reed-Muller codes: recursive lists

Ilya I. Dumer, Kirill Shabunov

Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes

arXiv:1703.05305•IEEE Transactions on Information Theory•Mar 1, 2006•161 citations
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.
Currently, many low-complexity decoding algorithms for Reed-Muller (RM) codes utilize the Plotkin structure of RM codes to decompose them into shorter RM subcodes for decoding. This study reveals a key relationship among RM subcodes, demonstrating that specific subcodes can generate all subcodes. Furthermore, we identify conditions where subcodes are inherently free of 4-cycles and 6-cycles structures. Building upon these insights, we modified existing well-known algorithms for RM codes, achieving similar error-correction performance with significantly lower complexity by requiring fewer subcode decodings.
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.
Recursive list decoding of Reed-Muller (RM) codes, with moderate list size, is known to approach maximum-likelihood (ML) performance of short length(≤256)(\leq 256)(≤256)RM codes. Recursive decoding employs the Plotkin construction to split the original code into two shorter RM codes with different rates. In contrast to the standard approach which decodes the lower-rate code first, the method in this paper decodes the higher-rate code first. This modification enables an efficient permutation-based decoding technique, with permutations being selected on the fly from the automorphism group of the code using soft information from a channel. Simulation results show that the error-rate performance of the proposed algorithms, enhanced by a permutation selection technique, is close to that of the automorphism-based recursive decoding algorithm with similar complexity for short RM codes, while our decoders perform better for longer RM codes. In particular, it is demonstrated that the proposed algorithms achieve near-ML performance for short RM codes and for RM codes of length2m2^{m}2mand orderm−3m-3m−3with reasonable complexity.
New soft- and hard decision decoding algorithms are presented for general Reed-Muller codes $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ of length 2m2^{m}2m and distance 2m−r2^{m-r}2m−r. We use Plotkin (u,u+v)(u,u+v)(u,u+v) construction and decompose code $\left\{\genfrac{}{}{0pt}{}{m}{r}\right\} $ onto subblocks $u\in\left\{\genfrac{}{}{0pt}{}{m-1}{r}\right\} $ and v∈{m−1r−1}.v\in\left\{\genfrac{}{}{0pt}{}{m-1}{r-1}\right\} .v∈{r−1m−1​}. In decoding, we first try to find a subblock vvv from the better protected code and then proceed with the block uuu. The likelihoods of the received symbols are recalculated in a way similar to belief propagation. Thus, decoding is relegated to the two constituent codes. We repeat this recursion and execute decoding only at the end nodes $\left\{\genfrac{}{}{0pt}{}{j}{1}\right\} $ and $\left\{\genfrac{}{}{0pt}{}{j}{j-1}\right\} $. The overall complexity has low order of nlog⁡n.n\log n.nlogn. It is shown that this decoding substantially outperforms other algorithms of polynomial complexity known for RM codes. In particular, for medium and high code rates, the algorithm corrects most error patterns of weight dln⁡d/2.d\ln d/2.dlnd/2.
Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes