渦輪碼 (turbo code) 是在1993年由Berrou等人所提出來的一種錯誤更正碼技術。此種錯誤更正碼技術是近年來在編碼理論的領域中一項非常重要的突破。它是由兩個相同的8-state迴旋編碼器以平行鏈結的方式及一個交錯存取器組合而成; 並以反覆解碼的架構進行解碼。
由於渦輪碼的錯誤更正能力非常強大，它可以在相當低的訊號雜訊比情況下依然能使數位通訊系統擁有很低的位元錯誤率，是一種被證明出非常接近沉農極限(Shannon-limit)的錯誤更正碼。因此相當適用於無線通訊傳輸系統的應用，故被選擇成為第三代行動通訊系統(3GPP、3GPP2)的通道編解碼方法之一。
若將渦輪碼解碼器與傳統的迴旋碼解碼器來做比較，前者的演算方式顯然複雜了許多，而且在硬體實現時，由於其大量暫存器和記憶體的消耗，以及複雜的運算程序，使得硬體在實現上存在著極大的瓶頸。為了解決此問題，本論文在硬體實現時選擇了硬體複雜度較低之Max-Log-MAP演算法作為解碼器的解碼演算法。而在MATLAB程式設計時則是使用Log-MAP的演算法(亦提供Max-Log-MAP演算法)來做模擬。
在本論文中，首先會介紹渦輪碼編碼器的架構，接著詳述其中迴旋碼編解碼器之原理，再者是介紹渦輪碼解碼器的演算法及其硬體概念。而在渦輪碼編解碼器的設計過程中，首先使用MATLAB程式來模擬其流程及功能是否正確，再來則是使用Verilog語言於Xilinx ISE環境下來模擬此電路。在模擬成功後，於Virtex-E之FGPA上合成實現本研究中所設計出之渦輪碼編解碼器電路。在本論文中，為印證所實現之FPGA渦輪碼編解碼器，我們將一串文字資料存入記憶體SRAM，然後從記憶體讀出資料並經編碼器編碼，編碼後加入適當的錯誤位元;再傳送解碼器解碼，還原為原傳送之文字資料。經由此實驗我們證實了所設計出FPGA的渦輪碼編解碼器之可行性及正確性。

Turbo code is an error correction technology developed by Berrou in 1993. In recent years, this technology is a very important breakthrough in the coding theorem. Turbo code comprises of two parallel concatenation convolutional encoders and an interleaver, and is decoded by iteration decoding procedures.
Owing to its excellent correction ability, turbo code can lead to that there is very low bit error ratio in digital communication system at low SNR, and is proved to be the error correction coding that approaches the Shannon-Limit. Consequently, turbo code quite befits the applications of wireless communication systems and has been selected as one of the channel coding schemes in the 3rd generation communication systems.
Compared with convolutional decoder, the turbo code is obviously more complex in decoding algorithm. There exists an extreme bottleneck in hardware implementation because of a great quantity of registers and memory consumptions and the complexity of the decoding procedure.
In this thesis, in order to resolve the problems mentioned above, we choose the lower complexity decoding method: Max-Log-MAP as our decoding algorithm in FPGA implementation. In MATLAB design environment, we use the Log-MAP decoding algorithm (also provide the Max-Log MAP decoding algorithm) for simulations.
In this thesis, we firstly introduce the structure of turbo codes, and then describe the principles of convolution codes. Furthermore, we depict the decoding algorithm of turbo decoder and its hardware design concept. In the process of designing both turbo encoder and decoder, we first develop MATLAB programs to verify the correctness of decoding procedures and its functions, and then derive Verilog HDL codes in Xilinx ISE environment to describe these circuits. After Verilog simulations done, we synthesize and implement the turbo encoder and decoder designed in this thesis on Virtex-E series FPGA. In the thesis, for verifying the implemented turbo code, we first write some sentences into the memory SRAM, and then encode those sentences reading from the memory by turbo encoder. The codewords are transferred to decoder after adding the error patterns. Finally, the receiver will get the original data. These experiments confirm that the FPGA-based turbo code implemented in the thesis is feasible and correct.

