渦輪碼(Turbo Code)是在1993年由Berrou等人所提出，其錯誤更正能力很接近理論上的雪農極限(Shannon-limit)。由於它強大的錯誤更正能力，渦輪碼被應用在第三代行動通訊等無線通訊傳輸系統，如WCDMA和CDMA2000等。渦輪碼解碼器核心單元的軟式輸入及軟式輸出(Soft-input soft output)解碼器，主要由最大機率(Maximum-A-Posterior)演算法和軟式輸出維特比(SOVA)演算法所構成。前者的解碼效能最佳但計算複雜度很高，後者解碼效能較差但大幅降低了計算複雜度而更適合硬體實現。

　　在此，我們針對軟式輸出維特比演算法中更新可靠度的兩種方式，並提出兩種新的可靠度更新方式。主要的概念是另找一條比競爭路徑更能代表輸出相反於最大可能路徑的最佳路徑。在經過模擬後，由第一種方式改良的軟式輸出維特比演算法在增加可接受的複雜度下解碼效能勝於Hagenauer軟式輸出維特比演算法。不僅如此，由第二種方式改良的軟式輸出維特比演算法，在增加少許計算複雜度的情況下勝過Battail軟式輸出維特比演算法的效能。最後我們對改良式軟式輸出維特比演算法做評估，並由渦輪碼模擬其解碼效能。

　　Turbo codes, introduced by Berrou et. al. in 1993, have been shown to be capable of performing close to the Shannon Limit. Due to its powerful error correction capability, turbo coding has been adopted as a channel coding scheme for several 3rd generation mobile systems, such as WCDMA and CDMA2000. The design of the core Soft-In Soft-Out (SISO) unit used in turbo code decoder is based on either the Maximum A-Posteriori Algorithm (MAP) or the Soft-Output Viterbi Algorithm (SOVA). Although the former provides the best performance in terms of minimizing the decoding errors, nevertheless, the latter in which bit error performance is traded for a reduction in decoding complexity is more suitable for practical implementation.

　　In this thesis, we focus on the two different updating rules of SOVA and propose two new updating rules. Our basic idea is to find a third path beside the competitor path, which more likely represents the best path with bit opposite to the final survivor path in the trellis. The simulation results verify that modified SOVA with the first proposed updating rule has a performance better than the Hagenauer SOVA with a moderate increase in complexity. Moreover, the modified SOVA with the second proposed updating rule outperforms the Battail SOVA with only a very small increase in complexity. Evaluations of the modified SOVA are presented, and the simulated turbo code performance results are shown.

[1] S. Lin, D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Prentice-Hill, 1983.
[2] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon Limit Error-Correcting Coding: Turbo Codes,” in Proc. IEEE Int. Conf Communications, May 1993, pp. 1064–1070.
[3] 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.
[4] 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.
[5] J. Hagenauer and P. Hoeher, “A Viterbi algorithm with soft-decision outputs and its applications,” in Proc. IEEE GLOBECOM, Dallas, Texas, Nov. 1989, pp. 47.11–47.17.
[6] G. Battail, “Ponderation des Symboles Decodes par L’Algorithme de Viterbi,” Annales des Telecommunications, vol. 42, no. 1-2, pp. 31–38, 1987.
[7] J. Hagenauer and L. Papke, “Decoding turbo codes with the soft-output Viterbi algorithm (SOVA),” in Proc. IEEE Int. Symp. Inform. Theory, Trondheim, Norway, 1994, p. 164.
[8] J. Hagenauer, “Source-controlled channel decoding,” IEEE Trans. Commun., vol. 43, pp. 2449-2457, Sept. 1995.
[9] J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. Inform. Theory, Mar. 1996, pp. 429-445.
[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] L. Lin and R. S. Cheng, “Improvements in SOVA-based decoding for turbo codes,” in Proc. IEEE Int. Conf. Communications, June 1997, pp. 1473-1478.
[12] D. Wang and H. Kobayashi, “High-performance SOVA decoding for turbo codes over cdma2000 mobile radio,” vol. 1, pp. 189-193, Digital Object Identifier 10.1109/MILCOM.2000.904938.
[13] O. Joeressen, M. Vaupel, and H. Meyr, “High-speed VLSI architectures for soft-output Viterbi decoding,” in Proc. Int. Conf. Application-Specific Array Processors, Aug. 1992, pp. 373-384.
[14] C. Berrou, P. Adde, E. Angui, and S. Faudeil, “A low complexity soft-output Viterbi decoder architecture,” in Proc. IEEE Int. Conf. Communications, 1993, pp. 737-740.
[15] D. Garret and M. Stan, “Low power architecture of the soft-output Viterbi algorithm,” in Proc. Int. Symp. Low-Power Electronics and Design, 1998, pp. 262-267.
[16] J. Petersen, “Implementierungsaspekte zur symbol-by-symbol MAP decodierung von faltungscodes,” in Proc. ITG Tagung, Codierung für Quelle, Kanal and Übertragung, pp. 41-48, Oct. 1994.
[17] J. Chen, S. Lin, and C. Xui, “Bi-directional SOVA decoding for turbo-codes,” IEEE Commun. Lett., vol. 4, no. 12, pp. 405-407, Dec. 2000.
[18] B. Sklar, “A primer on turbo code concepts,” IEEE Commun. Mag., Dec. 1997, pp.94-102.
[19] J. P. Woodard and L. Hanzo, “Comparative study of turbo decoding techniques: an overview,” IEEE Tran. Vehicular Technology, vol. 49, no. 6, November 2000.
[20] O. Acikel and W. E. Ryan, “Punctured turbo codes for BPSK/QPSK channels,” IEEE Trans. Commun., vol. 47, pp. 1315-1323, Sept. 1999.
[21] F. Babich, G. Montorsi, and F. Vatta, “Design of rate-compatible punctured turbo (RCTP) codes,” in Proc. Int. Conf. Commu., New York, USA, Apr. 2002, pp. 1701-1705.
[22] M. A. Kousa and A. H. Mugaibel, “Puncturing effects on turbo codes,” in Proc. IEE Comm., vol. 149, no. 3, pp. 132–138, June 2002.
[23] F. Mo, S. C. Kwatra and J. Kim, “Analysis of puncturing pattern for high rate turbo codes,” in Proc. Military Comm. Conf. (MILCOM’99), New Jersey, USA, Oct. 1999, pp. 547-500.
[24] I. Land and P. Hoeher, “Partially systematic rate 1/2 turbo codes,” in Proc. Int. Symp. Turbo Codes, Brest, France, pp. 287-290, Sept. 2000.
[25] I. A. Chatzigeorgiou, M. R.D. Rodrigues, I. J. Wassell and R. Carrasco, “Punctured Binary Turbo-Codes with Optimized Performance,” IEEE 62nd Semiannual Vehicular Technology Conference, Dallas, Texas, USA, Sept. 2005.
[26] L. Papke and P. Robertson, “Improved decoding with the SOVA in a parallel concatenated (turbot-code) scheme,” in Proc. IEEE Int. Conf. Communications, 1996, pp. 102-106.