在此篇論文中，我們提出了全新的二進制里德穆勒碼之疊代解碼演算法，包括兩種硬判決和一種軟判決解碼演算法。利用位元的可靠度量測，在每次重新編碼後進行更新。透過疊代及不斷更新位元可靠度來進行解碼。硬判決解碼算法根據每次更新的可靠性度量，在每次疊代中只翻轉接收序列的一個位元。且藉由標準化信息位元的可靠性度量，可以增進位元翻轉解碼算法的性能。除此之外，透過最小與總和的運算來更新接收序列的可靠性度量，本文也提出軟判決的解碼算法。本文所提出的多種解碼演算法，以多數決解碼為基礎，因此具有低運算複雜度。此外，提出的疊代解碼能在很少的疊代內快速收斂。模擬結果顯示，本文提出的硬判決解碼算法在性能上要比現有的傳統多數決解碼算法好，軟判決解碼算法也優於現有的軟判決多數決演算法和改良多數決演算法。

In this thesis, novel iterative decoding algorithms for binary Reed-Muller (RM) codes are presented. There are two hard-decision and one soft-decision decoding algorithms. These algorithms are devised based on the majority-logic decoding algorithm with reliability measures of the received sequence. The reliability measures can be updated by re-encoding the codeword in each iteration. 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, updating the reliability measures of received sequence by min-sum (MS) operation, a soft-decision MS decoding algorithm is also proposed. 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; the proposed soft-decision decoding algorithm has less complexity and performs better than the soft-decision majority-logic decoding algorithms.

[1] D. E. Muller, “Application of boolean algebra to switching circuit design and to error detection,” IRE Trans., no. 3, pp. 6–12, 1954.
[2] I. Reed, “A class of multiple-error-correcting codes and the decoding scheme,” IEEE Trans. Inf. Theory, vol. 4, no. 4, pp. 38–49, Sep. 1954.
[3] G. Schnabl and M. Bossert, “Soft-decision decoding of Reed-Muller codes as generalized multiple concatenated codes,” IEEE Trans. Inf. Theory, vol. 41, no. 1, pp. 304–308, Jan. 1995.
[4] A. E. Jones and T. A.Wilkinson, “Performance of Reed-Muller codes and a maximum-likelihood decoding algorithm for OFDM,” IEEE Trans. Commun., vol. 47, no. 7, pp. 949–952, Jul. 1999.
[5] K.-U. Schmidt and A. Finger, “Simple maximum-likelihood decoding of generalized first-order Reed-Muller codes,” IEEE Commun. Letters, vol. 9, no. 10, pp. 912–914, Oct. 2005.
[6] A. Ashikhmin and S. Litsyn, “Simple MAP decoding of first-order Reed-Muller and Hamming codes,” IEEE Trans. Inf. Theory, vol. 50, no. 8, pp. 1812–1818, Jul. 2004.
[7] K. G. Paterson and A. E. Jones, “Efficient decoding algorithms for generalized Reed-Muller codes,” IEEE Trans. Commun., vol. 48, no. 8, pp. 1272–1285, Aug. 2000.
[8] I. Dumer and R. Krichevskiy, “Soft-decision majority decoding of Reed-Muller codes,” IEEE Trans. Inf. Theory, vol. 46, no. 1, pp. 258–264, Jan. 2000.
[9] I. Dumer, “Recursive decoding and its performance for low-rate Reed-Muller codes,” IEEE Trans. Inf. Theory, vol. 50, no. 5, pp. 811–823, May. 2004.
[10] ——, “Soft-decision decoding of Reed-Muller codes: a simplified algorithm,” IEEE Trans. Inf. Theory, vol. 52, no. 3, pp. 954–963, Mar. 2006.
[11] I. Dumer and K. Shabunov, “Soft-decision decoding of Reed-Muller codes: recursive lists,” IEEE Trans. Inf. Theory, vol. 52, no. 3, pp. 1260–1266, Mar. 2006.
[12] M. Ye and E. Abbe, “Recursive projection-aggregation decoding of reed-muller codes,” IEEE Trans. Inf. Theory, Mar. 2020.
[13] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051–3073, Jun. 2009.
[14] ——, “A performance comparison of polar codes and Reed-Muller codes,” IEEE Commun. Lett., vol. 12, no. 6, pp. 447–449, Jun. 2008.
[15] M. Mondelli, S. H. Hassani, and R. L. Urbanke, “From polar to Reed-Muller codes: A technique to improve the finite-length performance,” IEEE Trans. Commun., vol. 62, no. 9, pp. 3084–3091, Aug. 2014.
[16] S. A. Hashemi, N. Doan, M. Mondelli, and W. J. Gross, “Decoding Reed-Muller and polar codes by successive factor graph permutations,” in 2018 IEEE Int. Symp. on Turbo Codes & Iterative Information Processing (ISTC), Dec. 2018, pp. 1–5.
[17] M. Kamenev, Y. Kameneva, O. Kurmaev, and A. Maevskiy, “A new permutation decoding method for Reed-Muller codes,” in 2019 IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2019, pp. 26–30.
[18] K. Ivanov and R. Urbanke, “Permutation-based decoding of Reed-Muller codes in binary erasure channel,” in 2019 IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2019, pp. 21–25.
[19] T.-Y. Yang and H.-S. Chen, “Modified majority logic decoding of Reed-Muller codes using factor graphs,” IET Commun., vol. 12, no. 7, pp. 759–764, April. 2018.
[20] S.-Y. Chung, T. J. Richardson, and R. L. Urbanke, “Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 657–670, Feb. 2001.
[21] J. Zhao, F. Zarkeshvari, and A. H. Banihashemi, “On implementation of min-sum algorithm and its modifications for decoding low-density parity-check (LDPC) codes,” IEEE Trans. Commun., vol. 53, no. 4, pp. 549–554, May. 2005.
[22] R. Gallager, “Low-density parity-check codes,” IRE Trans. Inf. Theory, vol. 8, no. 1, pp. 21–28, Jan. 1962.
[23] R. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inf. Theory, vol. 27, no. 5, pp. 533–547, Sept. 1981.
[24] F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 498–519, Feb. 2001.
[25] M. Jiang, C. Zhao, Z. Shi, and Y. Chen, “An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes,” IEEE Commun. Letters, vol. 9, no. 9, pp. 814–816, Nov. 2005.
[26] J. Zhang and M. P. Fossorier, “A modified weighted bit-flipping decoding of low-density parity-check codes,” IEEE Commun. Letters, vol. 8, no. 3, pp. 165–167, Mar. 2004.
[27] M. P. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low-density parity check codes based on belief propagation,” IEEE Trans. Commun., vol. 47, no. 5, pp. 673–680, May. 1999.
[28] J. Chen, A. Dholakia, E. Eleftheriou, M. P. Fossorier, and X.-Y. Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun., vol. 53, no. 8, pp. 1288–1299, Aug. 2005.
[29] Y. Be’ery and J. Snyders, “Optimal soft decision block decoders based on fast Hadamard transform,” IEEE Trans. Inf. Theory, vol. 32, no. 3, pp. 355–364, May. 1986.
[30] G. D. Forney, “Coset codes. II. Binary lattices and related codes,” IEEE Trans. Inf. Theory, vol. 34, no. 5, pp. 1152–1187, Sept. 1988.