吳安宇臺灣大學：電子工程學研究所詹承洲Zhan, Cheng-ZhouCheng-ZhouZhan2007-11-272018-07-102007-11-272018-07-102007http://ntur.lib.ntu.edu.tw//handle/246246/57362在新一代的通信標準中，有不少系統都採用低密度奇偶校驗編碼(low-density parity-check, LDPC)，舉凡IEEE 802.16e(mobile WiMAX)、IEEE 802.11n以及百億位元傳輸系統(10GBase-T)皆為此類。對於通道解碼器速度的要求也越來越大，從IEEE 802.16e的每秒數十百萬位元，到IEEE 802.11n的每秒數億位元，甚至是10GBase-T系統的每秒百億位元，都顯示了對速度上更進一步的要求。為了增加傳輸的可靠性，低密度奇偶校驗編碼(low-density parity-check, LDPC)成為通訊系統中極為重要通道編碼(channel coding)的模組，提供更強大的錯誤更正能力。 低密度奇偶校驗編碼最早是由Robert Gallager博士在1962年於其博士論文中發表，並且已被證實具有極為優越的性能。然而當時的科技卻無法實現這種編碼系統，也就逐漸被人們所遺忘。直到三十多年後，隨著超大型積體電路的製程不斷的演進，要實現低密度奇偶校驗編碼已不再是不可能的任務，才再度引起人們廣泛討論與研究。 本論文的目標是在支援單模IEEE 802.11n標準的無線通訊系統下，針對編碼器，利用簡單的邏輯電路來實現硬體；針對解碼器，提出一套有效率的設計流程，透過基本矩陣的行列重排、運算單元的重疊運算和提早結束機制等，設計出具有彈性化的硬體架構，其優點是縮小晶片的面積、提高硬體的使用率、縮短解碼所花費時間、彈性調整解碼的吞吐量和低功率的消耗。 在硬體實作上，透過標準單元的設計流程，利用TSMC 0.13um的先進製程來實現符合IEEE 802.11n單模之低密度奇偶校驗編碼的編解碼器，所實現的晶片面積為2.65mm×2.65mm。In modern communication systems, the low-density parity-check (LDPC) codes are adopted in several ones, such as IEEE 802.16e (mobile WiMAX), IEEE 802.11n, and 10GBase-T system. The demand for speed of the channel decoder grows from the tens of Mbps of IEEE 802.16e standard, hundreds of Mbps of IEEE 802.11n standard, to 10 Gbps of 10GBase-T system. This indicates that the need for the speed of the channel decoder is growing rapidly. To increase the reliability of the transmission, LDPC codes have become an important channel-decoding module in the communication systems. LDPC codes are first discovered by Dr. Galleger in 1962, and are proved to have great abilities for channel decoding. The technology in 1962 was not advanced enough to support these complex designs of LDPC codes, and it was rediscovered in the late 19 century. The goal of this thesis is to propose several techniques to improve the throughput, hardware utilization efficiency (HUE), and an early termination scheme to reduce the decoding latency. In hardware implementation, we will construct a simplified LDPC encoder suitable for the IEEE 802.11n standard, and construct the LDPC decoder by using the techniques mentioned in this thesis to prove the feasibility of our algorithms and techniques. We use the 0.13 technology of the cell-based design flow to implement our LDPC-codec chip suitable for single-mode IEEE 802.11n standard, and the chip area is 2.65mm×2.65mm.List of Figures xi List of Tables xvi Chapter 1 Introduction..................................................................1 1.1 Introduction.........................................................................................1 1.2 Motivation & Goal...............................................................................3 1.3 Thesis Overview...................................................................................6 Chapter 2 Low Density Parity-check Codes................................7 2.1 Error Correction Codes......................................................................7 2.1.1 Overview of the Error Correction Codes.......................................7 2.1.2 Block and convolutional codes......................................................9 2.2 Definition of LDPC Codes................................................................10 2.2.1 Encoders of LDPC Codes............................................................12 2.2.2 Decoders of LDPC Codes............................................................15 2.3 Decoding Algorithms.........................................................................17 2.3.1 Sum-Product Algorithm..............................................................17 2.3.2 Min-Sum Algorithm....................................................................20 Chapter 3 VLSI Implementation for LDPC Encoder Design..22 3.1 Parity check matrix in IEEE 802.11n standard..............................22 3.2 Hardware Implementation for Encoding Algorithm.....................23 Chapter 4 Proposed Two Techniques for Enhancing Hardware Efficiency 26 4.1 Matrix Reordering Algorithm..........................................................26 4.1.1 Introduction to LDPC Matrix Reordering...................................26 4.1.2 Proposed Matrix Reordering Algorithms....................................32 4.2 Overlapped Information Passing for Partially-parallel Quasi-Cyclic LDPC Codes...........................................................................................42 4.2.1 Overlapped Message Passing Decoding and State of the Art......42 4.2.2 Proposed Partially-Parallel and Overlapped Message Processing for QC-LDPC Codes....................................................................................................45 Chapter 5 The Early Termination Scheme................................54 5.1 Introduction to the Early Termination............................................54 5.2 Mechanism of Early Termination Schemes....................................55 5.2.1 Conventional Termination Schemes............................................55 5.2.2 Proposed Early Termination Scheme..........................................56 Chapter 6 VLSI Implementation of the LDPC Decoder Design 60 x 6.1 Decision of Word-length and Iteration Number.............................60 6.2 Bit Node Unit Design.........................................................................62 6.3 Check Node Unit Design...................................................................63 6.4 Critical Path Shortening Technique................................................64 6.4.1 The Critical Path in the Conventional Design.............................64 6.4.2 Proposed Structure to Shorten the Critical Path..........................66 6.5 Information Re-allocation for Higher Throughput........................71 6.5.1 Introduction to the Information Allocated in the Memory..........71 6.5.2 Proposed New Information Allocating Method in the Memory..72 Chapter 7 Chip Implementation.................................................75 7.1 Cell-based Design Flow.....................................................................75 7.1.1 C Model and Simulation..............................................................75 7.1.2 RTL Coding.................................................................................75 7.1.3 RTL Simulation...........................................................................76 7.1.4 Synthesis......................................................................................76 7.1.5 Gate-level Simulation..................................................................76 7.1.6 DFT..............................................................................................76 7.1.7 ATPG...........................................................................................77 7.1.8 Scanned Gate-level Simulation....................................................77 7.1.9 Place and Route...........................................................................77 7.1.10 DRC & LVS................................................................................78 7.1.11 Post-layout Gate-level Simulation...............................................78 7.2 Experimental Result..........................................................................78 7.3 Comparison........................................................................................81 Chapter 8 Conclusions.................................................................83 References 851333944 bytesapplication/pdfen-US低密度吞吐量奇偶校驗碼效率無線通訊LDPCthroughputefficiencyIEEE 802.11nwirelessthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/57362/1/ntu-96-R94943111-1.pdf