臺灣博碩士論文加值系統

在數位通訊系統領域中，維特比演算法（Viterbi Algorithm）為一公認的有效的近似解碼演算法，並已廣泛地應用在迴旋碼之解碼。迴旋碼因為具有良好的錯誤控制能力﹙Error- Control Performance﹚而廣泛地被應用在各通訊系統，例如行動電話、無線通訊、數位電視、數位廣播等等。
本論文使用MSB-first ACSU架構以加速Viterbi解碼器的整體處理速度。在實現高速Viterbi解碼器時，其內部的ACS單元為主要瓶頸，但是藉著在ACS單元內的各Critical Path之間取得平衡，且縮短各Critical Path之間的差距，以縮短Viterbi整體的Critical Path，提升速度。同時，使用者可自行調整碼率及記憶級數等設計參數，提供了有效且具彈性的通道解碼功能的實現，經由IP 模組化設計，使用者可有效加速晶片設計與實現之時程、降低開發的成本、提升性能及效率。

The Viterbi algorithm, widely used in digital communication systems, is known to be an efficient method for the realization of maximum likelihood decoding of convolution codes. Convolution codes are widely used in many communication systems due to their excellent error control performance.
In this thesis, a most-significant-bit (MSB)-first ACS unit is used to implement a high speed Viterbi decoder. The ACS unit is the main bottleneck on the decoding speed of a Viterbi decoder. By balancing the settling time of different paths in the ACS unit, the length of the critical path is reduced as close as possible to the iteration bound in the ACS unit. We supply a flexible IP implementation of channel decoding to easily adjust code rate and memory progression variable. With the help of our IP modules, the chip design time can be reduced efficiency.

摘 要 IV
ABSTRACT V
誌謝 VI
第一章 簡介 1
1.1 前言 1
1.2矽智產簡介 2
1.3研究動機與目的 3
1.4 章節概論 4
第二章 迴旋碼與維特比演算法 5
2.1 迴旋碼(Convolutional code) 5
2.2 維特比演算法(Viterbi Algorithm) 9
第三章 高速維特比解碼器之架構 16
3.1 維特比解碼器之主要單元 16
3.1.1 蝴蝶模組（Butterfly Module） 17
3.1.2 分支計量運算單元（BMU） 19
3.1.3 加-比較-選擇運算單元（ACSU） 20
3.1.4 存活記憶體單元(SMU) 22
3.2 硬體架構分類 22
3.3 Bit-Level Parallelization 23
3.4 Look-Ahead Technique 27
3.5 Retiming Cut-Set 29
第四章 高速維特比IP產生器之實現 36
4.1 可參數化通道編解碼IP模組產生器 36
4.2 規格與應用 37
4.3 IP產生器之驗證 39
4.4 數據比較 43
第五章 結論 44
附錄A　適用於腓特比解碼器之迴旋碼碼率 45
參考文獻 46

