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 Convention of Electrical and Electronics Engineers in Israel

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

Alexei Ashikhmin, Simon N. Litsyn

Published Jun 26, 2003• 1 citation
Publisher

Abstract

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.

DOI
10.1109/eeei.2002.1178368

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

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.

IEEE Information Theory Workshop (ITW)•Mar 2, 2004•6 citations

On recursive decoding with sublinear complexity for Reed-Muller codes

Ilya I. Dumer

Reed-Muller (RM) codes (m, r) of length 2/sup m/ are considered on a binary symmetric (BS) channel with high crossover error probability 1/2 -/spl epsiv/. For an arbitrarily small /spl epsiv/>0, new recursive decoding algorithms are designed that retrieve all information bits of RM codes of fixed order r with a vanishing error probability and sublinear complexity of order O(m/sup r+1/). The algorithms utilize a vanishing fraction of the received symbols for both hard- and soft-decision decoding.

IEEE Information Theory Workshop (ITW)•Mar 1, 2004•2 citations

Soft-Decision List Decoding with Linear Complexity for the First-Order Reed-Muller Codes

Ilya I. Dumer, Grigory A. Kabatiansky, Cédric Tavernier

Soft-decision decoding on a memoryless channel is considered for the first-order Reed-Muller codes RM (1, m) of length 2m. We assume that different positions j of the received binary vector y can be corrupted by the errors of varying weight wj. The generalized Hamming distance between vector y and any binary vector c is then defined as the sum of weighted differences wj|yj- cj| taken over all n positions. We obtain a tight upper bound LTon the number of codewords located within generalized Hamming distance T from vector y, and design a decoding algorithm that outputs this list of codewords with complexity O (n ln2LT). In particular, all possible error weights wjequal 1 if this combinatorial model is applied to a binary symmetric channel. In this case, the well known Green algorithm performs full maximum likelihood decoding of RM (1, m) and requires O (n ln2n) bit operations, whereas the Litsyn-Shekhovtsov algorithm operates within the bounded-distance decoding radius n/4-1 with linear complexity O(n). We close the performance-complexity gap between the two algorithms. Namely, for any fixed (0, ½), our algorithm outputs the complete list of codewords within the decoding radius n(½-) with linear complexity of order n ln2.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•2 citations

Decoding of Reed-Muller codes with polylogarithmic complexity

Ilya I. Dumer

Code transmission is considered over a binary symmetric (BS) channel whose bit error probability is arbitrarily close to 1/2. New recursive decoding algorithms are designed for Reed-Muller (RM) codes of growing length 2m and fixed order r. The algorithms retrieve all information with a vanishing error probability and polylogarithmic complexity of order mr+1.

•Jan 5, 2004•2 citations

Optimum 1-Step Majority-Logic Decoding of Binary Reed–Muller Codes

Hoang Ly, Emina Soljanin

The classical majority-logic decoder proposed by Reed for Reed-Muller codes RM(r, m) of order r and length 2^m, unfolds in r+1 sequential steps, decoding message symbols from highest to lowest degree. Several follow-up decoding algorithms reduced the number of steps, but for a limited set of parameters, or at the expense of reduced performance, or relying on the existence of some combinatorial structures. We show that any one-step majority-logic decoder-that is, a decoder performing all majority votes in one step simultaneously without sequential processing-can correct at most d_min/4 errors for all values of r and m, where d_min denotes the code's minimum distance. We then introduce a new hard-decision decoder that completes the decoding in a single step and attains this error-correction limit. It applies to all r and m, and can be viewed as a parallel realization of Reed's original algorithm, decoding all message symbols simultaneously. Remarkably, we also prove that the decoder is optimum in the erasure setting: it recovers the message from any erasure pattern of up to d_min-1 symbols-the theoretical limit. To our knowledge, this is the first 1-step decoder for RM codes that achieves both optimal erasure correction and the maximum one-step error correction capability.

arXiv:2508.08736•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations
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.
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.
Reed-Muller (RM) codes (m, r) of length 2/sup m/ are considered on a binary symmetric (BS) channel with high crossover error probability 1/2 -/spl epsiv/. For an arbitrarily small /spl epsiv/>0, new recursive decoding algorithms are designed that retrieve all information bits of RM codes of fixed order r with a vanishing error probability and sublinear complexity of order O(m/sup r+1/). The algorithms utilize a vanishing fraction of the received symbols for both hard- and soft-decision decoding.
Soft-decision decoding on a memoryless channel is considered for the first-order Reed-Muller codes RM (1, m) of length 2m. We assume that different positions j of the received binary vector y can be corrupted by the errors of varying weight wj. The generalized Hamming distance between vector y and any binary vector c is then defined as the sum of weighted differences wj|yj- cj| taken over all n positions. We obtain a tight upper bound LTon the number of codewords located within generalized Hamming distance T from vector y, and design a decoding algorithm that outputs this list of codewords with complexity O (n ln2LT). In particular, all possible error weights wjequal 1 if this combinatorial model is applied to a binary symmetric channel. In this case, the well known Green algorithm performs full maximum likelihood decoding of RM (1, m) and requires O (n ln2n) bit operations, whereas the Litsyn-Shekhovtsov algorithm operates within the bounded-distance decoding radius n/4-1 with linear complexity O(n). We close the performance-complexity gap between the two algorithms. Namely, for any fixed (0, ½), our algorithm outputs the complete list of codewords within the decoding radius n(½-) with linear complexity of order n ln2.
The classical majority-logic decoder proposed by Reed for Reed-Muller codes RM(r, m) of order r and length 2^m, unfolds in r+1 sequential steps, decoding message symbols from highest to lowest degree. Several follow-up decoding algorithms reduced the number of steps, but for a limited set of parameters, or at the expense of reduced performance, or relying on the existence of some combinatorial structures. We show that any one-step majority-logic decoder-that is, a decoder performing all majority votes in one step simultaneously without sequential processing-can correct at most d_min/4 errors for all values of r and m, where d_min denotes the code's minimum distance. We then introduce a new hard-decision decoder that completes the decoding in a single step and attains this error-correction limit. It applies to all r and m, and can be viewed as a parallel realization of Reed's original algorithm, decoding all message symbols simultaneously. Remarkably, we also prove that the decoder is optimum in the erasure setting: it recovers the message from any erasure pattern of up to d_min-1 symbols-the theoretical limit. To our knowledge, this is the first 1-step decoder for RM codes that achieves both optimal erasure correction and the maximum one-step error correction capability.