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 Access

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

Yong-Ting Ni, Duc Nhat Nguyen, Feng-Kai Liao, Tzu-Chieh Kao, Chao‐Yu Chen

Published Jan 1, 2022• 0 citations
Publisher

Abstract

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.

DOI
10.1109/access.2022.3180368

Related papers

An Iterative Bit-Flipping Decoding Algorithm For Binary Reed-Muller Codes *

Yong-Ting Ni, Cheng-Yu Pai, Chao‐Yu Chen

This paper presents an iterative bit-flipping (BF) decoding algorithm for binary Reed-Muller (RM) codes. The BF decoding algorithm is a hard-decision decoding algorithm. According to the updated hard reliability measures, one bit of the received hard-decision sequence is flipped at a time in each iteration. The simulation results show that the proposed BF decoding algorithm outperforms the conventional hard-decision majority decoding.

International Symposium on Information Theory and its Applications•Oct 24, 2020•1 citation

Soft decision majority decoding

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

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•0 citations

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

On Decoding Using Codewords of the Dual Code

Martin Bossert

We present novel decoding schemes for hard and soft decision decoding of block codes using the minimal weight codewords of the dual code. The decoding schemes will be described for cyclic codes where polynomials can be used, however, the modification for non-cyclic codes is possible and straight forward. The hard decision decoding calculates syndrome polynomials which are the product of the received polynomial with dual codewords. Proper cyclic shifts of these syndrome polynomials are obtained and the non-zero positions are counted componentwise for these shifts. The values of this counting are a reliability measure and can be used for locating the error and also the non-error positions. This reliability measure is the basis for various variants of hard decision decoding algorithms. Decoding schemes with iterative error reduction are possible as well as information set decoding using the inherent reliability information of the measure even if there is no reliability information from the channel. Further, we will show how reliability information from the channel can be included in order to obtain soft decision decoding schemes. We derive the relation between bit flipping, believe propagation, and majority logic decoding to the novel schemes. As examples to illustrate the functioning we use BCH and Reed-Muller codes as examples for binary codes, and RS codes for non-binary codes. Besides the Plotkin construction we recall a known result that Reed-Muller codes punctured by one position are cyclic and thus, are equivalent to special cases of BCH codes. Simulation results for hard and soft decision decoding will be given for several examples and compared with results from literature. Finally, we analyze the soft decision decoding of the Plotkin construction and derive that one of the two codes uses a $3$ dB better channel (also known as channel polarization).

arXiv:2001.02956•Jan 9, 2020•6 citations

Modified majority logic decoding of Reed–Muller codes using factor graphs

Ting‐Ya Yang, Houshou Chen

This study investigates the decoding algorithms of binary Reed–Muller (RM) codes. The main goal of the study is to modify majority‐logic decoding using sum‐product or min‐sum decoding algorithms at the highest‐order information bits in RM codes. Numerical results show that compared with the traditional majority‐logic decoding algorithm, the modified majority‐logic decoding method proposed in this study can reduce the bit error rate by a large margin. This is achieved without incurring a significant increase in decoding complexity because soft‐decision decoding is only used in the highest information bits in RM codes whereas majority‐logic decoding is still applied at the other orders of information bits in RM codes.

IET Communications•Jan 31, 2018•2 citations

The Novel Modified Weighted Bit-Flipping Decoding Algorithms for Reed-Muller Codes with Simple Scaling and SNR Adaption

Yufang Yin, Yingsong Chen

Bit-flipping (BF) algorithm has been widely employed in decoding linear block codes because of its simple implementation. We consider the most popular modified weighted bit-flipping (MWBF) algorithm and propose two novel LLR scaling based MWBF algorithms for RM (Reed-Muller) decoding. By introducing the log likelihood ratio as the scaling factor to tune the bit-based message and then approximately approaching the SNR adaption, the proposed two decoding algorithms outperform regular MWBF method with similar computational cost.

IEEE International Conference on Computer and Communications (ICCC)•Dec 11, 2020•0 citations
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.
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.
We present novel decoding schemes for hard and soft decision decoding of block codes using the minimal weight codewords of the dual code. The decoding schemes will be described for cyclic codes where polynomials can be used, however, the modification for non-cyclic codes is possible and straight forward. The hard decision decoding calculates syndrome polynomials which are the product of the received polynomial with dual codewords. Proper cyclic shifts of these syndrome polynomials are obtained and the non-zero positions are counted componentwise for these shifts. The values of this counting are a reliability measure and can be used for locating the error and also the non-error positions. This reliability measure is the basis for various variants of hard decision decoding algorithms. Decoding schemes with iterative error reduction are possible as well as information set decoding using the inherent reliability information of the measure even if there is no reliability information from the channel. Further, we will show how reliability information from the channel can be included in order to obtain soft decision decoding schemes. We derive the relation between bit flipping, believe propagation, and majority logic decoding to the novel schemes. As examples to illustrate the functioning we use BCH and Reed-Muller codes as examples for binary codes, and RS codes for non-binary codes. Besides the Plotkin construction we recall a known result that Reed-Muller codes punctured by one position are cyclic and thus, are equivalent to special cases of BCH codes. Simulation results for hard and soft decision decoding will be given for several examples and compared with results from literature. Finally, we analyze the soft decision decoding of the Plotkin construction and derive that one of the two codes uses a 333 dB better channel (also known as channel polarization).
This study investigates the decoding algorithms of binary Reed–Muller (RM) codes. The main goal of the study is to modify majority‐logic decoding using sum‐product or min‐sum decoding algorithms at the highest‐order information bits in RM codes. Numerical results show that compared with the traditional majority‐logic decoding algorithm, the modified majority‐logic decoding method proposed in this study can reduce the bit error rate by a large margin. This is achieved without incurring a significant increase in decoding complexity because soft‐decision decoding is only used in the highest information bits in RM codes whereas majority‐logic decoding is still applied at the other orders of information bits in RM codes.
Bit-flipping (BF) algorithm has been widely employed in decoding linear block codes because of its simple implementation. We consider the most popular modified weighted bit-flipping (MWBF) algorithm and propose two novel LLR scaling based MWBF algorithms for RM (Reed-Muller) decoding. By introducing the log likelihood ratio as the scaling factor to tune the bit-based message and then approximately approaching the SNR adaption, the proposed two decoding algorithms outperform regular MWBF method with similar computational cost.