在數位通訊系統領域中，腓特比演算法(VA)為一公認的有效率之近似解碼演算法，並已廣泛地應用在迴旋碼的解碼上。在腓特比解碼器(VD)的實現上，如何有效管理路徑計量值記憶體(PMMU)並搭配運算單元(ACSU)，以提高PMMU與ACSU間之等效記憶體頻寬同時簡化之間的連間線複雜度，已成為實現VD的關鍵技術之一在數位通訊系統領域中，腓特比演算法(VA)為一公認的有效率之近似解碼演算法，並已廣泛地應用在迴旋碼的解碼上。在腓特比解碼器(VD)的實現上，如何有效管理路徑計量值記憶體(PMMU)並搭配運算單元(ACSU)，以提高PMMU與ACSU間之等效記憶體頻寬同時簡化之間的連間線複雜度，已成為實現VD的關鍵技術之一
　　針對此問題，本論文首先針對蝴蝶模組與定位模式(in-place mode)間的特性，提出系統化公式將路徑計量值記憶體分割成許多區塊。此外，為了有效降低PMMU與ACSU間連接線路面積，我們使用定位模式(extended in-place mode)之演算法，此演算法可使得記憶體區塊與蝴蝶模組間的接線方式為單一且直接之區域化(locally)形式。本論文所發展之記憶體的管理架構具有下列的特性: (1)記憶體可以有系統的分割成多個獨立的區塊， (2)P個記憶體區塊可以合併成２個虛擬記憶體區塊。這將不只大幅降低位址產生電路的面積且有效的降低記憶體面積(3)硬體實現簡易且控制電路具規則性。(4)可應用於不同系統需求之實現。

　　Of the key techniques to successfully designing the Viterbi decoders, how to efficiently manage the path metric memory and at the same time to minimize the interconnection networks between the memory and add_compare_select unit (ACSU) is always a key concern of hardware implementation. In this thesis, we first derive a systematic method for conflict-free address arrangement of in-place path metric update according to the butterfly-based computation. In this manner, we can increase the equivalent memory bandwidth at the expense of more complicated interconnects. To further reduce the interconnect overhead, we 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 conceptually local to the specific ACS. The resulting architecture has the following　characteristics: (1) The whole memory can be systematically partitioned into several sets of banks and each set can be treated as a local memory of a specific ACS. (2) The P partition memory banks can be merged into only two pseudo-banks regardless of the number of ACS operations. This not only further reduces the hardware requirements of address generation, but also makes the small area of memory space. (3) The implementation can be derived in a simple way with regular controlling circuitry. (4) The result can be easily applied to different applications of Viterbi decoder and the effectiveness of the developed techniques is very apparent for convolutional codes with a long memory order.

[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] M. Boo, F. Arguello, J. D. Bruguera, R. Doallo, and E. L. Zapata, “High-Performance VLSI Architecture for the Viterbi Algorithm,” IEEE Trans.Commun., vol. 45, pp. 168-176, Feb. 1997.

[14] D. Akopian, J. Takala, J. Saarinen, and J. Astola, “Multistage Interconnection Networks for Parallel Viterbi Decoders,” IEEE Trans. Commun., vol. 51, pp. 1536-1545, Step. 2003.

[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,” in Proc. ISCAS, pp. IV449-452, 1998.

[17] C. M. Rader, “Memory Management in a Viterbi Decoder,” IEEE Trans. Commun. vol. 29, pp. 1399-1401, Sept. 1981.

[18] 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.

[19] L. G. Johnson, “Conflict Free Memory Addressing for Dedicated FFT Hardware,” IEEE Trans. Circuit and System, vol. 39, pp. 312-316, May, 1992.

[20] H.-F. Lo, M. D. Shieh, and C. M. Wu, “Design of an Efficient FFT Processor for DAB System,” in Proc. ISCAS, pp. 654-657, 2001.

[21] Peter J. Black and Teresa H. Meng, “A 140-Mb/s, 32-State, Radix-4 Viterbi Decoder,” IEEE J. Solid-State Circuits, vol. 27, pp. 1877-1885, Dec. 1992.