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/CIC International Conference on Communications in China (ICCC)

Partial Superposition Reed-Muller Codes

Weiye Ren, Wenyi Zhang

Published Aug 10, 2025• 0 citations
Publisher

Abstract

Reed-Muller (RM) codes can be constructed by Plotkin ($u, u \oplus v$) construction. When recursively decoding RM codes based on Plotkin construction, the superposition of component codes u on v acts as interference to the decoding of v, and it has hence been pointed out in the literature that the decoding error is dominated by v. Therefore, in this study we propose a variant of RM codes, leveraging the idea of partial superposition in Plotkin construction. Specifically, only a subset of the bits in u is superposed on v. We call the resulting codes Partial Superposition RM (PS-RM) codes. A superposition pattern design based on row weights of generator matrix is provided. Regarding decoding, we modify Dumer’s recursive list decoding algorithm and Constituent Automorphism Decoding (CAD) algorithm, to render them applicable to PS-RM codes. Simulation results show that the idea of partial superposition leads to evident performance improvements over RM codes, particularly for long code lengths and low/medium Signal-toNoise Ratios (SNRs). We remark that the performance gains of the proposed PS-RM codes are achieved without increasing complexity.

DOI
10.1109/iccc65529.2025.11149327

Related papers

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

Decoding of Reed-Muller Codes Starting With a Higher-Rate Constituent Code.

Mikhail Kamenev

List versions of recursive decoding are known to approach maximum-likelihood (ML) performance for the short length Reed-Muller (RM) codes. The recursive decoder employs the Plotkin construction to split the original code into two shorter RM codes, with a lower-rate RM code being decoded first. In this paper, we consider non-iterative soft-input decoders for RM codes that, unlike recursive decoding, start decoding with a higher-rate constituent code. Although the error-rate performance of these algorithms is limited, it can be significantly improved by applying permutations from the automorphism group of the code, with permutations being selected on the fly based on 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 length $(\leq 256)$ 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 RM codes of length $2^m$ and order $m - 3$ with reasonable complexity.

•Nov 28, 2021•0 citations

Recursive Decoding and Its Performance for Low-Rate Reed-Muller Codes

Ilya I. Dumer

Recursive decoding techniques are considered for Reed-Muller (RM) codes of growing length $n$ and fixed order $r.$ An algorithm is designed that has complexity of order $n\log n$ and corrects most error patterns of weight up to $n(1/2-\varepsilon)$ given that $\varepsilon$ exceeds $n^{-1/2^{r}}.$ This improves the asymptotic bounds known for decoding RM codes with nonexponential complexity.

arXiv:1703.05306•Mar 14, 2017•0 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•4 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

IEEE Transactions on Information Theory•Mar 1, 2006•163 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•Mar 14, 2017•0 citations
Reed-Muller (RM) codes can be constructed by Plotkin (u,u⊕vu, u \oplus vu,u⊕v) construction. When recursively decoding RM codes based on Plotkin construction, the superposition of component codes u on v acts as interference to the decoding of v, and it has hence been pointed out in the literature that the decoding error is dominated by v. Therefore, in this study we propose a variant of RM codes, leveraging the idea of partial superposition in Plotkin construction. Specifically, only a subset of the bits in u is superposed on v. We call the resulting codes Partial Superposition RM (PS-RM) codes. A superposition pattern design based on row weights of generator matrix is provided. Regarding decoding, we modify Dumer’s recursive list decoding algorithm and Constituent Automorphism Decoding (CAD) algorithm, to render them applicable to PS-RM codes. Simulation results show that the idea of partial superposition leads to evident performance improvements over RM codes, particularly for long code lengths and low/medium Signal-toNoise Ratios (SNRs). We remark that the performance gains of the proposed PS-RM codes are achieved without increasing complexity.
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.
List versions of recursive decoding are known to approach maximum-likelihood (ML) performance for the short length Reed-Muller (RM) codes. The recursive decoder employs the Plotkin construction to split the original code into two shorter RM codes, with a lower-rate RM code being decoded first. In this paper, we consider non-iterative soft-input decoders for RM codes that, unlike recursive decoding, start decoding with a higher-rate constituent code. Although the error-rate performance of these algorithms is limited, it can be significantly improved by applying permutations from the automorphism group of the code, with permutations being selected on the fly based on 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 length (≤256)(\leq 256)(≤256) 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 RM codes of length 2m2^m2m and order m−3m - 3m−3 with reasonable complexity.
Recursive decoding techniques are considered for Reed-Muller (RM) codes of growing length nnn and fixed order r.r.r. An algorithm is designed that has complexity of order nlog⁡nn\log nnlogn and corrects most error patterns of weight up to n(1/2−ε)n(1/2-\varepsilon)n(1/2−ε) given that ε\varepsilonε exceeds n−1/2r.n^{-1/2^{r}}.n−1/2r. This improves the asymptotic bounds known for decoding RM codes with nonexponential 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
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.