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 Transactions on Information Theory

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

Alexei Ashikhmin, Simon N. Litsyn

Published Jul 27, 2004• 55 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2004.831835

Related papers

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

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

On polylogarithmic decoding complexity for reed-muller codes

Ilya I. Dumer

For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•1 citation
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.
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.
For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2