臺灣博碩士論文加值系統

在目前大部份的通訊系統中，捲積碼廣泛的被使用來增加傳輸資料的可靠性。維特比解碼演算法是最常見的捲積碼解碼技術，它藉由大量的分支計量值運算來找到最有可能的解碼路徑。
本研究中，我們發現在捲積碼的籬狀圖分支中存在的分支對稱關係，而且分支對稱關係可以由該碼的生成序列得到。利用這樣的對稱關係，在不影響效能的情況下，維特比解碼器的分支計量值運算可以大量的被減少。配合分支對稱關係的使用，我們提出一個通用於所有碼率的蝴蝶結構。利用分支對稱關係，這樣的蝴蝶結構可以大大的簡化維特比解碼器的實現。我們採用一些熟知的最佳捲積碼來評估該蝴蝶結構的實用性。結果顯示這些碼大多可利用我們提出來的蝴蝶結構來降低它們的分支計量值運算至原來所需的1/2或1/4。
本研究進一步提出一個搜尋演算法來尋找新型捲積碼。在捲積碼的搜尋演算法上加入分支對稱關係，這些新型碼除了擁有好的錯誤修正能力外，亦具有高的分支對稱關係。本研究已找到很多具高分支對稱關係的新型碼。這些新型碼和之前的最佳碼相比，它們擁有相近的錯誤修正能力，但利用分支對稱關係，這些新型碼的分支計量值運算量可進一步被減少為原來所需的1/4、1/8 或1/16。

In recent communication systems, convolutional codes are widely used to increase the reliability of transmission. The Viterbi decoding algorithm is the most popular decoding scheme of convolutional codes, which finds the most-likely path by huge branch metric computation.
In this dissertation, we show that trellis of convolutional codes has inherent symmetry and can be derived from generator sequences. By exploiting the inherent branch symmetry, the branch metric computation of the Viterbi decoder can be reduced significantly without any performance loss. Additionally, a butterfly structure for all rates k/n convolutional codes is proposed to exploit the branch symmetry efficiently in the Viterbi decoder. The applicability of the butterfly structure is validated by the best codes of rates 1/2, 2/3, and 3/4. The results show that most of the best codes can apply the butterfly structure to reduce their branch metric computation by a factor of 2 or 4.
Furthermore, under the branch symmetry consideration we propose a modified search algorithm to find new convolutional codes with not only high error-correcting capability but also high branch symmetry. Many new codes with high branch symmetry are found in this dissertation. With similar error-correcting capability to previous best codes, the branch metric computation of these new codes can be reduced by a factor of 4, 8, or 16 by exploiting their branch symmetry.

ENGLISH ABSTRACT I
CHINESE ABSTRACT II
ACKNOWLEDGEMENTS III
LIST OF FIGURES VI
LIST OF TABLES VIII
CHAPTER 1 INTRODUCTION 1
1.1 Motivation and Objective 1
1.2 Literature Review 2
1.3 Organization 2
CHAPTER 2 CONVOLUTIONAL CODES 4
2.1 Introduction 4
2.2 Convolutional Codes 6
2.3 Viterbi Decoding Algorithm 11
2.4 Computational Complexity of the Viterbi Decoder 13
CHAPTER 3 BRACNH SYMMETRY AND BUTTERFLY STRUCTURE 14
3.1 Introduction 14
3.2 Traditional Butterfly Structure for Rate 1/n Codes 15
3.3 Low Complexity Radix-4 Butterfly Design 16
3.4 Branch Symmetry in Rate 1/n Codes 29
3.5 Butterfly Structure for Rate 2/n Codes 33
3.6 Butterfly Structure for All Rates k/n Codes 39
CHAPTER 4 LOW COMPLEXITY CONVOLUTIONAL CODES 50
4.1 Introduction 50
4.2 The Proposed Search Algorithm 50
4.3 Search Results and Performance Evaluation 54
CHAPTER 5 CONCLUSIONS AND FUTURE WORKS 62
5.1 Conclusions 62
5.2 Future Works 63
REFERENCES 65
PUBLICATION LIST 71
VITA 73

