在本論文中，我們專注於設計一種新的有限碼長低密度奇偶檢查碼(low density parity check code)的解碼演算法。一般來講，為了達到香農容量(Shannon capacity)必須使用長碼字(codelength)。然而，實際應用時過長的碼字會導致無法忍受的延遲(latency)。但是對於較短的碼字，傳統的置信傳遞(belief propagation, BP)解碼演算法的解碼效能不夠好。為了解決解碼效能的問題，我們使用了新的信息回授傳遞(feedback message passing, FMP) 並提出新的演算法。信息回授傳遞的想法是對於一個特殊的頂點集合執行兩階段的置信傳遞，而這個特殊的頂點集合被稱為回授頂點集合(feedback vertex set)。但是要從低密度奇偶檢查碼的圖中找到回授頂點集合是困難的，因此我們改成尋找停止集(stopping set)。藉著使用停止集來修改信息回授傳遞，我們的模擬結果顯示出當使用IEEE 802.11n標準的低密度奇偶檢查碼時我們提出的演算法比起一般的置信傳遞的解碼效能更好，而且跟一般的置信傳遞法一樣，我們提出的演算法複雜度還是與碼長呈線性比例。

In this thesis, we focus on designing a new decoding algorithm for finite block length low density parity check (LDPC) code. Typically, a long codeword length is necessary to achieve the Shannon capacity. However, long codeword length prohibits real-time applications due to the intolerable latency. For the short codeword length regime, the performance of conventional belief propagation(BP) decoding algorithm is not good enough. To solve this problem, we propose a new decoding algorithm which use the new feedback message passing (FMP). The idea of FMP is to perform a two-stage BP on a special set of vertices, named feedback vertex set. It is hard to find a feedback vertex set in the Tanner graph of LDPC code, thus we instead finding a stopping set. By modifying the FMP with the stopping set, our simulation results show that our proposed algorithm outperform the BP for the LDPC code adopted in IEEE 802.11n standard. And as BP algorithm, the complexity of proposed one is still linear in codeword length.

[1] Boccardi, Federico, et al. ”Five disruptive technology directions for 5G.” Communications Magazine, IEEE 52.2 (2014): 74-80.
[2] R. Gallager, ”Low-Density Parity-Check Codes,” IEEE Trans. Inf. Theory, vol. 8, Jan. 1962.
[3] MLA Tanner, R. Michael. ”A recursive approach to low complexity codes.” Information Theory, IEEE Transactions on 27.5 (1981): 533-547.
[4] Liu, Ying, et al. ”Feedback message passing for inference in Gaussian graphical models.” Signal Processing, IEEE Transactions on 60.8 (2012): 4135-4150.
[5] Di, Changyan, et al. ”Finite-length analysis of low-density parity-check codes on the binary erasure channel.” Information Theory, IEEE Transactions on 48.6 (2002): 1570-1579.
[6] Rosnes, Eirik. ”An efficient algorithm to find all small-size stopping sets of low-density parity-check matrices.” Information Theory, IEEE Transactions on 55.9 (2009): 4167-4178.
[7] Polyanskiy, Yury, H. Vincent Poor, and Sergio Verdú. ”Channel coding rate in the finite blocklength regime.” Information Theory, IEEE Transactions on 56.5 (2010): 2307-2359.
[8] Perahia, Eldad, and Robert Stacey. Next Generation Wireless LANS: 802.11 n and 802.11 ac. Cambridge university press, 2013.