適用於可移動式WiMAX 通訊之低面積複雜度的低密度奇偶檢查碼解碼器

An LDPC decoder with low area complexity for mobile WiMAX

吳宗晟(Zong-Cheng Wu)

指導教授 ： 翁詠祿

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

摘要

在這篇論文中, 我們提供了一個兩層式的比較器, 並且將這個比較器使用於之前的所提出的類循環低密度奇偶檢查碼解碼的架構之上, 用來縮短IEEE 802.16e standard 的類循環低密度奇偶檢查碼(QC-LDPC) 的解碼時間, 且使用這種比較器不至於增加過多的硬體面積。相較於之前的硬體架構，能夠減少33%的比較週期，而面積的耗費幾乎與之前相等。解碼器的硬體實現是依序地對相似的奇偶檢查矩陣的子矩陣Hl 來做解碼的運算, 而Hl 則是從類循環低密度奇偶檢查碼的奇偶檢查矩陣H 所衍生出來的子矩陣，Hl的數量則和字碼的長度成正比。在整個電路解碼的過程中，非本質的數質(Extrinsic values) 可以在經由這些子矩陣在奇偶檢查位置的重疊結構來做訊息的交換。因為Hl是奇偶檢查矩陣H 的子矩陣，所以Hl 的維度遠小於H, 以至於在硬體的實作上, 電路互相連接的複雜度也可因此而降低許多。另外, 我們伴隨著使用兩層式的比較器, 將原本所須要的比較週期數從3減少到2，有33%的減少，而面積部分幾乎沒有而外的增加。另外, 我們配合著管線化的技巧地使用來增加整個解碼的吞吐量，而且因為有做管線化的處理，可以使整個解碼器整個硬體的使用率大大地增加。藉此, 可以提供一個符合吞吐量要求(30Mbps)具有低面積及低複雜度的解碼硬體, 且適用於多種不同長度的低密度奇偶檢查碼的解碼器。

關鍵字

低密度奇偶檢查碼 ； 解碼器 ； 超大型積體電路 ； 最小和演算法 ； HASH(0x1db3cf00)

並列摘要

In this thesis, we propose a computing unit, i.e., two-stage comparator, to accelerate the decoding of quasi-cyclic low-density parity-check (QC-LDPC) codes used in the IEEE 802.16e standards based on a previously proposed decoding
architecture but with small parallelism. The decoding is implemented by sequentially decoding block codes with identical parity-check matrix Hl derived from the parity-check matrix H of the QC-LDPC code. Extrinsic values
are exchanged among these block codes since the code bits of block codes are overlapped. Since the dimensions of Hl are much smaller than those of H, the complexity of interconnection can be reduced. With the proposed two-stage
comparator, the number of cycles of comparison is reduced. In addition, a pipeline architecture is used to increase the decoding throughput. The proposed decoder has low area complexity but with satisfactory throughput and the scalability to support LDPC codes with various lengths.

並列關鍵字

LDPC code ； decoder ； VLSI ； min-sum algorithm ； IEEE 802.16e standard

參考文獻

[1] R. Gallager, ”Low-density parity-check Codes,” IRE Trans. Inf. Theory,

[2] D. Mackay, “Good error-correcting codes based on very sparse matrices,”

IEEE Trans. Inform. Theory, vol. 45, no. 2, pp. 399-431, Mar. 1999.

[3] Part 16: Air interface for fixed and mobile broadband wireless access systems

amendment for physical and medium access control layers for combined