隨著第三代個人行動通訊時代的來臨，資料在高速無線傳輸上的正確性更顯重要，先進的渦輪碼扮演解資料回復的重要角色。渦輪碼的解碼效能可以趨近於沈農極限，但運算複雜度太高卻也是渦輪碼的致命傷，所以以傳統維特比解碼為基礎的軟輸出維特比解碼便因此應用在渦輪碼上，因為軟輸出維特比解碼是以傳統維特比解碼為基本架構，所以運算複雜度較最大機率演算法(Maximum A-Posteriori, MAP )要少上許多，當然硬體實現上的速度也較快，相對的；效能上就不及最大機率演算法。因此，在不大量增加運算複雜度及考慮可行性的情況下，我們改進雙向軟輸出維特比演算法(Bi-directional SOVA)來增加效能。在經過模擬後，改良後的雙向軟輸出維特比演算法可以相當接近最大機率演算法的效能，最後我們將這個演算法實現在FPGA上，並且實際測量其解碼效能。

For the coming age of the third generation mobile communication system, the reliability of high-speed data transmission is more important. The performance of turbo code which can theoretically approach to the one of Maximum a-posterior (MAP) algorithm plays an important role in recovering information. However, the Achilles'' heel of Turbo code is the high computational complexity. SOVA (Soft-out Viterbi Algorithm) is a very good algorithm for using in turbo code because of its low computational complexity and it is based on the traditional Viterbi algorithm so its computational complexity would be considered as low as possible. Obviously, the implementation of SOVA could be easier than the MAP. Somehow, the performance of SOVA is relatively worth than the one of MAP. We consider a new algorithm that will not cause high computational complexity to improve the performance of SOVA. Therefore, we proposed the improved Bi-directional SOVA. Surprisely, the performance of Bi-directional SOVA could approach to the one of Log-MAP after simulation so it is a very efficient way to implement in hardware. We utilized the improved Bi-directional SOVA in FPGA and measured the performance indeed.

中文摘要 i
英文摘要 iv
誌謝 iv
目錄 iv
圖目錄 vi
表目錄 vii
第一章 簡介 1
第二章 渦輪編解碼及相關區塊介紹 3
2.1 渦輪編碼…………………………………………………………………………3
2.2軟資訊(Soft Imformation)交換與疊代(Iteration)……………………………6
2.3 渦輪解碼…………………………………………………………………………6
第三章 用於渦輪碼的迴旋解碼介紹 9
3.1 最大機率演算法(Max a-posteriori algorithm, MAP)…………………………9
3.2 指數最大機率演算法(Log-MAP)………………………………………………14
3.3 最大指數最大機率演算法(Max-Log-MAP)……………………………………15
3.4 軟輸出維特比演算法(Soft Output Viterbi Algorithm,SOVA)……………………20
3.5 用於渦輪碼之迴旋編碼效能比較………………………………………………26
第四章 軟輸出維特比演算法之改進方法介紹 30
4.1 改良式之軟輸出維特比演算法(Modified SOVA, M-SOVA)…………………30
4.2 雙向軟輸出維特比演算法……………………………………………………34
4.3 事後機率正規化………………………………………………………………37
4.4 具有量度因子的雙向軟輸出維特比演算法…………………………………43
第五章 軟輸出維特比演算法硬體實現之個別單元 46
5.1 比較-加法-選擇單元(CAS unit)………………………………………………46
5.2 暫存器交換單元（Register Exchange unit）…………………………………49
5.3 更新字串(Update Sequence)的計算……………………………………………50
5.4 可靠度更新單元…………………………………………………………………51
5.5 軟輸出維特比解碼器架構………………………………………………………52
5.6 雙向軟輸出維特比演算法之資料流程…………………………………………53
5.7模擬結果………………………………………………………………………56
5.8 合成與最後結果(Post simulation) ………………………………………………..58
第六章 結論 60
參考文獻

