臺灣博碩士論文加值系統

渦輪碼 (turbo code) 是由Berrou等人於1993年所提出來的一種錯誤更正碼技術。此種錯誤更正碼技術是當代編碼理論的一大突破，因為它在相當低的訊號雜訊比中仍可以使數位通訊系統具有低的位元錯誤率，所以被選擇於第三代行動通訊系統的通道編碼解碼方法之一。第三代行動通訊系統的標準規範被定義於IMT-2000 (International Mobile Telecommunications-2000)，IMT-2000 是由 ITU (International Telecommunication Union) 所定義。其位元傳輸率為到大部分地區：384 kbit/s，室內或靜止狀態：2 Mbit/s或更高。歐洲的WCDMA系統 與 北美的CDMA-2000 系統為第三代行動通訊系統的主要兩大方案，兩者的渦輪碼編碼器皆由兩個相同的8-state迴旋編碼器(convolutional encoder) 及一個交錯存取器所組成。而渦輪解碼器 (turbo decode) 主要是由兩個具有軟式輸入 (soft-input) 及軟式輸出 (soft-output) 的迴旋解碼器和一組交錯存取器所組成並以反覆解碼的架構來解碼。
用於軟式輸入軟式輸出解碼器的演算法，主要可分為軟式輸出緋特比演算法 (SOVA) 與最大事後機率 (MAP) 演算法兩大類。每種演算法具有不同的錯誤更正效果及運算複雜度，越好的錯誤更正效果通常伴隨著越複雜的運算複雜度。在本篇論文中，我們首先將探討這些演算法的運算原理以及降低運算複雜度的技巧。接下來，我們分析各種演算法的運算的運算複雜度與模擬在CDMA-2000 系統下，各種硬體設計上的考量與不同演算法間的錯誤更正效果。從這些分析與模擬結果，我們在錯誤更正效果及運算複雜度間做一取捨，選擇Max-Log-MAP演算法作為軟式輸入軟式輸出解碼器的演算法。依循這些模擬參數，我們設計一個全新架構的渦輪解碼器，此解碼器是依照 CDMA-2000 系統之規範，傳輸率可達到2 Mbit/s，並且可成功合成於FPGA上。

Contents II
List of Figures V
List of Tables VII
List of Notations VIII
List of Acronyms XI
Chapter 1 Introduction 1
1.1 Fundamental Limits 1
1.2 Related Work 3
1.3 Major Contributions of the Thesis 4
1.4 Thesis Outline 4
Chapter 2 Turbo Codes System 5
2.1 Element of a Digital Communication System 5
2.2 Turbo Encoder 6
2.2.1 Turbo Encoding of CDMA2000 6
2.2.2 Block Size and Data Rate 6
2.2.3 Constituent Encoder 7
2.2.4 Puncture Table and Repetition 9
2.2.5 Turbo Interleavers 10
2.3 Turbo Decoder 11
2.3.1 Turbo Decoder System 11
2.3.2 MAP Algorithm 12
2.3.2.1 Branch Metric 13
2.3.2.2 Forward Recursion 14
2.3.2.3 Backward Recursion 16
2.3.2.4 Log Likelihood Ratio 17
2.3.2.5 Extrinsic Information 18
2.3.3 Log-MAP algorithm 20
2.3.3.1 Forward Recursive 21
2.3.3.2 Backward Recursive 22
2.3.3.3 Log Likelihood Ratio 23
2.3.4 Max-Log-MAP algorithm 24
2.3.4.1 Forward Recursion 24
2.3.4.2 Backward Recursive 25
2.3.4.3 Log Likelihood Ratio 25
2.3.5 Sliding Windows MAP algorithm 26
2.3.6 Another Ways to Reduce Complexity 27
2.3.7 Original SOVA Algorithm 30
2.3.7.1 Viterbi Algorithm 30
2.3.7.2 Extrinsic Information of Original SOVA 32
2.3.8 Modified SOVA Algorithm 35
2.3.9 Another Ways to Simplify SOVA algorithm 36
2.3.11 Comparison for Each Decoding Algorithm 39
2.3.11.2 Memory Usage for Decoding Algorithms 42
2.4 Conclusion 42
Chapter 3 Simulation and Analysis of Turbo Decoder Algorithms 44
3.1 Simulation of MAP Algorithm 44
3.1.1 Simulation of MAP for Different Block Sizes 44
3.1.2 The Effects of Overlap-Length 46
3.1.3 Simulation of the Effect of Extrinsic Information 47
3.1.4 Simulation of the Effects of Quantization 49
3.1.5 Simulation of the Effect of Sliding window 50
3.2 Simulation of Log-MAP Algorithm 51
3.2.1 Simulation of the Effect of Overlap-Length 51
3.2.2 Simulation of the Effect of Quantization 53
3.3 Simulation of Max-Log-MAP Algorithm 54
3.3.1 Simulation of the Effect of Overlap-Length 54
3.3.2 Simulate the Effect of Quantization 56
3.4 Simulation of the Original SOVA 57
3.5 Simulation of Modified SOVA 59
3.6 Simulation of A Posterior Weighting Algorithm 60
3.7 All Algorithms 61
3.7 Conclusion 63
Chapter 4 VLSI Implementation of Turbo Decoder 64
4.1 Architecture of Top-Level Decoder 64
4.1.1 Receiving Data and Decoding Procedure 65
4.1.2 Decoding Procedure of a Frame 65
4.1.3 Decoding Procedure of a Constituent Decoder 65
4.1.4 Pipeline Execution of the Decoding Procedure for a SW 66
4.2 FIFO Module 68
4.3 I/O-Controller Module 68
4.4 Turbo-decoder module 69
4.4.1 Architecture of ACS Component 69
4.4.1.1 Radix-2 ACS Component 69
4.4.1.2 Radix-4 ACS Component 70
4.4.2 Architecture of ACS Array 71
4.4.3 Normalization of Alpha and Beta 73
4.4.4 Architecture of Lambda Array 73
4.4.5 Amount of words of alpha memory 75
4.5 Implement of Turbo Decoder by FPGA 76
4.5.1 Design Flow 76
4.5.1.1 ASM Chart of Turbo Decoder 77
4.5.1.2 Implicit Style Behavioral Module 78
4.5.1.3 Structural Module 79
4.5.1.4 Simulation 79
4.5.1.5 Timing Analysis and Design Modification 81
4.6 Conclusion 82
Chapter 5 Conclusion 84
5.1 Conclusion 84
5.2 Future Work 84
Bibliography 85