[1]B. Sklar, Digital Communications- Fundamentals and Applications. Prentice Hall, 1988.
[2]A. J. Viterbi, “Convolutional codes and their performance in communication systems,” IEEE Trans. Commun., vol. COM-19, pp. 751-772, Oct. 1971.
[3]A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inf. Theory, vol. IE13, pp. 260-269, April 1967.
[4]G. D. Forney Jr. “The Viterbi Algorithm,” Proc. IEEE , vol 61, pp. 268 - 278, March 1973.
[5]H. I. Lou, “Implementing the Viterbi algorithm,” IEEE Signal Processing Magazine, pp.42-52, Sep. 1995.
[6]H. Hendrix, “Viterbi Decoding Techniques in the TMS320C54x Family,” Texas Instruments, June 1996.
[7]M. D. Shieh, C. M. Wu, H. H. Chou, M. H. Chen and C. L. Liu, “Design and implementation of a DAB channel decoder,” IEEE Trans. on Consumer Electronics, Vol. 45, No. 3, pp. 553-556, Aug. 1999.
[8]P. K. Singh and S. Jayasimha, “A low-complexity, reduced-power Viterbi algorithm,” in Proc. 12th International Conf. on VLSI Design, Goa, India, pp 61-66, Jan. 1999.
[9]G. Kang and P. Zhang “The implementation of Viterbi decoder on TMS320C6201 DSP in W-CDMA system,” in Proc. IEEE International Conf. on Communication Technology, vol.2, pp. 1693-1696, 2000.
[10]J. J. Chang, D. J. Hwang and M. C. Lin, “Some extended results on the search for good convolutional codes,” IEEE Trans. Inform. Theory, Vol. 43, No.5, pp. 1682-1697, Sept. 1997.
[11]D. G. Daut, J. W. Modestino and L. D. Wismer, “New short constraint length convolutional codes constructions for selected rational rates,” IEEE Trans. Inform. Theory, vol. IT-28, pp. 794-800, Sept. 1982.
[12]Paaske, “Short binary convolutional codes with maximal free distance for rates 2/3 and 3/4,” IEEE Trans. Inform. Theory, vol. IT-20, pp. 683–688, September 1974.
[13]S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall, 1995.
[14]I. E. Bocharova and B. D. Kudryashov, “Rational rate punctured convolutional codes for soft-decision Viterbi decoding,” IEEE Trans. Inform. Theory, vol. 43, No. 4, pp. 1305-1313, July 1997.
[15]K. J. Larsen, “Short convolutional codes with maximal free distance for rates 1/2, 1/3, and 1/4,” IEEE Trans. Inform. Theory, vol. IT-19, pp.371-372, May 1973.
[16]P. Frenger, P. Orten and T. Ottosson, “Convolutional codes with optimum distance spectrum,” IEEE Communications Letters, Vol. 3, No. 11, pp. 317-319, Nov. 1999.
[17]A. Graell i Amat, G. Montorsi and S. Benedetto, “A new approach to the construction of high-rate convolutinal codes,” IEEE Comunications Letters, vol. 5, no. 11, pp. 453-455, Nov. 1989.
[18]P. Elias, “Coding for Noisy Channels,” IRE Convention Record, pt. 4, pp. 37-46, Mar. 1955.
[19]S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Prentice-Hall, 2004.
[20]Proakis, Digital Communications, McGraw-Hill, 1995.
[21]R. Johannesson and K. Zigangirov, Fundamentals of Convolutional Coding, IEEE Press, New York, 1999.
[22]J. A. Heller and I. M. Jacobs, “Viterbi decoding for satellite and space communications,” IEEE Transactions on Commun., vol. COM-19, pp. 835-848, October 1971.
[23]P. J. Black and T. H. Meng, “A 140-Mb/s, 32-state, radix-4 Viterbi decoder,” IEEE J. Solid-State Circuits, vol. 27, pp. 1877–1885, Dec. 1992.
[24]A. K. Yeung and J. M. Rabaey, “ A 210Mb/s radix-4 bit-level pipelined Viterbi decoder,” in Proc. IEEE International Solid-State Circuit Conf., pp. 88-89, Feb. 1995.
[25]E. Paaske and J. D. Andersen, “High Speed VITERBI Decoder Architecture,” First. ESA Workshop on Tracking, Telemetry and Command Systems, ESTEC June 1998.
[26]E. Casseau and E. Luthi, “Architecture of a high-rate VLSI Viterbi decoder,” in Proc. Third International Conf. on Electronics, Circuits and System, Rodos, Greece, pp. 21-24, October 1996.
[27]R.V.K Pillai and P. D’Arcy, “On high speed add-compare-select for Viterbi decoders,” in Proc. Canadian Conf. on Electrical and Computer Engineering, pp. 1193-1198, May 2001.
[28]Y. H. Hsu, C. Y. Hsu and T. S. Kuo, “Low Complexity Radix-4 Butterfly Design for the Viterbi Decoder,” in Proc. IEEE 64th Vehicular Technology Conf., Montreal, Cannada, Sept. 2006.
[29]C. Y. Hsu, T. S. Kuo and Y. H. Hsu, “Low Complexity Radix-4 Butterfly Design for the Soft-Decision Viterbi Decoder,” Journal of Microprocessors and Microsystems. (Accepted in February, 2, 2006)
[30]ETS 300 401: Radio broadcasting system; Digital Audio Broadcasting (DAB) to mobile, portable and fixed receivers, Feb. 1995.
[31]Eureka-147, Digital audio broadcasting system, www.eurekadab.org, April 2002.
[32]IEEE, IEEE Standard VHDL Language Reference Manual, std 1076-1933, 1933.
[33]P. J. Ashenden, The Designer’s Guide to VHDL, 2nd Edition, Morgan Kaufmann Publishers, 2002.
[34]Xilinx Inc., http://www.xilinx.com.
[35]C. Y. Hsu and T. S. Kuo, “A butterfly structure for rate 2/n convolutional codes,” IEICE Trans. on Fundamentals of Electronics, Communications and Computers Science, vol.E89-A, No. 2, pp.630-632, Feb. 2006.
[36]C. Y. Hsu and T. S. Kuo, “A butterfly structure for rate 2/n convolutional codes,” Proceedings of 5th International Conference on Information, Communication and Signal Processing, Tailand, pp. 776-780 Dec. 2005.
[37] T. S. Kuo and C. Y. Hsu, “A butterfly structure for rate k/n convolutional codes,” Proceedings of the IEEE Symposium on Signal Processing and Information Technology, Greece, pp. 528-533, Dec., 2005.
[38]T. S. Kuo and C. Y. Hsu, “Butterfly structure for Viterbi decoders of all rates k/n,” IEICE Trans. on Fundamentals of Electronics, Communications and Computers science, vol.E90-A, No. 2, pp.37-44, Feb. 2007.
[39]C. Y. Hsu and T. S. Kuo, “Low Complexity Convolutional Codes of Rate 2/n,” Journal of the Chinese Institute of Engineers. (Accepted in September, 3, 2006)
[40]C. Y. Hsu and T. S. Kuo, “Low Complexity Convolutional Codes Using the Branch Symmetry,” IEEE communications letters. (Submitted in October, 30, 2006)
[41]J. L. Massey and M. K. Sain, “Inverses of linear sequential circuits,” IEEE Trans. Comput., Vol. C-17, pp.330-337, Apr. 1968.
[42]L. R. Bahl. C. D. Cullum. W. D. Frazer, and F. Jelinek, “An efficient algorithm for computing the free distance,” IEEE Trans. Inform. Theory, vol. IT-18, pp. 437-439, Nov. 1972.
[43]K. J. Larsen, “Comments on �SAn efficient algorithm for computing the free distance�S ,” IEEE Trans. Inform. Theory, vol. IT-19, pp. 577-579, July 1973.
[44]M. Cedervall and R. Johannesson, “A fast algorithm for computing distance spectrum of convolutional codes,” IEEE Trans. Inform. Theory, Vol. IT-35, No. 6, pp.1146-1159, Nov. 1989.
[45]J. Conan, “The weight spectra of some short low-rate convolutional codes,” IEEE Trans. Commun., vol. COM-32, pp. 1050-1053, Sept. 1984.
[46]R. van Nee and R. Prasad, OFDM for Wireless Multimedia Communications, Artech House Publishers, Boston, 2000.
[47]C. Schlegel, Trellis Coding, IEEE Press, New York, 1997.
[48]E. Biglieri, D. Divsalar, P. J. Mclane and M. K. Simon, Introduction to Trellis-Coded Modulation with Applications, Macmillan, Canada, 1991.