建構長周長且可平行解碼之低密度同位檢測碼

Construction of large-girth and parallelized-decoding LDPC codes

王證貴(CHENG-KUEI WANG)

指導教授 ： 李昌明

國立中正大學/工學院/通訊工程學系/碩士(2016年)

摘要

低密度同位檢測 (Low-Density Parity-Check, LDPC) 碼有接近Shannon理論極限的效能，但是解碼過程複雜度高，導致無法使用於即時 (real-time) 系統，為解決此問題，許多研究將平行處理運用在LDPC解碼端，達到加速解碼的效果。但傳統的LDPC codes很難實現平行解碼，過程中會消耗大量的記憶體，或是減緩解碼速度。
本論文將提供一種可平行解碼的LDPC codes的建造方法，將LDPC codes的同位檢測矩陣 (parity-check matrix) 分割成數個同樣大小的區塊，使每個區塊在解碼端都可以在不同處理器運作，達到平行解碼的目的，並透過區塊間的記憶體存取限制，在有限的記憶體情況下防止存取衝突，可減少存取衝突時所需的緩衝時間，加快解碼速度；在考量平行解碼時，為維持LDPC codes的更錯效能，本論文將討論如何避免短周長 (girth) 的議題，會採用簡化矩陣 (simplified matrix) 來代替同位檢測矩陣，將周長的限制轉換成線性系統，在建造過程中可以更方便檢測是否符合記憶體存取與周長的限制，以建立具平行解碼與高更錯效能的同位檢測矩陣。

關鍵字

LDPC codes ； 長周長 ； 平行解碼

並列摘要

The low-density parity check (LDPC) codes have near-Shannon limit performance. But the complexity of LDPC decoding is too high to real-time systems. In the parallelization for high-throughput applications, the number of independent memory access usually dominates the coding throughput. Moreover, a class of large-girth LDPC codes usually has difficulties to realize the parallelization in the decoder.
We propose a code construction to take the number of required parallel decoding unit and the large-girth constraint into considerations at once. First, the parity check matrix would be split into the block-wise structure to fit the parallelization in the decoder. Second, the conversion of the cycle-checking inequalities can transform the girth issue into a linear system. In this paper, we represent the parity-check matrix by simplified matrix to check the constrains in construction easily.

並列關鍵字

LDPC codes ； large-girth ； parallelized-decoding

參考文獻

[1] F. Kienle and N. Wehn, “Design methodology for IRA codes” Design Automation Conference, 2004. Proceedings of the ASP-DAC 2004. Asia and South Pacific 27-30 Jan. 2004, Page(s):459 – 462.

[3] R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Information Theory, vol. IT-18, Jan. 1962, Page(s): 21-28

[5] Hao Zhong, Tong Zhong and E. F. Haratsch, “Quasi-Cyclic LDPC Codes for the Magnetic Recording Channel: Code Design and VLSI Implementation,” IEEE Transactions on Magnetics, vol. 43, Issue 3, March 2007, Page(s):1118 – 1123.

[7] Zongwang Li, Lei Chen, Lingqi Zeng, S. Lin and W. H. Fong, “Efficient encoding of quasi-cyclic low-density parity-check codes,” IEEE Transactions on Communications, vol. 54, Issue 1, Jan. 2006, Page(s):71 – 81.

[9] Sang-Min Kim and K.K Parhi, “Overlapped decoding for a class of quasi-cyclic LDPC codes,” IEEE Workshop on Signal Processing Systems, 2004. Page(s):113 – 117.