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 Information Theory Workshop (ITW)

A survey of reed-muller codes from polar coding perspective

Erdal Arıkan

Published Jan 1, 2010• 58 citations
Publisher

Abstract

A survey of Reed-Muller (RM) coding is given with the goal of establishing a continuity between RM codes and polar codes. The focus is mainly on recursive decoding methods for RM codes and other ideas that are most relevant to polar coding.
DOI
10.1109/itwksps.2010.5503223

Related papers

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

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

Olga Kapralova

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.

•Jan 1, 2013•1 citation

Recursive error correction for general Reed-Muller codes

DumerIlya, ShabunovKirill

Reed-Muller (RM) codes of growing length n and distance d are considered over a binary symmetric channel. A recursive decoding algorithm is designed that has complexity of order nlogn and corrects ...

Discrete Applied Mathematics•Feb 1, 2006•1 citation

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

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