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.

Introduction

     The Reed-Muller (RM) code is a class of multiple-error-correction codes. In the past, RM codes were used in wireless communications, especially in deep-space communications. RM codes were first discovered by Muller [1] and the conventional decoding scheme of RM code, which is the majority-logic decoding, was proposed by Reed in 1954 [2]. Ever since their discovery, a number of efficient decoding schemes have been constructed. In 1995, Schnabl and Bossert proposed a generation of Reed-Muller codes by multiple concatenations and provided a new decoding procedure using soft-decision information [3]. In 1999, a maximum-likelihood (ML) decoder which uses a distance-preserving map and multiple fast Hadamard transforms (FHTs) was presented by Jones and Wilkinson [4] whereas a maximum a posterior (MAP) decoding algorithm for the first-order RM codes was proposed in [5]. In 2000, a new soft-decision majority-logic decoding algorithm was presented by revising the conventional majority-logic decoding [6]. Besides, the recursive decoding algorithms were provided in [7]–[۱۱]. In 2006, the recursive list decoding was modified by Dumer and Shabunov to approach the performance of ML decoding [9]. Recently, Ye and Abbe proposed the recursive projection-aggregation (RPA) decoding algorithm with lists to have comparable performance with the recursive list decoding [10]. In the same year, the recursive puncturing-aggregation (RXA) algorithm was proposed via replacing the projection by puncturing in RPA [11].

     In recent years, the breakthrough of polar codes [12]–[۱۵] has brought attention back to RM codes due to the similarity of these two codes. The performance comparison between RM codes and polar codes was demonstrated in [10], [15]–[۱۷]. It has been shown that the RM codes with RPA decoding [10] can significantly outperform the polar codes under successive-cancellation list (SCL) decoding [18]–[۲۰]. In addition, by exploiting the idea of decoding polar codes, [21], [22] presented permutation-based decoding methods for RM codes.

Conclusion

     In this paper, we have proposed several hard-decision decoding algorithms for binary RM codes. They are iterative decoding algorithms that have not been proposed in the literature. The performance can be improved by updating the reliability measures and flipping codeword bits. These algorithms do not need large computational complexity since they can converge very rapidly in a small number of iterations. For hard-decision decoding, our proposed NBF decoding algorithm outperforms the conventional majority-logic decoding algorithm with 0.55 dB to 0.8 dB gain. These proposed algorithms have the same complexity orders. Specifically, the BF and MBF decoding algorithms only require integer additions.

     Decoding the RM codes with our iterative decoding algorithms converges very fast with a small number of iterations. Moreover, the proposed MBF/NMBF algorithms can decrease the number of iterations such that the overall complexity can be reduced. The average number of iterations can be reduced by 40% to 80% compared to the BF/NBF algorithms.