[1] Claude Berrou, Alain Glavieux and Punya Thitimajshima, “Near Shannon limit error-correcting coding and decoding : Turbo-codes (1)” Proc. IEEE Int. Conf. Commun, Geneva, Switzerland, 1993, pp.1064-1070
[2] Tri Ngo and Ingrid Verbauwhede, “Fixed point implementation for turbo codes” Final Report 1998-99 for Micro Project 98-162.
[3] Amir Chass, Arik Gubeskys and Gideon Kutz, “Efficient Software Implementation of the Max-Log-MAP Turbo Decoder on the StarCore SC140 DSP” Motorola Semiconductor Israel Ltd., Shenkar 1, Herzeliz 46725, Israel.
[4] Johannes Steensma and Chris Dick, “FPGA implementation of a 3GPP turbo codec” Conference Record of the Thirty-Fifth Asilomar Conference on, vol.1, 4-7 Nov. 2001, pp.61-65
[5] Mohamadreza Marandian, Jose Fridman, Zoran Zvonar and Masoud Salehi, “Performance Analysis of Turbo Decoder for 3GPP Standard using the Sliding Window Algorithm” IEEE International Symposium on, Volume:2, 30 Sept.-3 Oct. 2001, pp.E-127- E-131 vol.2
[6] James G. Harrison, “Implementation of a 3GPP Turbo Decoder on a Programmable DSP Core” Communication Design Conference, San Jose California, October 2, 2001.
[7] M. Z. Wang, A. Sheikh and F. Qi, “Interleaver Design for Short Turbo Codes” Global Telecommunication Conference – Globecom’99, pp. 894-898, 1999 IEEE.
[8] A. Burr, “Turbo-codes: the ultimate error control codes?”
Electronics Communication Engineering Journal, August 2001, pp.155-165.
[9] Jakob Dahl Andersen, “A Turbo Tutorial”, http://www.tele.dtu.dk~jda.
[10] Zhang Zhongpei and Zhou Liang, “A Low Complex Parallel Decoding Structure for Turbo-codes” UESTC Chengdu 610054 China.
[11] Robertson, P.,Villebrun, E. and Hoeher, P, ” A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain” IEEE International Conference, 18-22 June 1995, vol.2, pp. 1009 -1013
[12] Warren J. Gross, Vincent C. Gaudet, and P. Glenn 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, October 2001, pp.904-911.
[13] Lin S., Costello D.J., “Error Control Coding: Fundamentals and Applications” Englewood Cliffs, New Jersey, Prentice-Hall, 1983.
[14] Jason R. Hess, “Implementation of a Turbo Decoder on a Configurable Computing Platform”, A thesis, Virginia Polytechnic Institute and State University, Master of Science in Electrical Engineering, 17th Sep, 1999.
[15] James Yang, “Statistical Decision Making in Adaptive Modulation and Coding for 3G Wireless Systems”, A thesis, Waterloo, Ontario, Canada, 2002.
[16] Wu Yi, Zhou Shidong, Yao Yan, “Design of a DSP-Based High-Speed Turbo Code Decoder for WCDMA Applications” State Key Lab on Microwave & Digital Communications, Tsinghua University, Beijing 100084, China.
[17] Kuhn Ip, Desmond Lun, “Near-Shannon-limit channel coding using woven convolutional codes” Fourth year electrical engineering project report, November 13, 2000.
[18] Yuki NAKANO, Daisuke UMEHARA, Makoto KAWAI, and Yoshiteru MORIHIRO, “Viterbi Decoding for Convolutional Code over Class A Noise Channel” , Electrical and Electronic Engineering Graduate School of Informatics Kyoto University, Yoshidahonmachi, Sakyoku, Kyoto, 606-8501, Japan.
[19] Simom Haykin, “Communication systems 3rd ed” ISBN 957-21-1050-0.
[20] M. C. Valenti and J. Sun, “ The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios” International Journal of Wireless Information Networks, vol. 8, No. 4, October 2001, pp.203-215.
[21] K.K. Loo, K. Salman, T. Alukaidey and S.A. Jimaa, “ Parallelised max-log-Map model” Electronics Letters 15th August 2002, vol.38, pp. 971-972.
[22] FL. Sahak Yeongum Bldg, Dusan-Dong, Seo-Gu, Taejon, ”3GPP Turbo Decoder” May 4, 2001, http:// www.xilinx.com
[23] Hong, Sangjin, Yi, Joonhwan. and Stark, Wayne. E., “VLSI design and implementation of low-complexity adaptive turbo-code encoder and decoder for wireless mobile communication applications” IEEE Workshop on, 8-10 Oct. 1998, pp.233-242.
[24] “3GPP Compliant Turbo Convolutional Codec V1.0” May 11, 2001, http://www.xilinx.com/company/contact.htm.
[25] “MAP03T Very High Speed MAP Decoder” Small World Communications, 30 January 2002 (Version 4.0), http:// www.sworld.com.au
[26] Berrou C., Combelles, P., Penard, P., Talibart, B. “An IC for Turbo-Codes Encoding and Decoding” 1995 IEEE, International Solid-State Circuits Conference, pp. 90-91.
[27] Herbert Dawid and Heinrich Meyr, “Real-time algorithms and VLSI architecture for soft output MAP convolutional decoding” IEEE International Symposium. vol. 1, 27-29 Sept. 1995, pp.193-197
[28] “Turbo Codes”, http://www.channelscience.com.turbo_training.htm
[29] Sergio Benedetto, Guido Montorsi, “Design guidelines of parallel concatenated convolutional codes” IEEE. Global Telecommunication Conference, vol.3, 13-17 Nov. 1995, pp. 2273-2277.
[30] Eric K. Hall and Stephen G. Wilson, “Stream-oriented parallel concatenated convolutional codes” IEEE. Information Theory Workshop, 22-26 June. 1998, pp. 4-5.
[31] Tri Ngo, Ingrid Verbauwhede, “Turbo codes on the fixed point DSP TMS320C55x” IEEE, Signal Processing Systems, 11-13 Oct. 2000, pp.255-264.
[32] “Using block selectRAM+ memory in Spartan-II FPGAs”, XAPP173 (v1.1), 11 Dec. 2000, http://www.xilinx.com.
[33] T. R. N. Rao, E. Fujiwara, “ Error-Control Coding for Computer Systems” Englewood Cliffs, NJ: Prentice-Hall, 1995.
[34] Claude Berrou, Patrick Adde, Ettiboua Angui and Stephane Faudeil, “A Low Complexity Soft-Output Viterbi Decoder Architecture” IEEE, International Conference, vol. 2, 23-26 May 1993, pp. 737-740.
[35] Yan Wang, Chi-Ying Tsui, Roger S. Cheng, “A Low Power VLSI Architecture of SOVA-based Turbo-code decoder using Scarce State Transition Scheme” IEEE International Symposium on Circuits and Systems, May 28-31, 2000. Geneva, Switzerland, pp. I283-286.
[36] “Spartan-IIE 1.8V FPGA Family: Functional Description” DS077-2 (v2.0) November 18, 2002. http://www.xilinx.com.