適用於前瞻通訊系統的半循環低密度奇偶校驗解碼器之演算法與硬體架構設計

Algorithms and Architectures of QC-LDPC Decoder Designs for Advanced Communication Systems

施信毓(Xin-Yu Shih)

指導教授 ： 吳安宇

國立臺灣大學/電機資訊學院/電機工程學研究所/博士(2010年)

https://doi.org/10.6342/NTU.2010.02683

摘要

低密度奇偶校驗編碼是一種通道編碼技術，最早是由Robert Gallager博士在1962年發表，並且被證實具有最佳的錯誤更正能力。經過了三十多年後，由MacKay博士重新發現並加以研究。而隨著先進超大型積體電路製程的演進，低密度奇偶校驗編碼技術再度引起人們的興趣與研究。由於低密度奇偶校驗編碼的解碼效能甚至超越了前一代的渦輪碼，它已漸漸成為現今先進通訊系統中重要的前饋式錯誤更正碼模組。因此，為了不同的電路設計考量，在硬體層級上，我們設計了三顆低密度奇偶校驗的解碼器，並呈現個別的量測結果。除此之外，在演算法層級上，為了適用於多模式的設計，我們也提出了通用矩陣合併演算法。
1) 適用於IEEE 802.11n通訊系統的高效能且面積有效化之(1944, 972)低密度奇偶校驗解碼晶片:在後段晶片設計上，為了達到高效能和面積有效化的特性，我們提出了「有效率棋盤格佈局規劃策略」。除此，我們也提出了三種設計技巧，包含「兩階段群組比較」、「動態字長分配」和「資料封包策略」。利用TSMC 0.13um製程來實作，最高量測頻率為111.1MHz，平均功率消耗為76mW。整體特色有低面積成本、低功率消耗、重要路徑運算時間的縮短、解碼效能的改進和解碼吞吐量的提升。
2) 適用於IEEE 802.16e通訊系統的19種模式之低密度奇偶校驗解碼晶片:我們提出了多模式的低密度奇偶校驗解碼器設計之硬體架構。除外，我們也發展了三種設計技巧，包含「基本解碼矩陣重排」、「運算單元重疊運算」和「軟決定式提早解碼策略」。透過TSMC 0.13um製程來實現，最高量測頻率為83.3MHz，平均功率消耗為52mW。整體特色為較小的晶片面積、較高的硬體使用率、較短的總解碼時間、有彈性的解碼吞吐量和較低的功率消耗。
3) 適用於下一代可適性通道通訊系統的可即時重組且多碼率之低密度奇偶校驗解碼晶片:可即時重組的硬體架構可以讓使用者即時下載想要解碼的矩陣，不僅如此，我們所提出的三種設計技巧包含「分割群組比較」、「可適性字長分配」和「可適性通道的提早解碼策略」。架構在有效率棋盤格佈局規劃策略之上，更提出「類矩陣記憶體佈局擺放方法」，來提升核心面積的使用率，以及降低功率與能量的消耗。在晶片實作上，藉由TSMC 0.13um製程，最高量測頻率為125MHz，平均功率消耗為58mW。整體特色是可即時重組特性、重要路徑運算時間的縮短、解碼效能的改進、總解碼時間的縮短、低面積成本和低功率與能量的消耗。
4) 適用於多個差異性大解碼矩陣的多模式設計之通用矩陣合併演算法:面對多模式的低密度奇偶校驗解碼器設計，它可以有效率地減少繞線複雜度。在多個差異性大的解碼矩陣間，我們可以找出最佳的解決方法來最小化硬體的多付出成本。除此之外，我們可以拿IEEE 802.11n通訊系統中三個不同的解碼矩陣當作設計範例，並呈現此演算法的優異所在。
總而言之，在本論文中，針對現今先進通訊系統的不同設計考量，所提出低密度奇偶校驗解碼器的演算法和硬體架構設計，可以透過設計範例來加以驗證之。

關鍵字

低密度奇偶校驗編碼

並列摘要

