在數位通訊系統下廣泛地使用迴旋碼,由於它們有極好的錯誤修正效能。在高速度腓特比解碼器(VD)的實現上，如何有效縮減路徑計量值記憶體(PMMU)並搭配運算單元間連線複雜度，和如何提高運算單元(ACSU loop)間管線級數，已成為實現高速度VD的關鍵技術。在本論文，首先為了縮減連線的複雜度，我們提出一個全新且有效的定位模式(Extended In-Place)技術，可使得記憶體區塊與運算單元(ACSU)間接線方式為單一且直接之區域化(locally)形式。然後為了增加運算單元間管線級數，我們提出一個可降低資料相依性的系統化重排(Reorder)演算法。在本論文發展的架構有下列特性: (1) 記憶體可以有系統的分割成多個獨立的區塊， (2)記憶體區塊可以合併成固定數量虛擬記憶體區塊。這將不只大幅降低位址產生電路的面積且有效的降低記憶體面積，(3) 根據所提的重排(reorder)演算法及實驗結果,可證明我們管線架構的級數達到近似重排(reorder)技術的最佳情況。

　　Convolutional codes are widely used in communication systems due to their excellent error-control performance. High-speed Viterbi decoders for convolutional codes are of great interest for high data-rate applications. How to reduce the interconnection network efficiently between the path metric memory unit (PMMU) and add_compare_select unit(ACSU), and how to increase the pipelined stage within the loop of ACSU are always the key techniques for successfully designing the high- speed Viterbi decoders. In this thesis, In order to reduce the interconnect overhead further, we first present a novel and efficient in-place scheduling technique, denoted as the extended in-place scheduling, such that every ACSU will only access a dedicated, partitioned memory bank; therefore, the interconnection network is simplified and the bank becomes local to the specific ACSU conceptually. After that, in order to increase the pipelined stages of ACSU, we present a systematic reordering algorithm to relax the data dependences among consecutive trellis stages. The result architecture has the following characteristics: (1) The whole memory can be systematically partition into several sets of banks and each set can be treated as local memory of a specific ACSU. (2) The partitioned memory banks can be merged into a fixed number of pseudo-banks regardless of the number of ACS operations. (3) Based on the presented reordering technique, more pipelined stages be come available, Experimental results also show that the performance of the proposed reordering scheme is close to that of the optimal solution and to achieve the best situation that approximate to reorder technique.

[1] A. J. Viterbi, “Convolutional Codes and Their Performance in Communication Systems,” IEEE Trans. Commun., vol. COM-19, pp.751-772, Oct. 1971.
[2] S. Lin and D. J. Costello, Jr., Error Control Coding-Fundamentals and Applications, Prentice-Hill, 1983.
[3] S. B. Wicker, Error Control Systems for Digital Communication and Storage. Prentice-Hill, 1995.
[4] H. L. Lou, “Implementing the Viterbi Algorithm,” IEEE Signal Processing Magazine, vol. 12, pp. 42-52, Sept. 1995.
[5] G. Fettweis and H. Meyr, “Parallel Viterbi Algorithm Implementation: Breaking the ACS-Bottleneck,” IEEE Trans. Commun., vol. 37, pp. 785-790, Aug. 1989.
[6] C. Y Chang and K. Yao, “Systolic Array Processing of the Viterbi Algorithm,” IEEE Trans. Inform. Theory, vol. 35, pp. 76-86, Jan. 1989.
[7] 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,” in Proc. ISSCC, pp. 162-163, 1987.
[8] P. G. Gulak and E. Shwedyk, “VLSI Structures for Viterbi Receivers: Part I–General Theory and Application,” IEEE J. Select. Areas Commun., vol. SAC-4, pp. 142-154, Jan. 1986.
[9] P. G. Gulak and T. Kailath, “Locally Connected VLSI Architectures for the Viterbi Algorithm,” IEEE J. Select. Areas Commun. vol. 6, pp. 527-537, Apr. 1988.
[10] G. Feygin, P. G. Gulak, and P. Chow, “A Multiprocessor Architecture for Viterbi Decoders with Linear Speedup,” IEEE Trans. Signal Processing, vol. 41, pp. 2907-2917, Sep. 1993.
[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 Trans. Commun., vol. 41, 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 Trans. Commun., vol. 41, pp. 802-807, May 1993.
[13] 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.
[14] C. M. Rader, “Memory Management in a Viterbi Decoder,” IEEE Trans. Commun. vol. 29, pp. 1399-1401, Sept. 1981.
[15] M. Biver, H. Kaeslin, and C. Tommasini, “In-place Updating of Path Metrics in Viterbi Decoders,” IEEE J. Solid-State Circuits, vol. 24, pp. 1158-1159, Aug. 1989.
[16] J. Black and H. Meng, “A 140-Mb/s, 32-State, Radix-4 Viterbi Decoder,” IEEE J. Solid-State Circuits, vol. 27, pp. 1877-1885, Dec. 1992.
[17] W. T. Lee, T. H. Chen, and L. G. Lee, “A VLSI Architecture for Radix-2k Viterbi Decoding with Transpose Algorithm”VLSI TSAS, pp.219-223, 1995.
[18] 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,” in Proc. ISCAS, pp. IV449-452, 1998.
[19] C. M. Wu, M. D. Shieh, C. H. Wu, and M. H. Sheu, “An Efficient Approach for In-Place Scheduling of Path Metric Update in Viterbi Decoders” in Proc. ISCAS, vol. 3, pp. 61-64, 2000.
[20] C. M. Wu, M. D. Shieh, C. H. Wu, and M. H. Sheu, “VLSI Architecture of Extended In-Place Path Metric Update Metric Update for Viterbi Decoderd” in Proc, ISCAS. vol. 4, pp. 206-209,2001.
[21] M. Benaissa and Y. Zhu “A Novel ACS Scheme for Area-Efficient Viterbi Deocders”Proc. ISCAS, vol. 2, pp.264-267, 2003