臺灣博碩士論文加值系統

本論文依據混合式向後追溯法，提出一個新的軟輸出維特比演算法(SOVA)的超大型積體電路架構。一般對於維特比解碼器的設計，通常存活路徑的管理都扮演著相當重要的角色，因為它影響整個架構的速度和功率的消耗。為了要達到高速的解碼效能，在過去大多數的SOVA架構都採用暫存器交換法；然而，卻帶來複雜的繞線以及較多的資料交換動作。在本文中，經由結合暫存器交換法以及向後追溯法的混合式方式應用在SOVA架構的設計上。新的架構不但擁有相當好的規律性，而且因為較少的資料交換動作所以功率方面的消耗也可較低。除此之外，相較於一般的SOVA架構，為了要做第二步驟向後追溯動作，必須記憶許多存活路徑選擇結果，所提出的方法在這方面也可節省相當多的暫存器。

This thesis presents a novel VLSI architecture for soft output Viterbi algorithm (SOVA) based on hybrid track-back of transverse paths. For the design of Viterbi decoders, the management of survivor memory usually plays a crucial role affecting the speed and power of the entire architecture. In order to achieve very high speed of decoding, majority of SOVA designs in the past use simple register-exchange method that nevertheless suffers from both complex routing and high switching activities. In this thesis, a hybrid approach that combines both the trace-back and register exchange schemes has been applied to the design of SOVA. The resulted architecture not only exhibits better regularity due to less routing, but it can also lead to lower power consumption because of reduced switching activities. In addition, the proposed approach can also save lots of registers that are often required in common SOVA architectures for holding the current decision results in order to find out the competing paths later.

中文摘要……………………………………………………………i
英文摘要……………………………………………………………ii
目錄…………………………………………………………………iii
圖目錄………………………………………………………………v
表目錄………………………………………………………………vii
第一章 緒論………………………………………………… 1
第二章 維特比演算法……………………………………… 2
2.1 迴旋編碼……………………………………………… 3
2.2 維特比解碼器…………………………………… 4
2.3 存活路徑單元………………………………………7
第三章 軟輸出維特比演算法…………………………… 11
3.1 軟輸出維特比演算法………………………… 11
3.2 軟輸出維特比演算法可信度的評量值………… 13
3.3 SOVA中的SMU(State Metric Unit)架構……… 17
3.3.1 暫存器交換法SOVA-SMU架構……… 17
3.3.2 兩個步驟SOVA-SMU架構………… 18
第四章 混合式向後追溯軟輸出維特比解碼器架構…………… 24
4.1 混合式向後追溯法…………………………… 24
4.2 新的可信度評量單元…………………………… 33
4.3 新的路徑比較單元……………………………… 35
第五章 設計與分析……………………………………………… 38
5.1 設計……………………………………………… 38
5.2 分析……………………………………………… 42
第六章 結論……………………………………………………… 46
參考文獻……………………………………………………… 47

