吳安宇臺灣大學：電子工程學研究所李芳明Li, Fan-MinFan-MinLi2007-11-272018-07-102007-11-272018-07-102007http://ntur.lib.ntu.edu.tw//handle/246246/57547在先進的前向錯誤更正碼（Forward Error Correction, FEC）標準 堙A同時採用了迴旋碼和渦輪碼的編碼方法，所以我們需要一個可重置的錯誤更正解碼設計。此外，渦輪解碼是藉由疊代運算完成，為了降低它所造成的電源消耗和時間延遲，我們需要一個可以依據通訊環境的好壞，而提早終止（Early Termination, ET）疊代運算的機制。在本論文中，我們提出了一個整合型錯誤更正解碼器，針對了可動態運算和可重置的兩個特點而設計。 在之前的文獻裡，有很多關於疊代運算終止方法的研究，然而大部份的討論專注在可完成的解碼（假設接收端的資訊，已足夠在解碼過程中，分辨出傳送端的資訊）。在本論文中，藉由外部資訊轉移曲線（Extrinsic Information Transform, EXIT）圖，我們討論了解碼能力的極限。我們之後提出了一個資訊測量的方法，使用信號的相關性來預測解碼的極限值。另外，在解碼極限值的輔助下，我們提出了兩個疊代運算提早停止的方法（ET-I和ET-II）。當通道環境很好訊雜比高的時候，傳送的資訊很早就已解出，所以疊代運算可以提早停止（可完成的解碼）；另一方面，當通道環境很壞訊雜比低的時候，干擾已超出解碼器的能力極限，所以疊代運算亦可以提早停止（無法完成的解碼）。電腦模擬顯示，ET-I方法幾乎不會影響位元錯誤率，而ET-II方法亦能滿足系統規定。 在可重置的設計裡，我們首先有系統的分析Viterbi演算法和MAP演算法的時序圖。接著我們介紹可以在時序圖作變化的三種技巧︰「分散」、「指標」、和「平行」。另外我們提出以基本運算單元作為基礎，分析時序圖的關鍵特性。經由時序的分析，我們發展了VA/MAP時序圖。藉著互補Viterbi和MAP解碼程序裡閒置的部份，使得VA/MAP時序圖具有三種運作模式（「VA模式」、「MAP模式」、和「共同VA/MAP模式」）。接著在硬體設計方面，我們建立了FEC運算核心。針對四種不同的應用狀況，使用著可以把FEC運算核心搭配適當的記憶體，完成一個完整的FEC解碼器（「單模式迴旋解碼器」、「單模式渦輪解碼器」、「雙模式迴旋渦輪解碼器」、和「三模式迴旋渦輪解碼器」）。最後，我們在台積電的0.18μm製程，驗證了3GPP應用的FEC運算核心硬體設計原型。To satisfy the advanced Forward-Error-Correction (FEC) standards, in which the Convolutional code and Turbo code may co-exit, a reconfigurable FEC decoder is needed. Moreover, to reduce the power and latency of the iterative Turbo decoding, an Early Termination (ET) mechanism, in which the FEC decoder can stop according to the channel environment, is needed. In this literature, we propose a unified FEC decoder that contains the features of the dynamic computation and reconfigurable function. Although many stopping methods of iterative decoding have been discussed in the literatures extensively, many of them only focus on the solvable decoding (information is enough for successful decoding). In this literature, we discuss the limitation of the decoding ability based on the extrinsic information transform (EXIT) chart. Then, we propose a new information measurement by using cross correlation to predict the decoding threshold. Moreover, we propose two early termination (ET) schemes (ET-I and ET-II) based on the predicted decoding threshold. The iterative decoding can stop in either high-SNR situations where the decoded bits are highly reliable (solvable decoding), or low-SNR situations where the decoder already has no capability to decode (unsolvable decoding). The simulation results show that the reduced iterations due to the ET-I scheme almost will not affect the BER performance, and the ones due to the ET-II scheme can still satisfy the requirement of the specification. For the reconfigurable design, we first systematically analyze the timing charts of both the Viterbi algorithm and the MAP algorithm. Then, three techniques, including Distribution, Pointer, and Parallel schemes, are introduced. Furthermore, we propose a tile-based methodology to analyze the key features of timing charts. On the basis of the timing analysis, we develop a VA/MAP timing chart that has three modes (VA mode, MAP mode, and concurrent VA/MAP mode) by complementing the idle time of both Viterbi and MAP decoding procedures. Then, we construct a triple-mode FEC kernel. By integrating the FEC kernel with different size of memory, we can construct a types of FEC decoders for different application scenarios, such as 1) stand-alone Convolutional decoder (VA mode), 2) stand-alone Turbo decoder (MAP mode), 3) dual-mode Convolutional/Turbo decoder (VA mode and MAP mode), and 4) triple-mode Convolutional/Turbo decoder (VA mode, MAP mode, and concurrent VA/MAP mode). Finally, a prototyping FEC kernel processor that is compliant to 3GPP standard is verified in TSMC 0.18-μm CMOS process.誌謝 I 中文摘要 II Abstract IV Contents VI List of Figures X List of Tables XIII Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation 4 1.2.1 Low Power and Latency 4 1.2.2 Multi-mode and Multi-spec 5 1.3 Design Concepts 6 1.3.1 Stopping Strategy 6 A. High-SNR Environment 6 B. Low-SNR Environment 8 1.3.2 Reconfigurable Strategy 11 A. Timing Association 12 B. Hardware Association 13 1.4 Organization 16 Chapter 2 Review of The FEC Decoding Algorithms and The Conventional Early Termination Schemes 17 2.1 Coding Flow 17 2.2 Decoding Algorithms 19 2.2.1 Viterbi Algorithm 19 2.2.2 Log-MAP Algorithm 20 2.2.3 Iterative Decoding 23 2.3 Conventional Early Termination Schemes 24 2.3.1 Soft Decision Rules 25 A. Cross-Entropy (CE) [26] 25 B. Mean-Estimate (ME) [28] 26 C. Updated Threshold [29] 27 D. A-priori LLR Measurement [30] 28 2.3.2 Hard Decision Rules 28 A. Sign-Change-Ratio (SCR) [32] 28 B. Sign-Difference-Ratio (SDR) [33] 29 C. Hard-Decision-Aided (HDA) [32] 29 D. Improved Hard-Decision-Aided (IHDA) [34] 30 2.3.3 Other ET Methods 31 A. Mean-Sign-Change (MSC) [29] 31 B. Cyclic-Redundancy-Check (CRC) [35] 31 C. Valid-Code-Word (VCW) check [36] 31 2.3.4 Conventional GENIE [33] 31 Chapter 3 The Proposed Early Termination Schemes 33 3.1 The Proposed Measurement of Reliability (MOR) Stopping Criterion 33 3.1.1 Frame Testing vs. Stage Testing 34 3.1.2 Modification on Existing ET Methods 35 A. Modified-ME (M-ME) 36 B. Modified-SCR (M-SCR) 36 C. Modified-SDR (M-SDR) 37 D. Modified-HDA (M-HDA) 37 E. Modified-IHDA (M-IHDA) 37 3.2 Turbo Decoding Threshold Analysis 38 3.2.1 Direct Observations of LLR 38 A. LLR vs. Iterations in High-SNR conditions 38 B. LLR vs. Iterations in Low-SNR conditions 39 3.2.2 Extrinsic Information Transfer (EXIT) Chart 41 A. Gaussian Approximated Log-Likelihood-Ratio 41 B. SNR Measurement 42 C. Mutual Information Measurement 42 D. The proposed Cross-Correlation Measurement 43 E. The Trajectory in The EXIT Chart 45 3.3 The Proposed ET-I and ET-II Schemes 47 3.4 Simulations and Comparisons 48 3.4.1 Experiment I (ET-I Scheme) 49 A. Simulations for GENIE-Aided Benchmark 49 B. Simulations for Different Stopping Criteria 50 C. Simulations for Frame Testing vs. Stage Testing 53 D. Performance Simulations 55 3.4.2 Experiment II (ET-I and ET-II Schemes) 56 A. Simulations for The Decoding Threshold by the EXIT Chart 56 B. Simulations for The GENIE-Aided Benchmark 59 C. Characteristics of ET Indicators 62 D. Simulations for Different ET schemes 64 3.4.3 Summary of all ET Approaches 68 Chapter 4 Timing Analysis of The FEC Decoding 71 4.1 Timing Charts of The Viterbi Decoding 71 A. Distribution Technique 74 B. Pointer Technique 75 C. Parallel Technique 76 D. Combined Distribution/Pointer/Parallel Technique 77 4.1.2 Tile-Based Methodology for The Viterbi Timing Composition 78 4.2 Timing Charts of The MAP Decoding 81 A. Distribution Technique 83 B. Pointer Technique 85 C. Parallel Technique 86 D. Combined Distribution/Pointer/Parallel Technique 87 4.2.2 Tile-Based Methodology for The MAP Timing Composition 89 4.3 Timing Analysis of The Triple-Mode VA/MAP Decoding 91 4.3.1 Utilization Analysis 91 4.3.2 Tile-Based Analysis on The Utilization of The Complementary VA/MAP Timing Chart 92 4.3.3 Complementary Timing Charts of The VA/MAP Decoding 93 4.3.4 Realization of The Triple-Mode Timing Chart 96 4.3.5 Analysis of Hardware Utilization in The Triple-Mode Timing Chart 98 Chapter 5 The Proposed VLSI Architecture of The Triple-Mode FEC Decoder 101 5.1 Architecture of Triple-Mode FEC Decoder 101 5.1.1 VA Mode (Convolutional Decoding) 103 5.1.2 MAP Mode (Turbo Decoding) 104 5.1.3 Concurrent VA/MAP Mode (Concurrent Convolutional/Turbo Decoding) 105 5.2 DSP Module Designs of The Triple-Mode FEC Kernel 106 5.2.1 Encoder Embedded Trellis Router (EETR) 106 A. VA Mode 107 B. MAP Mode 109 5.2.2 BM/Gamma Module 111 5.2.3 RUF Module 115 5.2.4 Chip Implementation of the FEC Kernel 116 Chapter 6 Conclusions and Future Works 121 6.1 Conclusions 121 6.2 Future works 122 Bibliography 1241505674 bytesapplication/pdfen-US前向錯誤更正碼渦輪碼迴旋碼疊代運算提早終止forward error correctionFECTurbo codeConvolutional codeiterative decodingearly terminationETthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/57547/1/ntu-96-D91943011-1.pdf