LDPC碼的快速解碼方法研究

A Study of Fast LDPC Decoding Algorithm

林生旺(Sheng-Wang Lin)

指導教授 ： 鄭立德

中原大學/工學院/電子工程研究所/碩士(2012年)

https://doi.org/10.6840/cycu201200827

摘要

低密度校驗（Low Density Parity Check；LDPC) 碼使用疊代解碼方法來增加解碼的正確率，但因執行多次的疊代解碼動作則會造成功率的過度消耗及解碼時間的延遲。本文分析低密度校驗（Low Density Parity Check；LDPC) 碼之解碼方法，深入研究其對數域的信度傳播(Belief-Propagation；BP )演算法或是一般所稱之對數域的和-積演算法(Sum-Product Algorithm；SPA )，在解碼過程中分析傳遞訊息的收斂特性並利用交互熵(Cross Entropy；CE)的概念進行修正，進而提出一種能有效降低疊代次數和改善位元錯誤率之快速解碼演算法(Fast Decoding Algorithm；FDA )。模擬結果顯示，本文所提出之FDA方法相較於對數域BP演算法，不僅能有效地降低了疊代次數且在性能上有較優越的結果，確實提高了解碼效率。

關鍵字

交互熵 ； 快速解碼演算法 ； LDPC碼 ； 信度傳播演算法 ； 和-積演算法

並列摘要

Iterative decoding has been used in Low Density Parity Check (LDPC) codes to improve its performance, but too many iterations will result in waste of power consumption and time. In this thesis, we modify the logarithmic Belief-Propagation (BP) algorithm and LDPC decoding algorithms are reviewed in detail. The logarithmic Belief-Propagation algorithm is also called the logarithmic Sum-Product Algrithm (SPA). Due to deep theoretical analysis and simulative of inner character of LDPC iterative convergance, we developed a new reduced-complexity decoding algorithm. The proposed algorithm is called fast decoding algorithm (FDA). The fast decoding algorithm is based on the cross-entropy (CE) between the previous and the current APP (a posteriori probability) distribution of the decoded bit. With a simple modification, our presented method can reduce effectively the average number of iterations and achieve the better BER (bit error rate) performance, than that of logarithmic Belief-Propagation algorithm.

並列關鍵字

Low Density Parity Check (LDPC) ； cross-entropy (CE) ； fast decoding algorithm (FDA) ； Belief-Propagation (BP) ； Sum-Product Algorithm (SPA)

參考文獻

[1] C.E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, pp. 379-423(Part1); pp. 623-56(Part2), July 1948.

[2] R.G. Gallager, “Low Density Parity Check Codes,” IRE Trans. Inform. Theory, IT-8: pp. 21-28, January 1962.

[3] R.G. Gallager, Low Density Parity Check Codes, MIT Press, Cambridge, 1963.

[4] D.J.C. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices,” IEEE Trans. Inform. Theory, 45(2): pp. 399-432, March 1999.

[5] S.Y. Chung, G.D. Forney, Jr., T.J. Richardson, and R. Urbanke, “On the Design of Low Density Parity Check Codes within 0.0045dB of the Shannon Limit,” IEEE Communications Letters, 5: pp. 58-60, February 2001.