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

Recursive List Decoding for Reed-Muller Codes

Ilya I. Dumer, Kirill Shabunov

Published Mar 14, 2017• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1703.05304

Related papers

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

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 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 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 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 nlogn and corrects most error patterns of weight up to n(1/2-/spl epsiv/) given that /spl epsiv/ exceeds n/sup -1/2r/. This improves the asymptotic bounds known for decoding RM codes with nonexponential complexity. To evaluate decoding capability, we develop a probabilistic technique that disintegrates decoding into a sequence of recursive steps. Although dependent, subsequent outputs can be tightly evaluated under the assumption that all preceding decodings are correct. In turn, this allows us to employ second-order analysis and find the error weights for which the decoding error probability vanishes on the entire sequence of decoding steps as the code length n grows.

IEEE Transactions on Information Theory•May 1, 2004•98 citations

Permutation-based Decoding of Reed-Muller Codes in Binary Erasure Channel

Kirill Svyatoslavich Ivanov, Rudiger L. Urbanke

In this paper, we consider the problem of decoding Reed-Muller (RM) codes in binary erasure channel. We propose a novel algorithm, which exploits several techniques, such as list recursive (successive cancellation) decoding based on Plotkin decomposition, permutations of encoding factor graph as well as the properties of erasure channels.We show that with properly selected number of random permutations, this algorithm considerably outperforms straightforward list decoding while maintaining the same asymptotic complexity. This also means that near-MAP decoding can be achieved with lower complexity cost.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•15 citations
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.
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 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.
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.
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 nlogn and corrects most error patterns of weight up to n(1/2-/spl epsiv/) given that /spl epsiv/ exceeds n/sup -1/2r/. This improves the asymptotic bounds known for decoding RM codes with nonexponential complexity. To evaluate decoding capability, we develop a probabilistic technique that disintegrates decoding into a sequence of recursive steps. Although dependent, subsequent outputs can be tightly evaluated under the assumption that all preceding decodings are correct. In turn, this allows us to employ second-order analysis and find the error weights for which the decoding error probability vanishes on the entire sequence of decoding steps as the code length n grows.
In this paper, we consider the problem of decoding Reed-Muller (RM) codes in binary erasure channel. We propose a novel algorithm, which exploits several techniques, such as list recursive (successive cancellation) decoding based on Plotkin decomposition, permutations of encoding factor graph as well as the properties of erasure channels.We show that with properly selected number of random permutations, this algorithm considerably outperforms straightforward list decoding while maintaining the same asymptotic complexity. This also means that near-MAP decoding can be achieved with lower complexity cost.