使用任務安排演算法所實現之適用於WiMAX規範的低複雜度全模態低密度奇偶檢查碼編碼及解碼器

Processing-task Arrangement for a Low-complexity Full-mode WiMAX LDPC Codec

汪宇倫(Yu-Luen Wang)

指導教授 ： 翁詠祿

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

摘要

LDPC codes have been discovered as a powerful class of error control codes in a variety of communication applications. However, for applications demanding different levels of code rates and code lengths, there is a challenge in realizing a low-complexity multi-mode LDPC decoder. In this thesis, we propose dividing the decoding operations of a variety of irregular quasi-cyclic (QC) low-density parity-check (LDPC) codes into several smaller tasks. An algorithm is devised in order to arrange these tasks in a similar form such that a highly reusable multi-mode architecture can be designed to process these tasks. For this task-based decoder, the associated memory access can be accomplished with the help of the proposed address generators and two routing networks. Using these approach, the difficulty in designing a low-complexity multi-mode decoder, which is capable of supporting a variety of irregular QC-LDPC codes, can be overcome. In addition, layered encoding that enables the routing networks and memory for decoding to be reused for the encoding, and an early termination circuit which shares the same hardware resources with encoder, are also proposed. The encoding functions can thus be included with very low additional increase in chip area. Using the above techniques, a multi-mode codec architecture which can support both encoding and decoding functions for all 114 WiMAX LDPC codes is designed and implemented in a 90-nm 1P9M process. The full-mode WiMAX codec architecture achieves a moderate encoding (decoding) throughput of 800 Mb/s (200 Mb/s) and occupies an area of only 0.679 mm^2 at operation frequency of 400 MHz.

關鍵字

低密度奇偶檢碼

並列摘要

低密度奇偶檢查(Low-density parity-check, LDPC)碼為一類具有強大改錯能力的錯誤更正碼，且已被應用於多種通訊傳訊中。然而在需要多碼率及多碼長的應用中，實現一個低複雜度且能支援多種模式的低密度奇偶檢查碼解碼器仍然是一個困難的挑戰。在這篇論文中，我們提出了一種任務安排的方法，可將類循環低密度奇偶檢查(QC-LDPC)碼的解碼運算細切為數個較小的運算集合，稱為任務。任務安排演算法可將各種不同定義的類循環低密度奇偶檢查碼的解碼運算細切為較小且相似的任務，進而實現一可被高度重覆使用的任務運算器進行解碼運算。基於任務安排演算法所定義的任務以及任務運算器，我們也提出用於控制記憶體存取的位址產生器，以及運算單元中的二階搜尋器的實現方法。使用這些技術，我們完成一低複雜度且支援多種不同規範循環低密度奇偶檢查碼解碼運算的多模態解碼器。此外，我們也提出重覆使用解碼器的記憶體及繞線網路來達成階層編碼運算的方法，以及和編碼電路共用硬體資源的提前終止電路，於是編碼運算能夠在僅增加非常少量的複雜度後被支援。綜合以上的方法，我們設計了一個可支援WiMAX規範中共114種不同的類循環低密度奇偶檢查碼的編碼及解碼器電路。此電路晶片在90奈米製程實現下，核心面積僅有0.679 $mm^2$，且在操作頻率為400 MHz時最高可到達到800Mb/s的編碼吞吐量及200 Mb/s的解碼吞吐量。

並列關鍵字

LDPC code ； WiMAX ； Error correction code ； LDPC decoder ； LDPC encoder

參考文獻

[2] R. Gallager, “Low-density parity-check codes,” IRE Trans. Inf. Theory,

[3] D.-J.-C. MacKay, “Good error-correcting codes based on very sparse matrices,”

IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 399-431, March 1999.

Design, Automation and Test, pp. 216-219, April 2008.

[5] I. Ahmed and T. Arslan, “VLSI design of multi standard turbo decoder