具低錯誤地板之低密度同位元檢查碼之建構

Construction of LDPC Codes with Low Error Floors

葉宗鑫(Tsung-Hsin Yeh)

指導教授 ： 呂忠津

國立清華大學/電機資訊學院/電機工程學系/碩士(2008年)

摘要

在低密度同位元檢查碼(LDPC codes)的研究領域中，如何建構出具低錯誤地板(error floor)之低密度同位元檢查碼近年來受到熱烈地研究和探討。常見的研究走向是先想辦法找出導致低密度同位元檢查碼在錯誤地板時解碼出錯的結構(error-prone patterns)，再想辦法消除它們。小的停止集(stopping sets)是低密度同位元檢查碼在二元抹失通道(binary erasure channel)中導致在錯誤地板解碼出錯的主要結構。我們稱一個低密度同位元檢查碼之最小停止集大小為停止距離(stopping distance)，而一個停止距離較大的低密度同位元檢查碼往往具有較低的錯誤地板。且一個具有較大的最小環長(girth)的低密度同位元檢查碼往往具有較大的停止距離。
LU碼是一種以代數方法建構的低密度同位元檢查碼。建構LU碼可以建構出具備任意大之最小環長的低密度同位元檢查碼。但由於LU碼普遍只具備非常低的碼率(code rate)而難以實際應用，經由一種遮罩法(masking method)，可以以LU碼為基礎建構一個具有高碼率且擁有原來LU碼之最小環長(girth)的低密度同位元檢查碼，我們稱之為LUmk碼。
此論文首先提出一個LUmk碼停止距離的下界限，根據此下界限，我們可知在建構LUmk碼時，提高某特定幾個參數，可以提高LUmk碼的停止距離下界限，不過在此同時也提高了LUmk碼之碼長(codeword length)。然後，藉由一個可以對低密度同位元檢查碼之停止集做分類的參數，還有許多模擬實驗的嘗試，我們最後提出一套可以從所有LUmk碼中挑出效能較好且具較低錯誤地板之LUmk碼的方法步驟。

關鍵字

低密度同位元檢查碼 ； 停止集 ； LU碼 ； 二元抹失通道 ； 錯誤地板

並列摘要

In this thesis, we proposed an effective method to construct practical LDPC codes with low error floors. We first consider a class of LDPC codes, called LUmk codes each of which is obtained by removing edges and nodes of the Tanner graph of an LU code and may have arbitrary large girth and high code rate. We derived a lower bound for the stopping distance of an LUmk code and developed a simple method to choose some edges and nodes which should be removed and get a small code ensemble with relatively low error floors from the original LUmk code ensemble.

並列關鍵字

LDPC code ； stopping set ； LU code ； binary erasure channel (BEC) ； error floor

參考文獻

[2] D. J. C. MacKay and R. M. Neal, "Near Shannon limit performance of low density parity check codes," Electron. Lett., vol. 32, pp. 1645-1646, Jan. 1996.

[3] R. M. Tanner, "A recursive approach to low complexity codes," IEEE Trans. Inform. Theory, vol. 27, pp. 533-547, May 1981.

[4] C. Di, D. Proietti, I. E. Telatar, T. J. Richardson, and R. Urbanke, "Finite-length analysis of low-density parity-check codes on the binary erasure channel," IEEE Trans. Inform. Theory, vol. 48, pp. 1570-1579, June 2002.

[7] K. M. Krishnan and P. Shankar, "On the complexity of Finding stopping distance in Tanner graphs," preprint.

[8] T. Tian, C. Jones, J. D. Villasenor, and R. D. Wesel, "Construction of irregular LDPC codes with low error Floors," 2003 IEEE International Conference on