請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30627
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 吳安宇 | |
dc.contributor.author | Fan-Min Li | en |
dc.contributor.author | 李芳明 | zh_TW |
dc.date.accessioned | 2021-06-13T02:10:34Z | - |
dc.date.available | 2007-07-03 | |
dc.date.copyright | 2007-07-03 | |
dc.date.issued | 2007 | |
dc.date.submitted | 2007-06-25 | |
dc.identifier.citation | [1] A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inform. Theory, vol. IT-13, pp. 260-269, Apr. 1967.
[2] G. D. Forney, “The Viterbi algorithm,” Proc. IEEE, vol. 61, pp. 268-278, Mar. 1973. [3] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo codes,” in Proc. IEEE Int. Conf. Commun., May 1993, pp. 1064–1070. [4] C. Berrou and A. Glavieux, “Near optimum error correcting coding and decoding. Turbo-codes, “ IEEE Trans. Commun., vol. 44, no. 10, pp. 1261-1271, 1996. [5] R. Steele and L. Hanzo, Eds., Mobile Radio Communications: Second and Third Generation Cellular and WATM Systems, 2nded. New York: Wiley, 1999, ISBN 07273-1406-8. [6] http://www.3gpp.org/ [7] http://www.3gpp2.org/ [8] L. Bahl, J, Cocke, F. Jelinck, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inform. Theory, vol. IT-20, pp. 284-287, March 1974. [9] J. Hagenauer and P. Hoeher, “A Viterbi algorithm with soft-decision outputs and its applications,” IEEE Globecom, pp. 1680-1686, 1989. [10] P. Robertson, E. Villebrun, and P. Hoeher, “A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain,” in Proc. Int. Conf. Communications, June 1995, pp. 1009-1013. [11] K. K. Parhi and T. Nishitani, “Digital Signal Processing for Multimedia Systems.” Marcel Dekker, New York. [12] M. M. Mansour and N. R. Shanbhag, “VLSI Architecture for SISO-APP Decoders,” IEEE Trans. VLSI, Vol. 11, NO. 4, pp. 627-650, Aug. 2003. [13] E. Boutillon, W. J. Gross and P. G. Gulak, “VLSI Architectures for the MAP algorithm,” IEEE Trans. Comm. Vol. 51, NO. 2, pp. 175-185, Feb. 2003. [14] C. Schurgers, F. Catthoor and M. Engels, “Memory Optimization of MAP Turbo Decoder Algorithm,” IEEE Trans. VLSI, Vol. 9, NO. 2, pp.305-312, Apr. 2001. [15] Z. Wang, Z. Chi and K. K. Parhi, “Area –Efficient High-Speed Decoding Schemes for Turbo Decoders,” IEEE Trans. VLSI, Vol. 10, NO. 6, pp. 902-912, Dec. 2002. [16] M. Bickerstaff et al, “A unified turbo/viterbi channel decoder for 3GPP mobile wireless in 0.18 μm CMOS,” Solid-State Circuits Conference. Digest of Technical Papers. ISSCC. IEEE International, vol. 1, 2002, pp. 124-451. [17] M. C. Shin and I. C. Park, “A programmable turbo decoder for multiple 3G wireless standards,” Solid-State Circuits Conference. Digest of Technical Papers. ISSCC. IEEE International, 2003. [18] G. Kreiselmaier, T. Vogt. N. Wehn and F. Berens, “Combined Turbo and Convolutional Decoder Architecture for UMTS Wireless Applications,” Proceedings of the 15 th Symposium on Integrated Circuits and Systems Design, 2002. [19] J. Hagenauer, “The turbo principle: Tutorial Introduction and state of the art,” in Proc. Int. Symp. Turbo Codes and Related Topics, Brest, France, 1997, pp. 1-11. [20] S. Benedetto, D. Divsalar, G. Montorsi and F. Pollara, “Analysis, design and iterative decoding of serially concatenated codes with interleavers,” Special issue: IEEE Jour. Specially Areas in Commun., S. Benedetto, D. Divslar and J. Hagenauer, Eds., vol. JSAC-15, Jan. 1998. [21] C. Douillard, M. Jezequel, C. Berrou, A. Picart, P. Didier, A. Glavieux, “Iterative correction of intersymbol interference: Turbo-equalization.” European Trans. Telecommun., vol. 6, No. 5, pp. 507-511, Sept.-Oct. 1995. [22] P. Robertson and T. Woers, “A novel bandwidth efficient coding scheme employing turbo codes,” in Proc. IEEE Int. Conf. Commun., June 1996, pp. 962-967. [23] J. Hagenauer, “Forward error correcting for CDMA systems,” in Proc. IEEE Fourth Int. Symp. Spread Spectrum Techniques and Applications, Sept. 1996, pp. 566-569. [24] J. Hagenauer, “Source-controlled channel decoding,” IEEE Trans. Commun., vol. COM-43, no. 9, pp. 2449-2457, Sept. 1995. [25] R.G. Gallager, Low-Density Parity Check Codes. Cambridge, MA: MIT Press, 1963. [26] D. J. C. Mackay and R. M. Neal, “Good codes based on very sparse matrices,” in Proc. 5th IMA Conf. Cryptography and Coding, 1995, pp. 110-111. [27] J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. Inform. Theory, vol. 42, pp. 429-445, Mar. 1996. [28] Z. Wang, H. Suzuki, and K. K. Parhi, “VLSI implementation issues of turbo decoder design for wireless applications,” in Proc. IEEE Workshop on Signal Processing Systems, Oct. 1999, pp.503-512. [29] F. Zhai and I. Fair, “New error detection techniques and stopping criteria for turbo decoding,” in Proc. 2000 Canadian Conf. Electrical and Computer Engineering, Mar. 2000, pp. 58-62. [30] N. Y. Yu, M. G. Kim, Y. S. Kim, and S. U. Chung, “Efficient stopping criterion for iterative decoding of turbo codes,” IEE Electronic Letters, vol. 39, pp. 73-75, Jan. 2003. [31] D. Bokolamulla and T. Aulin, “A new stopping criterion for iterative decoding,” in Proc. IEEE Int. Conf. Commun., June 2004, pp. 538-541. [32] R. Y. Shao, S. Lin, and M. P. C. Fossorier, “Two simple stopping criteria for turbo decoding,” IEEE Trans. Commun., vol. 47, pp. 1117-1120, Aug. 1999. [33] Y. Wu, D. Woerner, and J. Ebel, “A simple stopping criteria for turbo decoding,” IEEE Commun. Letters, vol. 4, pp. 258-260, Aug. 2000. [34] T. M. N. Ngatched and F. Takawira, “Simple stopping criterion for turbo decoding,” IEE Electronic Letters, vol. 37, pp. 1350-1351, Oct. 2001. [35] A. Shibutani, H. Suda, and F. Adachi, “Reducing average number of turbo decoding iterations,” IEE Electronic Letters, vol. 35, pp. 701-702, Apr. 1999. [36] J. Heo, K. Chung, and K. M. Chugg, “Simple stopping criterion for min-sum iterative decoding algorithm,” IEE Electronic Letters, vol. 37, pp. 1530-1531, Dec. 2001. [37] F. M. Li and A. Y. Wu, “New stopping criterion for efficient early termination in turbo decoding design,” in Proc. 2005 Int. Symp. Intelligent Signal Processing and Commun. Systems, Dec. 2005, pp. 585-588. [38] H. E. Gamal and A. R. Hammons, “Analyzing the turbo decoder using the Gaussian approximation,” IEEE Trans. Inform. Theory, Vol. 47, No. 2, pp. 671-686, Feb. 2001. [39] S. T. Brink, “Convergence behavior of iteratively decoded parallel concatenated codes,” IEEE Trans. Commun., Vol. 49, No. 10, pp. 1727-1737, Oct. 2001. [40] S. J. Lee, A. C. Singer, and N. R. Shanbhag, “Linear turbo equalization analysis via BER transfer and EXIT charts,” IEEE Trans. Signal Processing, Vol. 53, No. 8, pp. 2883-2897, Aug 2005. [41] 3GPP2 C.S0002-D, Physical Layer Standard for cdma2000 Spread Spectrum Systems Revision D, Mar. 2004. [42] A. Ghosh, D. R. Wolter, J. G. Andrews and R. Chen, “Broadband wireless access with WiMax/802.16: Current Performance Benchmarks and Future Potential,” IEEE Commun. Magazine, pp. 129-136, Feb. 2005. [43] F. Wang, A. Ghosh, R. Love, K. Stewart, R. Ratasuk, R. Bachu, Y. Sun and Q. Zhao, “IEEE 802.16e system performance: Analysis and simulations,” in Proc. IEEE 16th Int. Symp. Personal, Indoor and Mobile Radio Commun., Sept. 2005, pp. 900-904. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30627 | - |
dc.description.abstract | 在先進的前向錯誤更正碼(Forward Error Correction, FEC)標準裏,同時採用了迴旋碼和渦輪碼的編碼方法,所以我們需要一個可重置的錯誤更正解碼設計。此外,渦輪解碼是藉由疊代運算完成,為了降低它所造成的電源消耗和時間延遲,我們需要一個可以依據通訊環境的好壞,而提早終止(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運算核心硬體設計原型。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T02:10:34Z (GMT). No. of bitstreams: 1 ntu-96-D91943011-1.pdf: 1505674 bytes, checksum: d379e886a53a51264294869657a5b8e0 (MD5) Previous issue date: 2007 | en |
dc.description.tableofcontents | 誌謝 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 124 | |
dc.language.iso | en | |
dc.title | 整合型錯誤更正碼之演算法及積體電路架構設計 | zh_TW |
dc.title | Algorithm and VLSI Architecture of Unified FEC Decoder Designs | en |
dc.type | Thesis | |
dc.date.schoolyear | 95-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 曹恆偉,吳文榕,黃穎聰,謝明德,張錫嘉,陳紹基,黃元豪 | |
dc.subject.keyword | 前向錯誤更正碼,渦輪碼,迴旋碼,疊代運算,提早終止, | zh_TW |
dc.subject.keyword | forward error correction,FEC,Turbo code,Convolutional code,iterative decoding,early termination,ET, | en |
dc.relation.page | 127 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2007-06-26 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 1.47 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。