在此篇論文中，我們提出了全新的二元里德穆勒碼之疊代列表解碼演算法，包括兩種硬判決和一種軟判決解碼演算法。這些演算法是基於疊代解碼演算法和列表解碼方法所結合設計的。其中疊代硬判決列表和標準化疊代硬判決列表解碼演算法是硬判決解碼演算法。在第一次疊代後，我們根據與接收向量之距離列出一個向量列表，每個可能向量都可能是傳輸的向量。疊代硬判決列表 和 標準化疊代硬判決列表解碼演算法在每次疊代中透過更新位元之可靠性度量，翻轉接收到的硬判決序列的一個位元或多個位元。由於標準化信息位元之可靠性度量，標準化疊代硬判決列表解碼演算法的性能優於疊代硬判決列表解碼演算法。 接著在疊代軟判決列表 演算法中我們利用列表解碼的概念列出多個可能的待解碼，並使用和積運算來更新可靠性度量。所提出的演算法具有相對較低的運算複雜度，並且可以在高信噪比區間以少次疊代快速收斂。模擬結果顯示，本文提出的硬判決列表解碼演算法優於位元翻轉演算法，所提出的軟決策列表解碼演算法的性能優於最小與總和演算法。

In this paper, we proposed three novel iterative list decoding algorithms for binary Reed-Muller (RM) codes. There are two hard-decision and one soft-decision decoding algorithms. These algorithms are devised based on the iterative decoding algorithms and the list decoding methods.
The iterative hard-decision list (IHDL) and the normalized iterative hard-decision list (NIHDL) decoding algorithms are hard-decision decoding algorithms. From the received vector, the proposed algorithms make a list of vectors which each of them are likely to be the transmitted vector. The IHDL and NIHDL algorithms flip one or multiple bits of the received hard-decision sequence in each iteration based on the updated reliability measures of code bits. The NIHDL decoding algorithm performs better than the IHDL decoding algorithm by normalizing the reliability measures of the information bits.
The iterative soft-decision list (ISDL) exploits the ideal of list decoding and uses the sum-product operation for computing the reliability measures. The proposed algorithms have relatively low computational complexities, and can converge rapidly with a small number of iterations in high signal-to-noise ratio region. The simulation results show that the proposed hard-decision list decoding algorithms outperform the bit-flipping algorithm and the proposed soft-decision list decoding algorithm performs better than the existing min-sum decoding algorithm.

[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 maximumlikelihood decoding algorithm for OFDM,” IEEE Trans. Commun., vol. 47, no. 7, pp. 949–952, Jul. 1999.
[5] 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.
[6] 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.
[7] 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.
[8] ——, “Soft-decision decoding of Reed-Muller codes: a simplified algorithm,” IEEE Trans. Inf. Theory, vol. 52, no. 3, pp. 954–963, Mar. 2006.
[9] 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.
[10] M. Ye and E. Abbe, “Recursive projection-aggregation decoding of Reed-Muller codes,” IEEE Trans. Inf. Theory, Aug. 2020.
[11] M. Lian, C. H¨ager, and H. D. Pfister, “Decoding Reed–Muller codes using redundant code constraints,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Virtual, Jun. 2020, pp. 42–47.
[12] M. Kamenev, Y. Kameneva, O. Kurmaev, and A. Maevskiy, “A new permutation decoding method for Reed-Muller codes,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Paris, France, Jul. 2019, pp. 26–30.
[13] K. Ivanov and R. Urbanke, “Permutation-based decoding of Reed-Muller codes in binary erasure channel,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Paris, France, Jul. 2019, pp. 21–25.
[14] 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.
[15] I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Trans. Inf. Theory, vol. 61, no. 5, pp. 2213–2226, May. 2015.
[16] E. Arikan, “A performance comparison of polar codes and Reed-Muller codes,” IEEE Commun. Lett., vol. 12, no. 6, pp. 447–449, Jun. 2008.
[17] 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.
[18] S. A. Hashemi, N. Doan, M. Mondelli, and W. J. Gross, “Decoding Reed-Muller and polar codes by successive factor graph permutations,” in Proc. IEEE Int. Symp. on Turbo Codes & Iterative Information Processing (ISTC), Dec. 2018, pp. 1–5.
[19] R. Gallager, “Low-density parity-check codes,” IRE Trans. Inf. Theory, vol. 8, no. 1, pp. 21–28, Jan. 1962.
[20] 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.
[21] 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.
[22] 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.
[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] Y.-T. Ni, C.-Y. Pai, and C.-Y. Chen, “An iterative bit-flipping decoding algorithm for binary Reed-Muller codes,” in Proc. Int. Symp. Inf. Theory and Its Appl. (ISITA), Kapolei, Hawai’i, Oct. 2020, pp. 1–5.
[26] Chase, “A class of algorithms for decoding block codes with channel measurement information,” IEEE Trans. Inf. Theory, Jan. 1972.
[27] P. Hagenauer, Offer, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. Inf. Theory, vol. 42, no. 2, pp. 429–445, 1996.
[28] 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.
[29] 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.
[30] 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.
[31] J. Zhang and M. P. Fossorier, “A modified weighted bit-flipping decoding of lowdensity parity-check codes,” IEEE Commun. Letters, vol. 8, no. 3, pp. 165–167, Mar. 2004.