An Efficient Layered Decoding Architecture Using Selective Algorithm for Non-Binary QC-LDPC Codes

適用於非二位元類循環低密度奇偶檢查碼的使用選擇式演算法之有效分層解碼架構

梁振業(Chen-Yap Leong)

指導教授 ： 翁詠祿

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

摘要

Low-density parity check (LDPC) codes have attracted tremendous research interest and many recent communication standards have included LDPC codes, but most of the recent applications are focused only on binary LDPC codes, applications about nonbinary LDPC codes are very limited due to its decoding complexity. In this thesis, a decoder architecture for nonbinary QC-LDPC codes is presented, this decoder architecture is flexible for nonbinary LDPC codes with quasicyclic form. The multiplication over Galois field is efficiently handled through a proposed permutation network for the check node processing. With a proposed filtering method combining with an efficient Minimum Finder architecture, a selective-input implementation for decoding of nonbinary LDPC codes is employed in the architecture design, which can increase the throughput. In order to increase the convergence speed, hence, reduce the numbers of iteration required for achieving a given performance, decoding of nonbinary LDPC codes with layered scheduling is also considered in our architecture design. Using a UMC 90-nm CMOS process, we implement a decoder for (248, 137) nonbinary LDPC code over GF(32) for demonstrating our ideas.

關鍵字

非二位元類循環低密度奇偶檢查碼 ； 解碼架構 ； 選擇式演算法

並列摘要

低密度奇偶檢查碼(LDPC codes)已經在各種不同的應用中引起了大家廣泛的研究興趣，並且也被不少的通訊標準所引用與討論，但是大部份目前所涉及到的應用與通訊標準都僅集中於二位元的低密度奇偶檢查碼的討論，而非二位元低密度奇偶檢查碼因為受限於它的解碼複雜度和在硬體實現上的難度，所以目前甚少被提及。但是，非二位元低密度奇偶檢查碼的高效解碼性能卻引起了我們的研究興趣。在本篇論文中，我們提出了一個非二位元類循環低密度奇偶檢查碼的解碼架構，此解碼架構對於任何非二位元類循環低密度奇偶檢查碼都有很高的適應性。在解碼架構中，我們所提出的旋轉網路(permutation network)架構有效的處理了在檢查點(check node)運算中涉及到伽羅瓦代數體(Galois field)的乘法運算，因此大量的減少了硬體架構中在處理乘法運算所需要付出的複雜度。另外，我們也提出了一個最小尋找器的硬體架構，此最小尋找器架構結合所規劃的過濾方法，我們在解碼架構中實現了非二位元類循環低密度奇偶檢查碼的選擇式演算法，進而減少檢查點運算中所需要的處理時間，提高吞吐量。此外，有鑒於希望加快解碼的收斂速度而減少欲達到相同解碼性能所需要的疊代次數，在我們的解碼架構中也引用了分層解碼的方式。最後，我們使用UMC 90-nm CMOS製程實現了一個(248,137),在GF(32)下的非二位元低密度奇偶檢查碼解碼架構來展示我們的構想。

並列關鍵字

nonbinary quasicyclic low-density parity check (QC-LDPC) codes ； Min-Max decoding algorithm ； very-large-scale integration (VLSI) architecture

參考文獻

[1] R. G. Gallager, Low density parity check codes," IRE Trans. Inform.

[2] M. C. Davey and D. J. C. Mackay, Low-density parity check codes over

[3] C. Spagnol and W. Marnane, A class of quasi-cyclic LDPC codes over

structions of nonbinary quasi-cyclic LDPC codes: a ¯nite ¯eld approach,"

IEEE Trans. Commun., vol. 56, no. 4, pp. 545-554, Apr. 2008.