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 International Symposium on Information Theory (ISIT)

Soft decision majority decoding

Ilya I. Dumer, R.E. Krichevskiy

Published Nov 7, 2002• 0 citations
Publisher

Abstract

We present a new soft decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of all received symbols are recalculated into the reliabilities of the parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to the more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft decision algorithm outperforms its conventional hard decision counterpart by 10 log/sub 10/(/spl pi//2)/spl ap/2 dB at any given output bit error rate /spl epsi/<1/2.

DOI
10.1109/isit.2000.866379

Related papers

Soft-decision majority decoding of Reed-Muller codes

Ilya I. Dumer, R.E. Krichevskiy

We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2/sup m/ transmitted symbols are recalculated into the reliabilities of 2/sup m-r/ parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log/sub 10/(/spl pi//2)/spl ap/2 dB at any given output error probability. For fixed code rate R and m/spl rarr//spl infin/, our algorithm increases almost 2/sup r/2/ times the correcting capability of soft-decision bounded distance decoding.

IEEE Transactions on Information Theory•Jan 1, 2000•31 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

Soft-decision decoding of Reed-Muller codes: a simplified algorithm

Ilya I. Dumer

Soft-decision decoding is considered for general Reed-Muller (RM) codes of length n and distance d used over a memoryless channel. A recursive decoding algorithm is designed and its decoding threshold is derived for long RM codes. The algorithm has complexity of order nlnn and corrects most error patterns of the Euclidean weight of order radicn/lnn, instead of the decoding threshold radicd/2 of the bounded distance decoding. Also, for long RM codes of fixed rate R, the new algorithm increases 4/pi times the decoding threshold of its hard-decision counterpart

IEEE Transactions on Information Theory•Mar 1, 2006•59 citations

Iterative Hard-Decision Decoding Algorithms for Binary Reed-Muller Codes

Yong-Ting Ni, Duc Nhat Nguyen, Feng-Kai Liao +2 more

In this paper, novel hard-decision iterative decoding algorithms for binary Reed-Muller (RM) codes are presented. First, two algorithms are devised based on the majority-logic decoding algorithm with reliability measures of the received sequence. The bit-flipping (BF) and the normalized bit-flipping (NBF) decoding algorithms are hard-decision decoding algorithms. According to the updated hard reliability measures, the BF and NBF algorithms flip one bit of the received hard-decision sequence at a time in each iteration. The NBF decoding algorithm performs better than the BF decoding algorithm by normalizing the reliability measures of the information bits. Moreover, the BF and NBF algorithms are modified to flip multiple bits in one iteration to reduce the average number of iterations. The modified decoding algorithms are called the multiple-bits-flipping (MBF) algorithm and the normalized multiple-bits-flipping (NMBF) algorithm, respectively. The proposed algorithms have low computational complexities and can converge rapidly after a small number of iterations. The simulation results show that the proposed hard-decision decoding algorithms outperform the conventional decoding algorithm.

IEEE Access•Jan 1, 2022•0 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

Error Exponents for Two Soft-Decision Decoding Algorithms of Reed–Muller Codes

M. V. Burnashev, Ilya I. Dumer

Error exponents are studied for recursive and majority decoding of general Reed-Muller (RM) codesRM(r,m) used on the additive white Gaussian noise (AWGN) channels. Both algorithms have low complexity and correct many error patterns whose weight exceeds half the code distance. Decoding consists of multiple consecutive steps, which repeatedly recalculate the input symbols and determine different information symbols using soft-decision majority voting. For any codeRM(r,m), we estimate the probabilities of the information symbols obtained in these recalculations and derive the analytical upper bounds for the block error rates of the recursive and majority decoding. In the case of a low noise, we also obtain the lower bounds and show that the upper bounds are tight. For a higher noise, these bounds closely approach our simulation results.

IEEE Transactions on Information Theory•Aug 24, 2009•2 citations
We present a new soft decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of all received symbols are recalculated into the reliabilities of the parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to the more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft decision algorithm outperforms its conventional hard decision counterpart by 10 log/sub 10/(/spl pi//2)/spl ap/2 dB at any given output bit error rate /spl epsi/<1/2.
We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2/sup m/ transmitted symbols are recalculated into the reliabilities of 2/sup m-r/ parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log/sub 10/(/spl pi//2)/spl ap/2 dB at any given output error probability. For fixed code rate R and m/spl rarr//spl infin/, our algorithm increases almost 2/sup r/2/ times the correcting capability of soft-decision bounded distance decoding.
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.
Soft-decision decoding is considered for general Reed-Muller (RM) codes of length n and distance d used over a memoryless channel. A recursive decoding algorithm is designed and its decoding threshold is derived for long RM codes. The algorithm has complexity of order nlnn and corrects most error patterns of the Euclidean weight of order radicn/lnn, instead of the decoding threshold radicd/2 of the bounded distance decoding. Also, for long RM codes of fixed rate R, the new algorithm increases 4/pi times the decoding threshold of its hard-decision counterpart
In this paper, novel hard-decision iterative decoding algorithms for binary Reed-Muller (RM) codes are presented. First, two algorithms are devised based on the majority-logic decoding algorithm with reliability measures of the received sequence. The bit-flipping (BF) and the normalized bit-flipping (NBF) decoding algorithms are hard-decision decoding algorithms. According to the updated hard reliability measures, the BF and NBF algorithms flip one bit of the received hard-decision sequence at a time in each iteration. The NBF decoding algorithm performs better than the BF decoding algorithm by normalizing the reliability measures of the information bits. Moreover, the BF and NBF algorithms are modified to flip multiple bits in one iteration to reduce the average number of iterations. The modified decoding algorithms are called the multiple-bits-flipping (MBF) algorithm and the normalized multiple-bits-flipping (NMBF) algorithm, respectively. The proposed algorithms have low computational complexities and can converge rapidly after a small number of iterations. The simulation results show that the proposed hard-decision decoding algorithms outperform the conventional decoding algorithm.
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
Error exponents are studied for recursive and majority decoding of general Reed-Muller (RM) codesRM(r,m) used on the additive white Gaussian noise (AWGN) channels. Both algorithms have low complexity and correct many error patterns whose weight exceeds half the code distance. Decoding consists of multiple consecutive steps, which repeatedly recalculate the input symbols and determine different information symbols using soft-decision majority voting. For any codeRM(r,m), we estimate the probabilities of the information symbols obtained in these recalculations and derive the analytical upper bounds for the block error rates of the recursive and majority decoding. In the case of a low noise, we also obtain the lower bounds and show that the upper bounds are tight. For a higher noise, these bounds closely approach our simulation results.