[1] G. Ungerboeck, “Channel coding with multilevel/phase signals,” IEEE Trans. Inf. Theory, Vol. 28, No. 1, pp. 55-67, Jan 1982.
[2] J. Viterbi, “Convolutional Codes and their Performance in Communication Systems,” IEEE Trans. Communication, Vol. 19, No. 5, pp. 751-772, Oct. 1971.
[3] G. Fettweis and H. Meyr, “Parallel Viterbi algorithm implementation: Breaking the ACS-bottleneck,” IEEE Trans. Commun., Vol. 37, pp. 785–790, Aug. 1989.
[4] P. Black and T. Meng, “A 140 Mb/s 32-state radix-4 Viterbi decoder,”IEEE J. Solid-State Circuits, Vol. 27, pp. 1877–1885, Dec. 1992.
[5] Jung-Gi Baek, Sang-Hun Yoon, Jong-Wha Chong, “MEMORY EFFICIENT PIPELINED VITERBI DECODER WITH LOOK-AHEAD TRACE BACK”, 2001, IEEE.
[6]G. Fettweis and H. Meyr, “High rate Viterbi processor: A systolic array solution,” IEEE J. Select. Areas Commun., Vol. 8, pp. 1520–1534, Oct. 1990.
[7] Keshab K. Parhi,“An Improved Pipelined MSB-First Add-Compare-Select Unit Structure for Viterbi Decoders,“IEEE Transactions on circuits and systems-I: Regular papers, vol. 51, No. 3, March 2004.
[8] J. Hagenauer, and P. Hoeher, “A Viterbi Algorithm with Soft-Decision Outputs and its Applications,” IEEE Conf. Global Telecommunications, pp. 1680-1686, Nov. 1989.
[9] K. Chadha, and J.R. Cavallaro, “A Reconfigurable Viterbi Decoder Architecture,” Thirty-Fifth Asilomar Conf. Signals, Systems and Computers, Vol. 1, 4-7, pp. 66-71, Nov. 2001.
[10] R.Burger, G Cesana, M. Paolini, M. Turolla, S. Vercelli, “A Fully Synthesizable Parameterized Viterbi Decoder,” IEEE Custom Integrated Circuits Conference,1999.
[11] C. B. Shung, H. D. Lin, R. Cypher, P. H. Siegel, and H. K. Thapar, “Area-efficient architectures for the Viterbi algorithm – Part I : theory,” IEEE Transactions on Communications, Vol. 41, No. 4, pp. 636-543, Apr. 1993.
[12] C. B. Shung, H. D. Lin, R. Cypher, P. H. Siegel, and H. K. Thapar, “Area-efficient architectures for the Viterbi algorithm – Part II : applications,” IEEE Transactions on Communications, Vol. 41, No. 4, pp. 802-807, May 1993.
[13] J. Sparso, H. N. Jorgensen, E. Paaske, S. Pedersen, and T. Rubner-Petersen: An area-efficient topology for VLSI implementation of Viterbi decoders and other shuffle-exchange type structures,” IEEE journal of Solid-State Circuit , Vol, 26, No. 2, pp. 90-96, Feb. 1991.
[14] T. Gemmeke, M. Gansen, and T. G. Noll, “Implementation of scalable power and area efficient high-throughput Viterbi Decoder” IEEE Journal of Solid-State Circuit, Vol. 37, No. 7, pp. 941-948, Jul. 2002.
[15] Gerhard Fettweis, and Heinrich Meyr, “High-Rate Viterbi Processor: A Systolic Array Solution”, IEEE Journal on Selected Areas in Communications, Vol. 8, No. 8, Oct. 1990.
[16] Gerhard Fettweis, and Heinrich Meyr, “A 100MBIT/S VITERBI DECODER CHIP : NOVEL ARCHITECTURE AND ITS REALIZATION,” 1990, IEEE.
[17] Gerhard Fettweis, and Heinrich Meyr, “High-Speed Parallel Viterbi Decoding : Algorithm and VLSI-Architecture,” May 1991, IEEE Communications Magazine.
[18] A. Yeung and J. Rabaey, “A 210 Mb/s radix-4 bit-level Viterbi decoder,” in Proc. IEEE Int. Solid-State Circuits Conf., Feb. 1995, pp. 88–89.
[19] V. S. Gierenz, O.Weiss, T. G. Noll, I. Carew, J. Ashley, and R. Karabed, “A 550 Mb/s radix-4 bit-level pipelined 16-state 0.25-_m CMOS Viterbi decoder,” in Proc. IEEE Int. Conf. Application-Specific Systems, Architectures, and Processors, 2000, pp. 195–201.
[20] Peter J. Black, and Teresa H.-Y. Meng, “A 1-Gb/s, Four-State, Sliding Block Viterbi Decoder”, IEEE Journal of Solid-State Circuits, Vol. 32, No.6, June 1997.
[21] R.Burger, G Cesana, M. Paolini, M. Turolla, S. Vercelli, “A Fully Synthesizable Parameterized Viterbi Decoder,” IEEE Custom Integrated Circuits Conference,1999.
[22] 葉丞淵，具多目標式腓特比解碼器之矽智財產生器，國立台北科技大學，電腦通訊與控制研究所，碩士論文，民91年。