針對建構有限長度之PEG 類型演算法效能改善之研究

Performance Improvement of PEG-based Construction for Finite-Length

杜建東

指導教授 ： 王忠炫

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

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

摘要

PEG演算法是一種常見而且簡單被用來建構large girth之有限長度的低密度奇偶檢查碼的方法。然而，我們發現PEG演算法在架構上有不足的地方，導致每次在Tanner graph上生長edge時無法把產生的cycle長度拉得更大，因此傷害了解碼效能。為了克服這樣不足的地方，這這篇論文中介紹了兩個方法。我們以前人的演算法為基礎，並運用這兩個方法，提出了兩個修改後的新演算法。此外，我們介紹了一個序列，這個序列透露了某些degree的variable node之間存在的cycle長度。從數據的結果顯示，我們的方法可以有效的拉大這個序列中的數值。而且這個數列不但可以簡單的區別Tanner graph的好壞，也可以提供給我們造碼的方向。從結果顯示，我們提出的演算法可以有效的改善cycle的連結性，因此效能能夠有一定程度的改善。

關鍵字

低密度奇偶檢查碼 ； 造碼 ； 效能改善

並列摘要

The progressive-edge-growth (PEG) algorithm is a well-known simple approach to construct finite length LDPC codes with large girth.
However, we find that the PEG algorithm has some fundamental weaknesses, which limit the maximum achievable cycle length of each edge grows in Tanner graph and hence hurt the decoding performance.
To overcome the weaknesses, two strategies for the PEG algorithm are proposed in this thesis. With these strategies, we proposed two algorithms modified from the PEG algorithm and the improved PEG algorithm respectively.
In addition, we introduce a cycle length sequence which coveys the cycle length information between variable nodes with different degree. The obtained results confirm that our strategies can effectively increase the cycle length sequence. This sequence is not only useful for discriminating a Tanner graph, but also valuable to provide new insights for code construction. Our results also show that the proposed algorithms can considerably improve the connectivity of cycles, and thus the performance is improved to some extent.

並列關鍵字

LDPC ； code construction ； performance improvement

參考文獻

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

[2] C. Y. Di et al., “Finite-length analysis of low-density parity-check codes on the binary erasure channel,” IEEE Trans. Inf. Theory , vol. 48, pp. 1570-1579, June 2002.

[5] T. Tian, C. Jones, J. D. Villasenor, and R. D. Wesel, “Selective avoidance of cycles in irregular LDPC code construction,” IEEE Trans. Commun., vol. 52, pp. 1242-1247, Aug. 2004.

[6] X. Y. Hu, E. Eleftheriou, and D. M. Arnold, “Regular and irregular progressive edgegrowth Tanner graphs,” IEEE Trans. Inf. Theory , vol. 51, no. 1, pp. 386-398, Jan. 2005.

[7] G. Richter and A. Hof, “On a construction method of irregular LDPC codes without small stopping sets,” in Proc. IEEE ICC'06. Istanbul, Turkey, 11-15 Jun. 2006, pp. 1119-1124.