近年來，無線通訊之蓬勃發展不僅帶給人們極大的便利，更滿足人們的各種需求，也因此發展出許多新世代的無線通訊系統。其中，適用於短距離及低功率的超寬頻無線通訊技術，是一種常被熱烈討論的通訊系統。此系統會在傳送資料前，使用迴旋碼編碼法加入額外的位元，以提升資料在傳送過程中抵抗雜訊的能力。在接收端，最常被用來對迴旋碼進行解碼的技術是維特比演算法，其特色是可以將受到雜訊干擾而錯誤的資料更正回來，且擁有最大近似的解碼效果。
由於維特比演算法的計算量很大，所以當硬體實現被考量時，功率消耗會是一個重要的議題，特別是可攜式電子產品的電力來源通常有限，因此設計一個低功率的維特比解碼器是有必要的。本論文探討一種適應性維特比演算法—T-演算法，此法透過定義一個臨界值可以減少所需的計算量。我們研究發現，在不同的階段使用變動的臨界值，可以比使用固定的臨界值降低更多的計算量。本論文針對T-演算法提出一個有效的低功率電路設計，除了使用變動的臨界值外，也使用時脈閘控技術來進一步減少電路的功率消耗。
論文提出的低功率維特比解碼器是用Verilog 硬體描述語言進行電路設計並使用Artisan TSMC 0.18μm標準元件庫進行合成實現，其合成結果為75848個邏輯閘數，工作頻率則為140MHz。和其他維特比解碼器比較起來，我們提出的電路需要最少的功率消耗。

Advanced wireless communication systems not only offer variously convenient services, but also satisfy different requirements for human being. Hence, many wireless communication systems are developed in the recent years. In them, the ultra wideband wireless communication system is one of the most popular systems. To make the transmitted data error-resilient, it adds the extra bits into original data by using convolution coding. Then, viterbi algorithm is used to obtain the maximum likelihood results for decoding the convolution codes.
The computation complexity of viterbi decoder is quite large, so the power consumption becomes an important issue. The power source for capable portable devices is limited. Hence, it would be nice to have a low power viterbi decoder. In this thesis, we analysis the performance of an adaptive viterbi algorithm - T-algorithm which reduces the computation complexity by using a threshold value, and find that the variable threshold value can be used to further reduce computation complexity. By using T-algorithm with various threshold values and clock gating technique, we develop a low power VLSI architecture of viterbi decoder.
The VLSI architecture of our viterbi decoder was implemented by using Verilog HDL. We used Design Vision to synthesize the design with TSMC’s 0.18μm cell library. The synthesis results show that our design occupies 75848 gate counts at the clock rate of 140 MHz. As compared with other viterbi decoders, our design requires the lowest power consumption.

[1] High rate ultra wideband PHY and MAC standard, ECMA Standard 368, Dec. 2005.
[2] P. Elias, “Error-free coding,” IRE Trans. Inform Theory, vol. IT-4, pp.29–37, Sept. 1954.
[3] A.J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Transactions on Information Theory, vol. IT-13, April, 1967, pp. 260-269.
[4] A. Batra, J. Balakrishnan, and A. Dabakand, et al., “Multi-band OFDM physical layer proposal for IEEE 802.15 Task Group 3a,” IEEE P802.15-03/268r3, March 2004.
[5] P.A. Bengough and S.J. Simmons, “Sorting-based VLSI architectures for the M-algorithm and T-algorithm trellis decoders,” IEEE Trans. Commun., vol. 43, no. 2, Feb. 1995, pp. 514–522.
[6] M.H. Chan, W.T. Lee, M.C. Lin, and L.G. Chen, “IC design of an adaptive viterbi decoder,” IEEE Trans. Consum. Electron., vol. 42, no.1, Feb. 1996, pp. 52–62.
[7] J.J. Kong and K.K. Parhi, “Low-latency architectures for high-throughput rate Viterbi decoders,” IEEE Trans. VLSI Systems, vol. 12, no. 6, June 2004, pp. 642–651.
[8] H. Kim, H. Son, T. Roska, L.O. Chua, “High-performance Viterbi decoder with circularly connected 2-D CNN unilateral cell array,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 52, no. 10, Oct. 2005, pp. 2208–2218.
[9] F. Sun and T Zhang, “Parallel high-throughput limited trellis decoder VLSI design,” IEEE Trans. VLSI Systems, vol. 13, no. 9, Sept. 2005, pp. 1013–1022.
[10] R. Cypher and C.B. Shung, “Generalized trace back techniques for survivor memory management in the viterbi algorithm,” in Proc. GLOBECOM, vol. 2, pp. 1318–1322, Dec. 1990.
[11] G. Feygin and P. Gulak, “Architectural tradeoffs for survivor sequence memory management in viterbi decoders,” IEEE Trans. Commun., vol. 41, no. 3, Mar. 1993, pp. 425–429.
[12] C. Rader, “Memory management in a viterbi decoder,” IEEE Trans. Commun., vol. 29, no. 9, Sep. 1981, pp. 1399–1401.
[13] G.D. Forney, Jr., “Convolutional codes Ⅱ: maximum likelihood decoding,” Inform. Control, pp. 222-266, July 1974.
[14] J.A. Heller and I.M. Jacobs, “Viterbi decoding for satellite and space communication,” IEEE Trans. Commun. Technol., vol. COM19, no. 5, Oct. 1971, pp. 835-848.
[15] F. Chan and D. Haccoun, “Adaptive viterbi decoding of convolutional codes over memoryless channels,” IEEE Trans. Commun., vol. 45, Nov. 1997, pp. 1389–1400.
[16] J. Jin and C.Y. Tsui, “Low-power limited-search parallel state viterbi decoder implementation based on scarce state transition,” IEEE Trans. VLSI Systems, vol.15, no. 10, Oct. 2007, pp. 1172-1176.
[17] D.J. Lin, C.C. Lin, C.L. Chen, H.C. Chang, and C.Y. Lee, “A low-power viterbi decoder based on scarce state transition and variable truncation length,” in Proc. IEEE ISCAS, pp. 99–102, May. 2007.