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)

Simple MAP decoding of first order Reed-Muller and Hamming codes

Alexei Ashikhmin, Simon N. Litsyn

Published Mar 2, 2004• 6 citations
Publisher

Abstract

We present new MAP decoding algorithms for first order Reed-Muller and Hamming codes. The proposed algorithms have complexities proportional to n/spl times/log/sub 2/(n), where n is the code length.
DOI
10.1109/itw.2003.1216684

Related papers

Simple MAP Decoding of First-Order Reed–Muller and Hamming Codes

Alexei Ashikhmin, Simon N. Litsyn

A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.

IEEE Transactions on Information Theory•Jul 27, 2004•55 citations

Simple MAP decoding of first order Reed-Muller and Hamming codes

Alexei Ashikhmin, Simon N. Litsyn

In this paper we are interested in MAP decoding of first order Reed-Muller and Hamming codes. A MAP decoder of a linear code computes a-posteriori probabilities for all values of each transmitted symbol and chooses the maximum one. The standard way of doing this is the BCJR algorithm. This algorithm is based on a trellis representation of a code. Such a representation allows one to reduce the complexity of MAP decoding, though it still remains exponential. The BCJR algorithm for binary first order Reed-Muller and Hamming codes has complexity proportional to n/sup 2/, where n is the code length. In this paper we propose a new MAP decoding algorithm for both RM-1 and Hamming codes with complexity proportional to nlog/sub 2/n.

IEEE Convention of Electrical and Electronics Engineers in Israel•Jun 26, 2003•1 citation

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

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

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
A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.
In this paper we are interested in MAP decoding of first order Reed-Muller and Hamming codes. A MAP decoder of a linear code computes a-posteriori probabilities for all values of each transmitted symbol and chooses the maximum one. The standard way of doing this is the BCJR algorithm. This algorithm is based on a trellis representation of a code. Such a representation allows one to reduce the complexity of MAP decoding, though it still remains exponential. The BCJR algorithm for binary first order Reed-Muller and Hamming codes has complexity proportional to n/sup 2/, where n is the code length. In this paper we propose a new MAP decoding algorithm for both RM-1 and Hamming codes with complexity proportional to nlog/sub 2/n.
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 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.