[1] A. J. Viterbi, "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm," IEEE Trans. on Information Theory, IT-13, April 1967.
[2] G. D. Forney Jr., "The Viterbi Algorithm," Proc. IEEE, pp.268-278, 1973.
[3] S. Lin, D. J. Costello Jr., Error Control Coding :Fundamentals and Applications. Prentice-Hall, Inc., Engelwood Cliffs, N. J., pp.288-348, 1983.
[4] H.-L. Hou, "Implementing the Viterbi algorithm," IEEE Signal Processing Mag., vol. 12, pp. 42-52, Sept. 1995.
[5] Stephen B. Wicker, “Error Control Systems for Digital Communication and Storage,” Prentice-Hall, 1995.
[6] J. Hagenauer, P. Hoeher, “A Viterbi algorithm with soft-decision outputs and its applications,” GLOBECOM '89., IEEE , vol.3, pp.1680 —1686, 1989.
[7] X.A. Wang; S.B Wicker,”A soft output decoding algorithm for concatenated systems,” Information Theory, Proceedings.,IEEE International Symposium on ,pp. 475, 1995
[8] J. Hagenauer ,P. Hoeher, ”Concatenated Viterbi-Decoding,” Proceedings of the 4. Joint Swedish-Soviet Int. Workshop on Information Theory, Gotaland, Sweden, Studentliteratur Lund,27.Sept. 1989
[9] O.Joeressen, M.Vaupel, H. Meyr, “High-speed VLSI architectures for soft-output Viterbi decoding,” Application Specific Array Processors, 1992. Proceedings of the International Conference on , pp,373 —384, 1992.Journal of VLSI signal Processing,1994.
[10] O.J. Joeressen, M. Vaupel, H. Meyr, “Soft-output Viterbi decoding: VLSI implementation issues,” Vehicular Technology Conference, 1993., 43rd IEEE ,pp.941 —944,1993.
[11] C. Berrou, P. Adde, E. Angui, S. Faudeil, ”A low complexity soft-output Viterbi decoder architecture,” Communications, 1993. ICC '93 Geneva. Technical Program, Conference Record, IEEE International Conference on , vol: 2 ,pp.737-740,1993
[12] O.J. Joeressen, H. Meyr, “ 40 Mbit/s soft output Viterbi decoding ASIC,“ Global Telecommunications Conference, 1994. GLOBECOM '94. Communications: The Global Bridge., IEEE , Vol.3 ,pp 1482 —1486,1994
[13] O.J. Joeressen , H. Meyr, “A 40 Mb/s soft-output Viterbi decoder,” Solid-State Circuits, IEEE Journal of , Vol.30 Issue 7 , pp 812 —818,1995
[14] C. Berrou,; A. Glavieux,; P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1,” Communications, 1993. ICC '93 Geneva. Technical Program, Conference Record, IEEE International Conference on , vol.2,pp 1064-1070, 1993
[15] C. Berrou, P. Combelles, P. Penard, B. Talibart ,”An IC for turbo-codes encoding and decoding ,“ Solid-State Circuits Conference,Digest of Technical Papers. 41st ISSCC, IEEE International ,pp 90 —91,1995
[16] J. Hagenauer , L. Papke, “Decoding Turbo-codes with th Soft Output viterbi Algorithm,” Information Theory, 1994. Proceedings., 1994 IEEE International Symposium on , pp. 164,1994
[17] A.-W. Kuei, Y.-L. Jau, "Parallel processing for Viterbi algorithm," IEEE Electronics Letters, vol. 24-17, pp.1098-1099, 18 Aug. 1988.
[18] G. Fettweis, H. Meyr, "Parallel Viterbi algorithm implementation: breaking the ACS-bottleneck," IEEE Trans. on Communications, vol. 37-8 , pp.785-790, Aug. 1989.
[19] G. Fettweis, H. Meyr, "High-speed parallel Viterbi decoding: algorithm and VLSI-architecture," IEEE Communications Magazine, vol. 29-5, pp.46 -55, May 1991.
[20] H. Suzuki, Y.-N. Chang, K.K. Parhi, "Low-power bit-serial Viterbi decoder for 3rd generation W-CDMA system," in IEEE Custom Integrated Circuits Conf., San Diego, CA, pp.589-592, May 1999.
[21] Y.-N. Chang, H. Suzuki, K.K. Parhi, "A 2-Mb/s 256-state 10-mW rate-1/3 Viterbi decoder," IEEE J. Solid-State Circuits, vol. 35, pp.846-834, June 2000.
[22] H.-D. Lin and B. Shung, "General in-place scheduling for the Viterbi Algorithm," in Proc. of ICASSP, vol. 25, no. 4, pp.1577-1579, 1991.
[23] 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. of ISCAS'98, vol. 4, pp. 449-452, 1998.
[24] G. Feygin, and P. G. Gulsk, “Survivor Sequence Memory Management in Viterbi Decoder,” Circuits and Systems, 1991., IEEE International Sympoisum on, pp 2697-2970 vol.5
[25] T. K. Truong, M. T. Shin, I. S. Reed and E. H. Satorius, “ A VLSI Design for Trace-Back Viterbi Decoder” IEEE Trans. Comm., vol.40, No. 3, Mar. 1992.
[26] F Hemmati, D.J. Costello. Truncation Error Probability in Viterbi Decoding. IEEE Transactions Communications,pp530-532,1997
[27] I.M. Onyszchuk. Truncation Length for Viterbi Decoding. IEEE Transactions Communications,pp1023-1026,1991
[28] E. Yeo, P. Pakzad, B. Nikolic, V. Anantharam, “VLSI architectures for iterative decoders in magnetic recording channels,“ Magnetics, IEEE Transactions on , vol. 37, Issue: 2 Part: 1 , pp 748 —755,March 2001
[29] D. Garrett and M. Stan, “A 2.5 Mb/s ,23mW SOVA Traceback Chip for Turbo Decoding Application, “ Circuits and Systems, 2001. ISCAS 2001. The 2001 IEEE International Symposium on , vol. 4, pp. 61-64, 2001
[30] P. J. Black, T. H.-Y. Meng, "Hybrid survivor path architectures for Viterbi decoders," IEEE Int. Conf. on ICASSP, vol. 1, pp.433-436, 1993.
[31] E. Boutillon, N. Demassieux, "High speed low power architecture for memory management in a Viterbi decoder," IEEE Int. Symp. on Circuits and Systems, vol. 4, pp.284-287, 1996.
[32] C. B. Shung, P. H. Siegel, G. Ungerboeck, H. K. Thapar, "VLSI architectures for metric normalization in the Viterbi algorithm," in Int. Conf. Communications, vol.4, Atlanta, GA, pp.1723-1728, Apr. 1990.
[33] C-W Wang , Y-N Chang ”Design of Viterbi decoders with in-place state metric update and hybrid trace back processing, “Signal Processing Systems, IEEE Workshop on , pp. 50-15, 2001