[1]Jinghu Chen, Shu Lin and Chengqi Xu, “Bi-Directional SOVA Decoding for Turbo-Codes” IEEE Commun. Lett., vol. 4, no. 12, pp. 405-407, Dec. 2000.
[2]L. Papke and P. Robertson, “Improved decoding with the SOVA in a parallel concatenated (turbo-code) scheme,” in Proc. ICC96, pp. 102-106, 1996.
[3]Sanjay Sharma, Sanjay Attri and R.C. Chauhan “A Simplified and Efficient Implementation of FPGA-Based Turbo Decoder”, in Performance, Computing, and Communications Conference, pp. 207 – 213, April 2003.
[4]Zhongfeng Wang and Keshab K. Parhi, “High Performance, High Throughput Turbo/SOVA Decoder Design,” IEEE Trans. on Commun., vol. 51, no. 4, pp. 570-579, Apr. 2003.
[5]Engling Yeo, Stephanie A. Augsburger, W. Rhett Davis and Borivoje Nikolic, "A 500-Mb/s Soft-Output Viterbi Decoder," IEEE Journal of Solid-State Circuits, vol. 38, no. 7, pp. 1234-1241, July 2003.
[6]Yu-Chuan Chang and Jenn-Kaie Lain, “Improved Decoding with the Bi-Directional SOVA for Turbo Codes,” in vtc2005spring, Sweden, Stockholm, 2005.
[7]Claude Berrou, Patrick Adde, Ettiboua Angui and Stephane Faudeil, “A Low Complexity Soft-Output Viterbi Decoder Architecture”, in ICC 93, vol.2, pp. 737-740, May 1993.
[8]Chung-Hsuan Wang, Wei-Ting Wang and Chi-chao Chao, “A Unified Structure of Trellis-Based Soft-Output Decoding Algorithms for Turbo Codes”, IEEE Trans. on Commun., vol. 52, no. 8, Aug 2004.
[9]Zhongfeng Wang and Keshab K. Parhi, “Decoding Metrics and Their Applications in VLSI Turbo decoders”, in ICASSP ''00, vol. 6, pp. 3370 – 3373, June 2000.
[10]M. Fossorier, F. Burkert, S. Lin, and J. Hagenauer, “On the equivalence between SOVA and max-log-MAP decoding,” IEEE Commun. Lett., vol. 2, pp. 137-139, May 1998.
[11]Patrice Robertson, Emmanuelle Villebrun and Peter Hoeher, “A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain” IEEE Int. Commun. Conf., vol. 2 , PP. 1009 -1013, Jun 1995.
[12]G. Battail, “Ponderation des symboles decodes par l’algorithme de viterbi,” Ann. Telecommun., vol 42, pp. 31-38, Jan. 1987.
[13]Zhongfeng Wang, Hiroshi Suzuki and Keshab K. Parhi, “EFFICIENT APPROACES TO IMPROVING PERFORMANCE OF VLSI SOVA-BASED TURBO DECODERS”, in IEEE ISCAS 2000, vol. 9, pp. 287-290 May. 2000.
[14]Taek Won Kwon, Dae Won Kim, Woo Tae Kim, Eon Kyeong Joo, Jun Rim Choi, Pyung Choi, Jun Jin Kong, Sung Han Choi, Won Hee Chung and Ki Won Lee, “A MODIFIED TWO-STEP SOVA-BASED TURBO DECODER FOR LOW POWER AND HIGH PERFORMANCE”, in IEEE TENCON 1999, vol. 1, pp. 297-300 Sept 1999.
[15]Yan Wang, Chi-Ying Tsui and Roger S. Cheng, “A Low Power VLSI Architecture of SVOA-based Turbo-code decoder using Scare State Transition Scheme”, in IEEE ISCAS, vol. 9, pp. 283-286, May 2000.
[16]Mahmoud El-Assal and Magdy Bayoumi, “LOW POWER SOVA ARCHITECHTURE USING BI-DIRECTIONAL SCHEME” in IEEE, pp. 277-280, 2002.
[17]Lingyan Sun, Toshihiro Horigome and B. V. K. Vijaya Kumar, “A High-Throughput, Field Programmable Gate Array Implementation of Soft Output Viterbi Algorithm for Magnetic Recording”, IEEE Trans. on Commun., vol. 40, no.4, pp. 3081-3083. July 2004.
[18]Jinhong Yuan and Branka Vucetic, “Turbo Code Performance on Rician Fading Channels”, in IEEE ICC ''99, vol.1, pp. 83 – 87, June 1999.
[19]Wenzhen Li, Vimal K. Dubey and Choi Look Law, “The Performance of Turbo Coding Over Power-Controlled Fading Channel in Ka-Band LEO Satellite Systems”, IEEE Trans. on Vehi. Tech., vol. 52, no. 4, pp. 1032-1043, July 2003.
[20]Todd A. Summers and Stephen G. Wilson, “SNR Mismatch and Online Estimation in Turbo Decoding”, IEEE Trans. on Commun., vol. 46, no. 4, pp. 421-423, April 1998.
[21]Bernard Sklar, “How I Learned to Love the Trellis-using the viterbi algorithm for signal equalization and detection”, IEEE Signal processing magzine, pp. 87-102, May 2003.
[22]Yun-Nan Chang, “DESIGN OF SOFT-OUTPUT VITERBI DECODERS WITH HYBRID TRACE-BACK PROCESSING”, in IEEE ISCAS ''03, vol. 2 pp. II-69 - II-72, May 2003.
[23]Zhongfeng Wang, Hiroshi Suzuki and Keshab K. Parhi etc.., “VLSI IMPLEMENTATION ISSUES OF TURBO DECODER DESIGN FOR WIRELESS APPLICATIONS”, in IEEE SiPS 99, pp. 503- 512, Oct. 1999.
[24]S. Papaharalaos, P. Sweeney and B.G. Evans, “Modification of branch metric calculation to improve iterative SOVA decoding of turbo codes”, IEE ELECTRONICS LETTERS, vol. 39, no. 19, Sept 2003.
[25]Yasmine Fahmy , Hala A.G. Abdel Kader, Magdi M.S. El-Soudani, “in IEEE Melecon 2002, pp. 168-172, May 2002.
[26]L. Hanzo, T.H. Liew and B.L. YEAP, Turbo Coding, Turbo Equalisation and Space-Time Coding-for Transmission over Fading Channels. JOHN WILEY & SONS, LTD 2002.
[27]Simon Haykin, COMMUNICATION SYSTEMS. JOHN WILEY & SONS, LTD, 4 th Ed. 2001.