[1] http://www.itu.int/home/index.html.
[2] http://www.etsi.org/.
[3] http://www.tiaonline.org/.
[4] TELECOMMUNICATIONS INDUSTRY ASSOCIATION, “Physical Layer Standards for cdma2000 Spread Spectrum Systems”, TIA/EIA/IS-2000-2, 1999.
[5] G. Berrou, A. Glavieux, and P. Thitmajshima, “Near Shannon limit error-correcting codeing: turbo codes,” in Proc. 1993 Int. Conf. Commun., Geneva, Switzerland, May 1993, pp. 1064-1070.
[6] C.E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal, Vol. 27, pp. 379-423 (Part One) and 623-656 (Part Two), Oct. 1948.
[7] S. A. Barbulescu and S. S. Pietrobon, “Interleaver design for turbo codes”, Electron. Lett. , Vol. 30, No. 25, pp. 2107-2108, Dec. 1994.
[8] M. Eroz, A.R. Hammons Jr., “On the design of prunable interleavers for turbo codes”, Vehicular Technology Conference, 1999 IEEE 49th, Vol. 2, 1999.
[9] J. Hokfelt, O. Edfors, and T. Maseng, “On the theory and performance of trellis termination methods for turbo codes”, IEEE Journal on slelected areas in communication, Vol. 19, NO. 5, May 2001.
[10] J. Andersen, “The turbo coding scheme”, IEEE International Symposium on Information Theory, Trondheim, Norway, June 1994.
[11] Jan-Ming Hsu and Chin-Liang Wang, “A parallel decoding Scheme for turbo cdoes”, IEEE International Symposium on circuits and systems, Vol. 4 1998.
[12] P. Robertson, “Illuminating the structure of code and decoder for parallel concatenated recursive systematic (turbo) codes,” IEEE GLOBECOM’94, San Francisco, USA, Nov.—Dec. 1994.
[13] W.T. Wang, “On soft-output decoding algorithm for turbo codes”, Master thesis, National Tsing Hua University, Hsinchu, Taiwan, R.O.C., June 1999.
[14] L.R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Trans. Inform. Theory, Vol. IT-20, pp. 284-287, Mar. 1974.
[15] P. Robertson, E. Villebrun, P. Hoeher, “A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain”, 1995. ICC ''95 Seattle, ''Gateway to Globalization'', 1995 IEEE International Conference on Communications, Vol. 2, pp.1009 —1013, 1995
[16] A. Worm, P. Hoeher, N. Wehn, “Turbo-decoding without SNR estimation”, IEEE Communications Letters , Vol. 4, Issue 6 , pp. 193 —195, June 2000
[17] B. Bai, X. Ma, X. Wang, “Novel algorithm for continuous decoding of turbo codes”, IEE Proceedings-Communications, Vol. 146, Issue 5 , pp. 271 —274, Oct. 1999.
[18] D. Wang, H. Kobasyashi, “Low-complexity MAP decoding for turbo codes”, Vehicular Technology Conference Proceedings, 2000. VTC 2000-Spring Tokyo. 2000 IEEE 51st, Vol. 2, pp. 1035 —1039, 2000.
[19] S. S. Pietrobon and S. A. Barbulescu, “A simplification of the modified Bahl decoding algorithm for systematic convolutional codes”, Int. Symp. on Inform. Theory and its Applications, pp. 1073-1077, Nov. 1994. Revised 4 Jan. 1996.
[20] S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “Soft-output decoding algorithms for continuous decoding of parallel concatenated convolutional codes”, JPL TDA Progress Report, vol. 42-124, pp. 63—87, Feb. 1996.
[21] P. Hoeher, “New iterative(“Turbo”) decoding algorithms”, in Proc. Int. Symp. on Turbo Codes & Related Topics, Brest, France, pp. 63—70, 1997.
[22] P. Robertson, P. Hoeher, and E. Villebrun, “Optimal and sub-optimal maximum a posteriori algorithms suitable for turbo decoding”, ETT, Vol. 8, No. 2, pp. 119-125, Mar./Apr. 1997.
[23] J. Hagenauer, P. Hoeher, ” A Viterbi algorithm with soft-decision outputs and its applications”, Global Telecommunications Conference, 1989, and Exhibition. Communications Technology for the 1990s and Beyond. GLOBECOM ''89., IEEE , pp. 1680 -1686 Vol.3, 1989.
[24] J. Hagenauer, “Source-controlled channel decoding”, IEEE Transactions on Communications, Vol. 43 Issue 9 , pp. 2449 —2457, Sept. 1995.
[25] M.P.C. Fossorier, F. Burkert, Shu Lin, J. Hagenauer, “On the equivalence between SOVA and max-log-MAP decodings”, IEEE Communications Letters, Vol. 2, Issue. 5, pp. 137 —139, May 1998.
[26] O.J. Joeressen, H. Meyr,, “A new postprocessing architecture for soft output Viterbi decoding”, VLSI Signal Processing, VII, 1994, pp. 336 -345.
[27] C. Berrou, P. Adde, E. Angui, S. Faudeil, “A low complexity soft-output Viterbi decoder architecture”, 1993. ICC ''93 Geneva. Technical Program, Conference Record, IEEE International Conference on Communications, Vol. 2, pp. 737 -740 vol.2, 1993.
[28] H. Michel and N.Wehn, “Turbo-decoder quantization for UMTS”, IEEE Communications Letters, 2000. Accepted.
[29] H. Michel, A. Worm, and N.Wehn, “Influence of quantization on the bit-error performance of turbo-decoders”, In Proc. VTC’00 Spring, May 2000.
[30] Q. Li, N.S. Ramesh, ”Channel coding performance in cdma2000 systems”, Emerging Technologies Symposium: Broadband, Wireless Internet Access, 2000 IEEE , pp. 5, 2000.
[31] P. Luukkanen, Ping Zhang, “Comparison of optimum and sub-optimum turbo decoding schemes in 3rd generation cdma2000 mobile system”, Wireless Communications and Networking Conference, 1999. WCNC. 1999 IEEE , Vol.1, pp. 437 —441, 1999.
[32] A. Hmimy, S.C. Gupta, “Performance of turbo-codes for WCDMA systems in flat fading channels”, Wireless Communications and Networking Conference, 1999. WCNC. Vol.11999, IEEE , 1999, pp. 452 -456.
[33] D. Garrett, M. Stan, “Low Power Architecture of the Soft-Output Viterbi Algorithm”, 1998 International Symposium on Low Power Electronics and Design, 1998 pp. 262 —267, 1998.
[34] D. Garrett, M. Stan, “A 2.5 Mb/s, 23mW SOVA traceback chip for turbo decoding application”, The 2001 IEEE International Symposium on Circuits and Systems, Vol. 4, pp. 61—64, 2001.
[35] O.J. Joeressen, H. Meyr, “A 40 Mbitps soft output Viterbi decoding ASIC”, Global Telecommunications Conference, 1994. GLOBECOM ''94. Communications: The Global Bridge., IEEE , Vol. 3 , 1994, pp. 1482 -1486.
[36] O.J. Joeressen, H. Meyr, “A 40 Mb/s soft-output Viterbi decoder”, IEEE Journal of Solid-State Circuits, Vol. 30 Issue: 7 , July 1995, pp. 812-818.
[37] O.J. Joeressen, M. Vaupel, H. Meyr, “Soft-output Viterbi decoding VLSI implementation issues”, Vehicular Technology Conference, 1993., 43rd IEEE , 1993, pp. 941 -944.
[38] O.J. Joeressen, M. Vaupel, H. Meyr, “High-speed VLSI architectures for soft-output Viterbi decoding”, Proceedings of the International Conference on Application Specific Array Processors, 1992, pp. 373 -384.
[39] W. Gross, V. Gaudet, and G. Gulak, ”Difference Metric Soft-Output Detection: Architecture and Implementation”, IEEE Transactions on Circuits and Systems II - Analog and Digital Signal Processing, Vol. 48, No. 10, pp. 904-911, October 2001.
[40] Xuan Li, Wen-Tao Song, Han-Wen Luo, “Design and analysis of Turbo decoder for Chinese third generation mobile communication system”, The 7th IEEE International Conference on Electronics, Circuits and Systems, Vol. 2, pp. 680—683, 2000.
[41] A. Worm, H. Lamm, N. Wehn, “VLSI architectures for high-speed MAP decoders”, Fourteenth International Conference on VLSI Design, pp. 446 —453, 2001.
[42] H. Dawid, G. Gehnen, H. Meyr, “Map channel decoding: Algorithm and VLSI architecture”, VLSI Signal Processing, pp. 141 —149, 1993.
[43] C. Schurgers, F. Catthoor, M. Engels, “Memory optimization of MAP turbo decoder algorithms”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 9 Issue 2, pp. 305 —312, April 2001.
[44] F. Raouafi, A. Dingninou, C. Berrou, “Saving memory in turbo-decoders using the max-log-MAP algorithm”, IEE Colloquium on Turbo Codes in Digital Broadcasting - Could It Double Capacity? (Ref. No. 1999/165), pp. 14/1 -14/4, 1999.
[45] C. M. Lin, “VLSI implementation of a soft-input soft-output MAP decoder for turbo decoder”, Master thesis, National Tsing Hua University, Hsinchu, Taiwan, R.O.C., June 1997.
[46] P.J. Black, T.H.-Y Meng, “A 140Mb/s 32-state radix-4 Viterbi Decoder”, Solid-State Circuits Conference, 1992. pp. 70 -71, 247, 1992.
[47] M. Traber, “A novel ACS-feedback scheme for generic, sequential Viterbi - decoder macros”, The 2001 IEEE International Symposium on Circuits and Systems, Vol. 4, pp. 210 —213, 2001.
[48] R.V.K. Pillai, P. D''Arcy, “On high speed add-compare-select for Viterbi decoders”, Canadian Conference on Electrical and Computer Engineering, Vol. 2 , pp. 1193 -1198, 2001.
[49] G. Fettweis, H. Meyr, “Parallel Viterbi decoding by breaking the compare-select feedback bottleneck”, ICC ''88. Digital Technology - Spanning the Universe. Conference Record., IEEE International Conference on Communications, Vol. 2, pp. 719 -723 1998.
[50] H. Dawid, S. Bitterlich, H. Meyr, “Trellis pipeline-interleaving: a novel method for efficient Viterbi decoder implementation”, 1992 IEEE International Symposium on Circuits and Systems, 1992. ISCAS ''92. Proceedings., Vol. 4 , pp, 1875 —1878, 1992.
[51] G. Fettweis, H. Meyr, , 1990., IEEE International Symposium on Circuits and Systems, Vol. 2, pp. 978 —981, 1990.
[52] G. Fettweis, H. Dawid, H. Meyr, “Minimized method Viterbi decoding: 600 Mbit/s per chip”, Global Telecommunications Conference, 1990, and Exhibition. ''Communications: Connecting the Future'', GLOBECOM ''90., IEEE , Vol. 3, pp. 1712 —1716, 1990.
[53] A.P. Hekstra, “An alternative to metric rescaling in Viterbi decoders”, IEEE Transactions on Communications, Vol. 37, Issue: 11, pp. 1220 —1222, Nov. 1989.
[54] C.B. Shung, P.H. Siegel, G. Ungerboeck, H.K. Thapar, “VLSI architectures for metric normalization in the Viterbi algorithm”, IEEE International Conference on Communications. ICC ''90, Including Supercomm Technical Sessions. SUPERCOMM/ICC ''90, Vol. 4, pp. 1723 —1728, 1990
[55] Mark Gordon Arnold, “Verilog digital computer design algorithms into hardware”, Prenrice Hall PTR.
[56] http://www.cs.brockport.edu/~jshuler.