新的用於低密度同位檢查碼之重組解碼方法及其收斂性分析

New Shuffled Decoding of LDPC Codes and their Convergence Analysis

許晏誠

指導教授 ： 蘇育德

國立交通大學/電機學院/電信工程系所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00883

摘要

在本論文中，我們提出了兩種新的用於低密度同位檢查碼 (LDPC codes) 的重組信度傳遞解碼演算法(Shuffled Belief-Propagation Decoding)；為了加速解碼收斂速度以及降低運算複雜度，我們提出了一種將檢查節點分成有交集的組別的重組信度傳遞解碼方法。此外，我們亦提出了將水平重組(針對檢查節點分組)和垂直重組(針對變數節點做分組)混合交互使用的解碼方法。經由蒙特卡羅 (Monte-Carlo) 模擬的結果可以發現我們所提出的兩種演算法比起傳統的重組信度傳遞解碼演算法皆有較好的錯誤率效能。在此論文中，我們亦使用高斯近似 (Gaussian Approximation) 的方法來分析不同信度傳遞演算法的效能與解碼行為；理論分析與實驗模擬結果皆一致地顯示出我們所提之方法在相同的複雜度下可以達到較好的解碼成果。

關鍵字

低密度檢查碼 ； 低密度同位檢查碼 ； 解碼 ； 重組解碼

並列摘要

Two new shuffled belief propagation decoding algorithms for low-density parity-check (LDPC) codes are proposed in this thesis. To accelerate the decoding convergence rate and lower the implementation complexity, we propose a group shuffled decoding schedule which divides check nodes into non-disjoint groups to perform group-by-group
message-passing decoding. A hybrid shuffled manner utilizing horizontal shuffled scheme (partitioning check nodes into groups) and vertical shuffled scheme (partitioning variable nodes into groups) jointly is also presented. Monte-Carlo simulations show that our proposed approaches could provide better error-rate performance in comparison with the conventional shuffled decoding schedules. Performance of the proposed algorithms are analyzed by a Gaussian approximation approach. Both analysis and numerical experiments verify that the new algorithms do yield a convergence performance better than that of existing conventional shuffled BP decoder with the same computing complexity constraint.

並列關鍵字

Shuffled Decoding ； LDPC Codes

參考文獻

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

[3] D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electronics Lett., vol. 32, no. 18, pp. 1645-1646, Aug. 1996.

[4] DD. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inf. Theory, vol. 45, pp. 399-431, Mar. 1999.

[5] J. Zhang and M. Fossorier, “Shuffled belief propagation decoding,” IEEE Trans. Commun., vol. 53, pp. 209-213, Feb. 2005.

[6] A. Segard, F. Verdier, D. Declercq and P. Urard, “A DVB-S2 compliant LDPC decoder integrating the horizontal shuffle schedule,” presented in ISPACS06., pp. 1013-1016, Dec. 2006.