適用於IEEE 802.16e標準之中低密度同位檢查碼的快速收斂解碼方式與具有有效記憶體使用的超大型積體電路解碼器架構

A fast-convergence decoding method and memory- efficient VLSI decoder architecture for LDPC codes in IEEE 802.16e standard

鄭仲超(Chung-Chao Cheng)

指導教授 ： 翁詠祿

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

摘要

在本論文中我們提出降低解碼疊代次數的演算法，這解碼演算法適用於LDPC(Low-Density Parity-Check)碼，類似IEEE 802.16e Standard所使用的LDPC碼。我們所提出的解碼方式把LDPC碼的同位檢查矩陣H分解成相同的同位檢查矩陣Hl ，再利用序列方式做解碼，所以非本質數值可以被同位檢查矩陣Hl 之間使用。因此，我們所提出的解碼演算法可以降低疊代次數，與傳統的Message Passing Algorithm比較可降低40%疊代次數即達到相同的BER(Bit Error Ratio)。我們使用部分平行積體電路架構實現解碼演算法，我們所設計積體電路解碼器使用我們的演算法架構可以提升系統輸出吞吐量。另外，只需要儲存Check-to-Variable的訊息，所以可以降低記憶
體的使用量。

關鍵字

低密度偶校碼 ； 奇偶檢查矩陣 ； 超大型積體電路

並列摘要

In this thesis, we propose a modified iterative decoding algorithm to decode a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes such as QC-LDPC codes used in the IEEE 802.16e standards. The proposed decoding is implemented by serially decoding block codes with identical parity-check matrix Hl derived from the parity-check matrix H of the QC-LDPC codes. The dimensions of Hl are much smaller than those of H. Extrinsic values can be passed between these block codes since the code bits of these block codes are overlapped. Hence, the proposed decoding can reduce the number of iterations required by up to forty percent without error performance degradation as compared to the conventional message passing algorithm. A partially-parallel very large-scale integration (VLSI) architecture is proposed to implement such a decoding algorithm. The proposed VLSI decoder can fully take advantage of the proposed decoding to increase its throughput. In addition, the proposed decoder only needs to store check-to-variable messages and hence is memory efficient.

並列關鍵字

LDPC ； Parity Check Matrix ； VLSI

參考文獻

[2]D. J. C. MacKay,“Good Error-Correcting Codes based on Very Sparse Matrices, ＂IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 399-431, Jan. 1999.

[5]I.C. Park and S.H. Kang, “Scheduling algorithm for partially parallel architecture of LDPC decoder by matrix permutation,＂in Proc. IEEEISCAS,pp. 5778-5781, May 2005

[6]Hao Zhong; Tong Zhang;“Block-LDPC: A Practical LDPC Coding System Design Approach,＂IEEE Transactions on Circuit and Systems--I: regular papers, Vol. 52, No. 4, pp.766-775 , April 2005

[8]T. Zhang and K. K. Parhi, “Joint (3, k)-regular LDPC code and decoder/encoder design,＂to appear IEEE Transactions on Signal Processing,Vol. 52, NO. 4,pp 1065-1079 ,April 2004

[10]T. Zhang and K. K. Parhi,“A 54 MBPS (3, 6)-regular FPGA LDPC decoder, ＂in Proc. IEEE Int. Symp. Information Theory, pp 127-132, Oct. 2002