迴旋碼及腓特比解碼器已被廣泛使用於各式數位通訊系統標準中，以得到較低的位元錯誤率進而提升系統的傳輸品質。然而在無線技術快速發展之下，針對不同應用之各式通訊協定即因應而生，因此在各個標準中對腓特比解碼器的規格需求也不盡相同，例如在短距離無線裝置之應用如超寬頻 (MB-OFDM) 上，通常需要極高的資料輸出率；對於手持裝置而言，低功率消耗則是電路設計的基本前提，為了能夠設計出符合各種標準且有效率的腓特比解碼器，並且縮短電路設計的時間，一有效率的腓特比解碼器之矽智產產生器將扮演著非常重要的角色。
主論文主要是探討腓特比解碼器在硬體實現上常遇到的兩個重要問題：如何降低存活路徑儲存單元的高功率消耗，以及當系統頻率高於電路之輸出率時，為節省面積而使用面積效率架構所造成的高連接線複雜度。除了針對這兩個主要的問題提出改良之架構外，並基於此架構建立一可參數化的電路並延伸為矽智產產生器。

Convolutional codes and Viterbi decoders (VDs) are widely applied to modern digital communication systems for reducing the overall bit error rate and improving the resulting performance. Rapid development in wireless techniques also results in the emergence of a variety of communication standards, each aiming at different applications. This in turn implies that different VD specifications might be needed in different communication standards. For example, a short-distance wireless communication such as the MB-OFDM UWB requires an ultimate high throughput rate, while portable devices demand low power consumption. As a result, an efficient VD IP generator would be required to shorten the design time and to take into account the effects of different VD specifications.
The primary challenges of VD designs are the large power consumption of storage elements such as those for the survivor memory management, and the high interconnect complexity in area-efficient architectures adopted when the system clock rate is faster than the required throughput rate. This thesis presents improved architectures to solve the two problems and then develop a parameterized IP generator based on proposed VD architectures.

Table Of Content iii
List Of Figures v
List Of Tables vii
Chapter 1 Introduction 1
1.1 Channel Coding 1
1.2 Motivation 2
1.3 Thesis Overview 3
Chapter 2 Viterbi Hardware Architecture 4
2.1 Viterbi Algorithm and Implementation 4
2.2 Branch Metric Unit (BMU) 9
2.3 Add Compare Select Unit (ACSU) 10
2.4 Survivor Memory Unit (SMU) 12
Chapter 3 Enhanced Architectures 15
3.1 Segmented Register Exchange Method 15
3.1.1 Segmented RE with TFU (m-level SRE) 17
3.1.2 Segmented conventional RE (bit-level SRE) 21
3.1.3 SRE with Scarce State Transition (SST) 23
3.2 Fixed Interconnections Area-Efficient ACSU 25
3.2.1 Conflict Free Memory Access 26
3.2.2 Extended In-place Scheduling 31
3.2.3 Local Memory with Pseudo Bank Architecture 34
3.3 Experimental Results 38
3.3.1 Experimental Results of SRE 38
3.3.2 Experimental Results of Fixed Interconnections ACSU 41
Chapter 4 Viterbi Decoder IP Generator 44
4.1 Specifications and Parameters 44
4.2 IP Generator Design 47
4.3 Verification Flow and Application Methods 49
Chapter 5 Conclusions and Future Work 52
5.1 Conclusions 52
5.2 Future Work 53

[1]S. Lin, D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Prentice-Hill, 1983
[2]A. J. Viterbi, “Convolutional codes and their performance in communication systems,” IEEE Trans. Commun., vol. COM-19, pp.751-772, Oct. 1971.
[3]T. Chi-Ying Tsui, R.S.-K. Cheng, C. Ling, “Low power ACS unit design for the Viterbi decoder [CDMA wireless systems],” IEEE Int. Symp. ISCAS'99, vol. 1, pp. 137-140, May 1999.
[4]S. B. Wicker, Error Control Systems for Digital Communication and Storage. Prentice-Hill, 1995.
[5]G. Feygin and P. G. Gulak, “Architectural tradoffs for survivor sequence memory management in Viterbi decoders," IEEE Trans. Commun., vol. 41, no. 3, pp.425-429, Mar. 1993.
[6]Y. Gang, A. T. Erdogan, and T. Arslan, “An efficient pre-traceback architecture for the Viterbi decoder targeting wireless communication applications,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 53, no. 9, pp. 1918-1927, Sep. 2006.
[7]P. J. Black and T. H.-Y. Meng, “Hybrid survivor path architectures for Viterbi decoders,” Proc. IEEE Int. Conf. Acoust., Speech, Signal Process, pp. 433-436, 1993.
[8]F. Sun and T. Zhang, “Low-power state-parallel relaxed adaptive Viterbi decoder,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 54, no. 5, pp. 1060-1068, May 2007.
[9]J. Jin and C. Y. Tsui, “Low-power limited-search parallel state Viterbi decoder implementation based on scarce state transition,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 15, no. 10, pp. 1172-1176, Oct. 2007.
[10]M. Kamuf, V. Öwall, and J. B. Aderson, "Survivor path processing in Viterbi decoders using register exchange and traceforward," IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 54, no. 6, Jun. 2007.
[11]S. Kubota, and S. Kato, “Novel Viterbi decoder VLSI implementation and its performance,” IEEE Trans. Commun., vol. 41, no. 8, pp. 1170-1178, Aug. 1993.
[12]G. Fettweis and H. Meyr, “Parallel Viterbi algorithm implementation: breaking the ACS-bottleneck,” IEEE Trans. Commun., vol. 37, pp. 785-790, Aug. 1989.
[13]C. Y. Chang and K. Yao, “Systolic array processing of the Viterbi algorithm,” IEEE Trans. Inform. Theory, vol. 35, pp. 76-86, Jan. 1989.
[14]S. C. Glinski, T. M. Lalumia, D. R. Cassiday, T. Koh, C. M. Gerveshi, A. Wilson, and J. Kumar, “A processor for graph search algorithms,” IEEE Int. Solid-State Circuits Conf., pp. 162-163, 1987.
[15]S. Y. Kim, H. Kim, and I. C. Park, “Path metric memory management for minimising interconnections in Viterbi decoders,” Electronics Letters, vol. 37, pp. 925-926, July 2001.
[16]M. D. Shieh, M. H. Sheu, C. M. Wu, and W. S. Ju, “Efficient management of in-place path metric update and its implementation for Viterbi decoders,” Proc. ISCAS, pp. IV449-452, 1998.
[17]F. Daneshgaran and K. Yao, “The iterative collapse algorithm: a novel approach for the design of long constraint length Viterbi decoders—Part I,” IEEE Trans. Commun., vol. 43, no. 2/3/4, pp. 1409-1418, Feb./Mar./Apr. 1995.
[18]T. Järvinen, P. Salmela, T. Sipilä, and J. Takala, “Systematic approach for path metric access in Viterbi decoders,” IEEE Trans. Commun., vol. 53, no. 5, pp. 755-759, May 2005.