Low-Density Parity-Check (LDPC) Codes are one kind of channel coding schemes. They were first introduced by Gallager in 1962, and verified to own the best error-correcting capabilities. After three decades, LDPC Codes were rediscovered by Dr. MacKay. As the advanced VLSI technology proceeds, the interests in LDPC Codes have been dramatically increased because of their excellent error-correcting performance. Even the decoding performance of LDPC Codes is much better than that of Turbo Codes. It becomes feasible to implement LDPC Codes as the kernel Forward Error Correction (FEC) module in the modern advanced communication systems. Hence, for different circuit design considerations, we develop three LDPC decoder chips with measurement results in the hardware architecture level. Besides, in the algorithm level, we also propose a universal matrix-merging algorithm for accommodating multi-mode design.
1) A high-performance cost-effective (1944, 972) LDPC decoder chip for IEEE 802.11n system: In order to achieve high-performance cost-effective characteristic, Efficient Checkerboard Layout Scheme (ECLS) is proposed for the back-end chip design. Also, it is developed with three design techniques, such as Two-Stage Group Comparison (TSGC), Flexible Wordlength Assignment (FWA), and Data Packet Scheme (DPS). The chip in TSMC 0.13um CMOS technology can be measured at 111.1 MHz with 76 mW. It features low area cost, low power dissipation, critical path shortening, decoding performance improvement, and throughput enhancement.
2) A 19-mode LDPC decoder chip for IEEE 802.16e system: We propose the multi-mode hardware architecture of the LDPC decoder design. Besides, we also develop three design techniques, including Base-Matrix Reordering (BMR), CNU/BNU Overlapped Operations (CBOO), and Soft-Decision Early Termination Scheme (SD-ETS). Via TSMC 0.13um CMOS technology, the chip is measured at 83.3 MHz with 52 mW. Its benefits are smaller chip area, higher hardware utilization, lower decoding latency, flexible decoding throughput, and lower power consumption.
3) A run-time reconfigurable multi-rate LDPC decoder chip for next-generation channel-adaptive communication system: The run-time reconfigurable hardware architecture is proposed for the users to run-time download the desired parity check matrix. In addition, three developed design techniques are Divided-Group Comparison (DGC), Dynamic Wordlength Assignment (DWA), and Channel-Adaptive Early Termination Scheme (CA-ETS). Based on ECLS, Matrix-Like Memory Layout Placement (ML-MLP) is proposed to enhance core utilization and reduce power/energy consumption. In the ASIC chip implementation, by using TSMC 0.13um CMOS technology, the maximum frequency operates at 125 MHz and the power dissipates 58 mW in average. It can deliver run-time reconfigurable property, critical-path shortening, decoding performance improvement, decoding latency saving, small chip area, and low power/energy consumption.
4) A universal matrix-merging algorithm for accommodating multi-mode design with very different parity check matrices: It is used to efficiently reduce wiring complexity of a multi-mode LDPC decoder design. Among very different parity check matrices, we can find out the optimal solutions to minimize the hardware overhead with respect to a single-mode design. Additionally, we would use three different parity check matrices with code rate of 1/2 defined in IEEE 802.11n system for demonstrating the design examples with its benefits.
In summary, for various design considerations in the modern advanced communication applications, the proposed algorithms and architectures of the LDPC decoder designs are verified with demonstrated design examples in this dissertation.

並列關鍵字

LDPC Codes

參考文獻

[15] C. C. Lin, K. L. Lin, H. C. Chang, and C. Y. Lee, “A 3.33Gb/s (1200,720) Low-Density Parity-Check Code Decoder,” in 31th European Solid-State Circuits Conf. (ESSCIRC), Grenoble, France, September 2005, pp.211–214.

[1] R. Gallager, “Low-Density Parity-Check Codes,” IRE Trans. Inf. Theory, vol. 7, pp. 21–28, Jan. 1962.

[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.

[3] D. J. C. MacKay, and R. M. Neal, “Near Shannon Limit Performance of Low Density Parity Check Codes,” Electron. Lett., vol. 33, no. 6, pp. 457–458, Mar. 1997.

[4] T. J. Richardson, and R. L. Urbanke, “The Capacity of Low-Density Parity-Check Codes under Message-Passing Decoding,” IEEE Trans. Inform. Theory, vol. IT-47, pp. 599–618, Feb. 2001.