在歐氏幾何基礎上建立的低密度奇偶檢查碼之迭代解碼研究

Study on the Decoding Algorithms for LDPC Codes Constructed from Euclidean Geometry

簡輔辰(Fu-Chen Chien)

指導教授 ： 翁詠祿

國立清華大學/電機資訊學院/積體電路設計產業研發碩士專班/碩士(2007年)

摘要

快速信息傳衍 (Turbo-Decoding Message-Passing ,TDMP)的解碼演算法已經被熟知用來加快傳統信息傳衍(Message-Passing)的收斂速度，此方法在低密度奇偶檢查(Low Density Parity Check ,LDPC)碼的應用上能夠達到較好的解碼能力並且解碼器在硬體實現上能節省記憶體。然而，快速信息傳衍(TDMP)演算法的吞吐量(throughput)將被限制在檢查節點(check node)的多寡來決定。
在這篇論文中,我們研究同步運行序列解碼(Concurrent Turbo-Decoding Message-Passing ,CTDMP)，可以在硬體實現上利用同步運行的層疊碼(super-codes)彼此交換非本質訊息(extrinsic information)，來增加吞吐量。另一種已被提出的方法稱為比例因子解碼(Scaled-Factor Message-Passing ,SF-MP)，比例因子是為了尋求解碼過程中，利用降低非本質回饋值造成信息變化的不穩定性，使解碼的信息遞迴傳衍能夠有較快的收斂速度，因為同步運行序列解碼(CTDMP)其平行性並不會降低原本(TDMP)的解碼能力，因此將比例因子解碼(SF-MP)和同步運行序列解碼(CTDMP)兩者結合，故而有可以提高吞吐量，同時也較快的收斂速度。

關鍵字

歐氏幾何 ； 低密度奇偶檢查碼 ； 快速信息傳衍

並列摘要

Turbo-Decoding Message-Passing (TDMP) algorithm has been proposed to improve the convergence rate of the conventional Message-Passing (MP) decoding algorithm for Low Density Parity Check (LDPC) codes. TDMP can achieve a better error performance and memory saving in implementation. However the throughput of the TDMP algorithm is limited, especially when the number of check equations is large.
In this thesis, we investigate Concurrent Turbo-Decoding Message-Passing (CTDMP) algorithm which can be used in VLSI implementation to increase the decoding throughput. The CTDMP algorithm is implemented by concurrently decoding the super-codes and exchanging extrinsic information among these super-codes. In addition, TDMP is used in the decoding of these super-codes.
Since CTDMP has no loss of convergence speed and is suitable for parallel implementation, CTDMP can be used to increase the decoding throughput. It is known that Scaled-Factor Message-Passing (SF-MP) algorithm can be used to increase the convergence speed of decoding. Hence, we also combine SF-MP and CTDMP algorithms to further increase the decoding throughput.

並列關鍵字

Euclidean Geometry ； Low Density Parity Check Codes ； Turbo-Decoding Message-Passing ； TDMP ； LDPC ； extrinsic information ； Scaled-Factor ； throughput

參考文獻

[1] R. G. Gallager, “Low density parity check codes,” IRE Trans. Inf.Theory, vol. IT-8, no. 1, pp. 21–28, Jan. 1962.

[3] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,”IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 399–432, Mar.1999.

[4] T. Richardson and R. Urbanke, “The capacity of low-density parity check codes under message-passing decoding,” IEEE Trans. Inf. Theory,vol. 47, no. 2,

Approaching low density parity check codes,” IEEE Trans. Inf. Theory,vol. 47,

[6] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inf.Theory, vol. IT-27, no. 9, pp. 533–547, Sep. 1981.