針對高碼率之類循環低密度奇偶校驗碼的低複雜度階層式解碼器

A Reduced-Complexity Layered Decoder Architecture for High Rate QC-LDPC Codes

胡鈞凱(Jyun-Kai Hu)

指導教授 ： 翁詠祿

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

摘要

傳統上低密度奇偶校驗碼(low-density parity-check code, LDPC code)的階層式解碼器 (layered decoder) 通常在校驗節點 (check node) 會採取循序 (serial) 而非平行的計算以降低面積成本，但這樣一來，我們會需要一個額外的記憶體空間去暫存變數節點 (variable node) 傳至校驗節點的訊息，而在高碼率的規格下，這樣的一塊記憶體空間會佔據不小的面積。針對以上的問題，本文提出了一種重新安排處理流程的階層式解碼器架構，且不需儲存對數似然比 (log-likelihood ratio)，取而代之的是儲存變數節點傳至校驗節點的訊息，同時也不需要額外的儲存空間去為了在校驗節點計算整個階層之後立刻更新相鄰變數節點的對數似然比。除此之外，本文也討論了有關排程 (scheduling) 與資源綁定 (resource binding) 的三種方法來解決存在於文中架構的記憶庫衝突 (bank conflict)。對於碼率0.9碼長4 kB的類循環 (quasi cyclic) 低密度奇偶校驗碼，在不造成錯誤率增加的前提之下，約可以減少百分之二十二的解碼器面積。最後以90奈米互補式金屬氧化物半導體 (complementary metal-oxide-semiconductor, CMOS) 製程實作出面積為6.46平方毫米的類循環低密度奇偶校驗碼階層式解碼器，並可達到每秒5.87 Gb的吞吐量 (throughput)。

關鍵字

低密度奇偶校驗碼 ； 記憶庫衝突 ； 三著色問題 ； 排程

並列摘要

The conventional layered decoder for LDPC codes usually adopt serial check node units to reduce the area cost, but this way requires an additional variable-to-check (V2C) FIFO and the area of this FIFO may be very large when high rate codes are used. This thesis presents a decoder architecture by rearranging the processing order, and the proposed layered decoder stores V2C extrinsic information instead of log-likelihood ratio (LLR) values. No additional FIFO is required for the updating after the serial operation. In addition, three methods about scheduling and resource binding are discussed to resolve the bank conflict of the proposed decoder architecture. For the LDPC code with the code length 4 kB and the code rate 0.9, approximate 22% of the total area is reduced without performance loss. After implemented in 90-nm CMOS process, the proposed LDPC decoder can achieve a throughput of 5.87 Gb/s with an area of 6.46 mm².

並列關鍵字

LDPC code ； bank conflict ； 3-coloring ； scheduling

參考文獻

[1] D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electron. Lett., vol. 32, no. 18, pp. 1645–1646, 1996.

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

[3] Z. Li, L. Chen, L. Zeng, S. Lin, and W. H. Fong, “Efficient encoding of quasi-cyclic low-density parity-check codes,” IEEE Trans. Commun., vol. 54, no. 1, pp. 71–81, 2006.

[5] “IEEE Standard for Air Interface for Broadband Wireless Access Systems.” IEEE-SA, 2012.

[7] J. Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 1988.