吳安宇臺灣大學：電子工程學研究所施信毓Shi, Xin-YuXin-YuShi2007-11-272018-07-102007-11-272018-07-102006http://ntur.lib.ntu.edu.tw//handle/246246/57294在新一代IEEE 802.16e標準的無線通訊系統中，除提供定點通訊的操作模式外，更增加有限的可移動性，尤其是在車速移動下進行高速率資料傳輸和提供語音功能。除此，其特色是能涵蓋更遠的傳輸距離、提供更大的頻寬，以及提升頻帶使用率。為了增加傳輸的可靠性，低密度奇偶校驗編碼(low-density parity-check, LDPC)成為IEEE 802.16e標準中極為重要通道編碼(channel coding)的模組，提供更強大的錯誤更正能力。 低密度奇偶校驗編碼最早是由Robert Gallager博士在1962年於其博士論文中發表，並且已被證實具有極為優越的性能。然而當時的科技卻無法實現這種編碼系統，也就逐漸被人們所遺忘。直到三十多年後，隨著超大型積體電路的製程不斷的演進，要實現低密度奇偶校驗編碼已不再是不可能的任務，才再度引起人們廣泛討論與研究。 本論文的目標是在支援IEEE 802.16e標準的無線通訊系統下，針對編碼器，利用簡單的邏輯電路來實現硬體；針對解碼器，提出一套有效率的設計流程，透過基本矩陣的行列重排、運算單元的重疊運算和提早結束機制等，設計出具有彈性化的硬體架構，其優點是縮小晶片的面積、提高硬體的使用率、縮短解碼所花費時間、彈性調整解碼的吞吐量和低功率的消耗。 在硬體實作上，透過標準單元的設計流程，利用TSMC 0.13um 1P8M的先進製程來實現低密度奇偶校驗編碼的編解碼器。所實現的晶片有二：首先是編解碼器，可提供三種不同的操作模式，分別是單純編碼、單純解碼和同時編解碼等功能；實現的晶片面積為2.91mm×2.91mm。其次是多模式解碼器，可提供19種不同的操作模式，分別適用於19種不同的編碼長度；實現的晶片面積為2.88mm×2.88mm。IEEE 802.16e standard, one of the advanced wireless communication systems as known as WiMAX, not only offers the static transmission, but also provides the limited mobility, especially for the applications of high data-rate transmission and voice communication at moving vehicles. In addition, it can cover larger transmission area, provide larger communication bandwidth and enhance bandwidth utilization. In order to increase transmission reliability, Low-density parity-check (LDPC) codes, which possess powerful error-correcting ability, become the important module of channel coding for IEEE 802.16e standard communication system. LDPC codes were first introduced by Gallager in 1962 and were verified to possess superior properties in error-correcting field. Unfortunately, the past technology in 1960s wasn’t advanced enough to support their hardware implementation complexity. Therefore, LDPC codes weren’t widely discussed at that time and were left behind little by little. After three decades, it wasn’t an impossible mission to implement LDPC codes with the progress of the advanced VLSI technology. Therefore, the interests in LDPC codes were dramatically increased day by day. The goal of the thesis is to give the delicate solutions for IEEE 802.16e standard communication system. At the aspect of encoders, the hardware realization can be implemented by the simple combinational circuits. On the other hand, an efficient design flow can be adopted with reordering of the base matrix, overlapped operations of key components and early termination strategy. The advantages are area reduction of die size, enhancement of hardware utilization, reduction of decoding latency, dynamic adjustment of decoding throughput and low power consumption. In hardware implementation, our LDPC codec and multi-mode decoder design are both implemented in TSMC 0.13-um 1.2-V CMOS process with eight levels of metal. In our codec design, we can provide triple modes, including only encoding mode, only decoding mode and concurrent encoding and decoding mode. The die size is 2.88mm×2.88mm giving a total area of 8.29 mm2. In our multi-mode decoder design, we can provide 19 kinds of operating modes, including block sizes of 576, 672, …..., 2208, 2304. The die size is 2.91mm×2.91mm giving a total area of 8.47 mm2.Abstract ........................................................................................xxxi Table of Contents ........................................................................xxxiii List of Figures ..............................................................................xxxv List of Tables ................................................................................xxxix Chapter 1 Introduction ...............................................................1 1.1 Introduction ..........................................................................................1 1.2 Motivation & goal ................................................................................3 1.3 Thesis organization ..............................................................................6 Chapter 2 Low-density parity-check codes ..............................9 2.1 Error correction codes ..........................................................................9 2.2 Definition of LDPC codes ...................................................................11 2.3 Quasi-cyclic LDPC codes (QC-LDPC) ...............................................13 2.4 Encoders of LDPC codes .....................................................................15 2.5 Decoders of LDPC codes .....................................................................19 Chapter 3 Decoding algorithm ..................................................21 3.1 Sum-Product Algorithm .......................................................................21 3.1.1 Simulation environment ............................................................24 3.1.2 Simulation of different block lengths .......................................25 3.2 Min-sum algorithm ..............................................................................28 3.3 Fixed-point min-sum algorithm ...........................................................30 Chapter 4 VLSI implementation for LDPC encoder design ..33 4.1 Parity check matrix in IEEE 802.16e standard ....................................33 4.2 Hardware implementation for encoding algorithm ..............................34 4.2.1 Characteristics of inverse matrix of T .......................................35 4.2.2 Block diagram for LDPC encoder design .................................36 Chapter 5 Design flow for LDPC decoder design ....................41 5.1 Design flow for decoding algorithm ....................................................41 5.1.1 Reordering of the base matrix ...................................................42 5.1.2 Overlapped operations of BNUs and CNUs .............................46 5.1.3 Early termination strategy .........................................................50 5.2 Simulation of early termination strategy ..............................................53 5.3 Comparison of different decoding algorithms .....................................57 Chapter 6 VLSI implementation for LDPC decoder design ..59 6.1 Determination of word lengths for mutual information .......................59 6.2 Architecture for CNUs .........................................................................60 6.3 Architecture for BNUs .........................................................................64 6.4 Block diagram for LDPC decoder design ............................................67 Chapter 7 Chip implementation ................................................71 7.1 Cell-based design flow .........................................................................71 7.1.1 C model and simulation ............................................................72 7.1.2 Verilog-HDL design -- RTL coding ..........................................72 7.1.3 RTL simulation .........................................................................73 7.1.4 Synthesis ...................................................................................73 7.1.5 Gate-level Simulation ...............................................................74 7.1.6 DFT ...........................................................................................74 7.1.7 ATPG .........................................................................................74 7.1.8 Scanned Gate-level Simulation .................................................75 7.1.9 Place and Route .........................................................................75 7.1.10 DRC & LVS ............................................................................76 7.1.11 Post-layout Gate-level Simulation ..........................................76 7.2 LDPC codec design ..............................................................................76 7.3 Multi-mode LDPC decoder design ......................................................80 7.4 Comparison ..........................................................................................83 Chapter 8 Conclusions ................................................................85 References .......................................................................................873997277 bytesapplication/pdfen-US低密度奇偶校驗編碼無線都會網路全球微波存取互通介面LDPC codesIEEE 802.16eWiMAXthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/57294/1/ntu-95-R93943027-1.pdf