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

Reed-Muller Codes: Spherically-Punctured Codes and Decoding Algorithms

Olga Kapralova

Published Jan 1, 2013• 1 citation
OpenAlex

Abstract

Reed-Muller (RM) codes are classical codes that have enjoyed unabated interest since their introduction in 1954 due to their simple recursive structure and low-complexity decoding. The main goal of the thesis is to develop new coding techniques that can improve the performance of RM codes. In this work, we wish to keep the recursive low-complexity structure of RM codes while extending the sets of possible parameters and decoding algorithms. We address this task using two different methods. First, we consider new code constructions that extend code parameters using puncturing. Second, we design new decoding algorithms that repeatedly use the gradient properties of the classic recursive structure to improve code performance of RM codes. In the first part of the thesis, we propose a new class of codes that enjoy the recursive structure of RM codes, but reduce the exponential length of RM codes to a polynomial in m. These codes are obtained by puncturing classical RM codes, i.e. by restricting binary RM codes to small subsets of their positions. We study new recursive properties of these codes and analyze their parameters. In the second part of the thesis we develop new decoding algorithms for binary RM codes of second order that achieve near optimal performance for short and moderate code lengths. RM codes enjoy some simple decoding procedures; however, these algorithms fall short of optimal performance on moderate block lengths. We propose a suboptimal algorithm that reduces the complexity of maximum-likelihood decoding from super-polynomial order O(n(m+1)/2) to polynomial order O(mn2). At the same time, our numerical simulations show that the new algorithm performs very closely to its maximum-likelihood counterpart for blocks of up to several thousand bits.

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

Recursive List Decoding for Reed-Muller Codes

Ilya I. Dumer, Kirill Shabunov

We consider recursive decoding for Reed-Muller (RM) codes and their subcodes. Two new recursive techniques are described. We analyze asymptotic properties of these algorithms and show that they substantially outperform other decoding algorithms with nonexponential complexity known for RM codes. Decoding performance is further enhanced by using intermediate code lists and permutation procedures. For moderate lengths up to 512, near-optimum decoding with feasible complexity is obtained.

arXiv:1703.05304•Mar 14, 2017•2 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

Recursive Projection-Aggregation Decoding of Reed-Muller Codes

Min Ye, Emmanuel A. Abbe

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

IEEE Transactions on Information Theory•Mar 3, 2020•79 citations

Recursive projection-aggregation decoding of Reed-Muller codes

Min Ye, Emmanuel A. Abbe

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms based on list-decoding algorithms and code concatenation. We run our main algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) and low code rate (≤ 0.5) regime. Simulation results show that the new algorithm not only outperforms the previous decoding algorithms for RM codes, it also outperforms the optimal decoder for polar codes (SCL+CRC) with the same parameters by a wide margin. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•22 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
Reed-Muller (RM) codes are classical codes that have enjoyed unabated interest since their introduction in 1954 due to their simple recursive structure and low-complexity decoding. The main goal of the thesis is to develop new coding techniques that can improve the performance of RM codes. In this work, we wish to keep the recursive low-complexity structure of RM codes while extending the sets of possible parameters and decoding algorithms. We address this task using two different methods. First, we consider new code constructions that extend code parameters using puncturing. Second, we design new decoding algorithms that repeatedly use the gradient properties of the classic recursive structure to improve code performance of RM codes. In the first part of the thesis, we propose a new class of codes that enjoy the recursive structure of RM codes, but reduce the exponential length of RM codes to a polynomial in m. These codes are obtained by puncturing classical RM codes, i.e. by restricting binary RM codes to small subsets of their positions. We study new recursive properties of these codes and analyze their parameters. In the second part of the thesis we develop new decoding algorithms for binary RM codes of second order that achieve near optimal performance for short and moderate code lengths. RM codes enjoy some simple decoding procedures; however, these algorithms fall short of optimal performance on moderate block lengths. We propose a suboptimal algorithm that reduces the complexity of maximum-likelihood decoding from super-polynomial order O(n(m+1)/2) to polynomial order O(mn2). At the same time, our numerical simulations show that the new algorithm performs very closely to its maximum-likelihood counterpart for blocks of up to several thousand bits.
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.
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.
We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.
We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms based on list-decoding algorithms and code concatenation. We run our main algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) and low code rate (≤ 0.5) regime. Simulation results show that the new algorithm not only outperforms the previous decoding algorithms for RM codes, it also outperforms the optimal decoder for polar codes (SCL+CRC) with the same parameters by a wide margin. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.
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.