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:2409.03700 · IEEE Transactions on Communications

Constituent Automorphism Decoding of Reed-Muller Codes

Yicheng Qu, Amir Tasbihi, Frank R. Kschischang

Published Jan 29, 2025• 4 citations
arXivHTMLPDF

Abstract

Automorphism-ensemble decoding is applied to the Plotkin constituents of Reed-Muller codes, resulting in a new soft-decision decoding algorithm with state-of-the-art performance versus complexity trade-offs.
DOI
10.1109/tcomm.2025.3535882

Related papers

Automorphism Ensemble Decoding of Reed–Muller Codes

Marvin Geiselhart, Ahmed Elkelesh, Moustafa Ebada +2 more

Reed–Muller (RM) codes are known for their good maximum likelihood (ML) performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a versatile decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) and may use any polar or RM decoder as constituent decoders. We provide extensive error-rate performance simulations for successive cancellation (SC)-, SC-list (SCL)- and belief propagation (BP)-based constituent decoders. We furthermore compare our results to existing decoding schemes and report a near-ML performance for the RM(3,7)-code (e.g., 0.04 dB away from the ML bound at BLER of 10−3) at a competitive computational cost. Moreover, we provide some insights into the automorphism subgroups of RM codes and SC decoding and, thereby, prove the theoretical limitations of this method with respect to polar codes.

arXiv:2012.07635•IEEE Transactions on Communications•Jul 21, 2021•93 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

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

Soft-In/Soft-Out Decoding of Reed-Muller-Codes based on the Plotkin-Construction

Armin Dammann

•Jan 1, 2002•0 citations

Soft-decision decoding of Reed-Muller codes: a simplified algorithm

Ilya I. Dumer

Soft-decision decoding is considered for general Reed-Muller (RM) codes of length n and distance d used over a memoryless channel. A recursive decoding algorithm is designed and its decoding threshold is derived for long RM codes. The algorithm has complexity of order nlnn and corrects most error patterns of the Euclidean weight of order radicn/lnn, instead of the decoding threshold radicd/2 of the bounded distance decoding. Also, for long RM codes of fixed rate R, the new algorithm increases 4/pi times the decoding threshold of its hard-decision counterpart

IEEE Transactions on Information Theory•Mar 1, 2006•59 citations
Reed–Muller (RM) codes are known for their good maximum likelihood (ML) performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a versatile decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) and may use any polar or RM decoder as constituent decoders. We provide extensive error-rate performance simulations for successive cancellation (SC)-, SC-list (SCL)- and belief propagation (BP)-based constituent decoders. We furthermore compare our results to existing decoding schemes and report a near-ML performance for the RM(3,7)-code (e.g., 0.04 dB away from the ML bound at BLER of 10−3) at a competitive computational cost. Moreover, we provide some insights into the automorphism subgroups of RM codes and SC decoding and, thereby, prove the theoretical limitations of this method with respect to polar codes.
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.
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 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.
Soft-decision decoding is considered for general Reed-Muller (RM) codes of length n and distance d used over a memoryless channel. A recursive decoding algorithm is designed and its decoding threshold is derived for long RM codes. The algorithm has complexity of order nlnn and corrects most error patterns of the Euclidean weight of order radicn/lnn, instead of the decoding threshold radicd/2 of the bounded distance decoding. Also, for long RM codes of fixed rate R, the new algorithm increases 4/pi times the decoding threshold of its hard-decision counterpart