臺灣博碩士論文加值系統

維特比解碼器(Viterbi decoder)是使用在無線通訊設備中一個著名的錯誤更正通道解碼器，然而維特比解碼器通常也佔用移動設備很大比例的功率消耗。為了避免過多的碼字(codeword)需要進行解碼並且降低功率消耗，本論文提出了兩個適用於降低維特比解碼器功率消耗的技術和相對應的VLSI架構。首先，相對於分段式錯誤偵測的方式，我們提出碼字式的state transparent convolutional (STC) code解碼器用於偵測每個碼字是否有錯誤，此細緻的錯誤偵測方式將會降低需要被送至維特比解碼器的碼字數量。根據碼字式的錯誤偵測方式，我們開發了一個簡單的方法定位並且修正獨立且不連續錯誤的單一碼字，實驗結果顯示此方法可以進一步減少維特比解碼器的啟動時間。此外，我們提出了具有存活狀態偵測技術的維特比解碼器，此方法可以偵測出非屬於存活路徑的狀態，並且刪除其在維特比解碼器存活記憶體單元中不必要的操作，因此可以降低存活記憶體單元中決策位元的交換數量並且達成低功耗的效果。實驗結果證明我們提出來的這兩個技術可以更進一步地降低維特比解碼器的功率消耗。

Viterbi decoders are one of the most popular error-correcting channel decoders in wireless communication devices. However, a Viterbi decoder is also usually the dominant module in the mobile devices regarding power consumption. To avoid the superfluous codeword decoding and reduce the power consumption, this dissertation proposes two low-power techniques and their corresponding VLSI architectures for the Viterbi decoder. Firstly, instead of the segment-based error detection, we propose the codeword-based STC decoder to detect whether each received codeword is erroneous. The fine-grained error detection conduces to fewer codewords that have to be corrected through the Viterbi decoder. Based on the codeword-based error detection, we develop a simple method to locate and correct the isolated faulty codewords that do not appear successively. As can be seen in the experimental results, the activation times of the Viterbi decoder can be further decreased. Secondly, we propose a survivor state (SS) detection technique to detect the non-survivor states and eliminate the unnecessary operations in the survivor memory unit (SMU) of a Viterbi decoder. The SS detection technique results in fewer decision bits that have to be exchanged in the SMU and achieves the low-power goal. Experimental results demonstrate that the power consumption of the Viterbi decoder can be further reduced based on the proposed two low-power techniques.

論文審定書 i
論文公開授權書 ii
誌謝 iii
摘要 iv
Abstract v
Table of Contents vii
List of Figures x
List of Tables xiv
Chapter 1 Introduction 1
1.1 Background 4
1.2 Motivation 5
1.3 Organization of dissertation 7
Chapter 2 Related works 8
2.1 Convolutional code 8
2.1.1 Definition of convolutional codes 9
2.1.2 Structure and property of convolutional codes 10
2.1.3 Free distance of convolutional codes 15
2.1.4 Termination methods of convolutional codes 19
2.1.5 Punctured convolutional codes 26
2.1.6 Hard decision and soft decision 29
2.2 Viterbi algorithms and architectures 31
2.2.1 Branch Metric Unit 36
2.2.2 Add-Compare-Select Unit 37
2.2.3 Path Metric Memory Unit 40
2.2.4 Survivor Memory Unit 43
2.3 M-algorithm and T-algorithm 52
2.4 Scarce State Transition 53
2.5 Modified RE method and memoryless Viterbi decoder 55
2.6 State transparent convolutional code 55
2.7 Segment-based STC Viterbi decoder 56
Chapter 3 Proposed Low-power techniques for the Viterbi decoder 57
3.1 Proposed codeword-based STC Decoder 60
3.1.1 Basic concept of State Transparent Convolutional code 60
3.1.2 Basic concept of segment-based STC Viterbi decoder 63
3.1.3 Proposed codeword-based error detection 65
3.1.4 Proposed codeword-based error correction 70
3.1.5 Flowchart of codeword-based decoding 73
3.1.6 Proposed architecture of codeword-based STC decoder 76
3.2 Proposed survivor-state Viterbi decoder 80
3.2.1 Definition of survivor state 82
3.2.2 Proposed survivor state detection technique 84
3.2.3 Flowchart of survivor-state Viterbi decoder 95
3.2.4 Proposed architecture of survivor-state Viterbi decoder 99
Chapter 4 Experimental Results 102
4.1 Simulation environment 102
4.2 Experimental results of proposed codeword-based STC decoder 105
4.3 Experimental results of proposed survivor-state Viterbi decoder 110
4.4 Comparisons of different low-power techniques 116
Chapter 5 Conclusions and Further Work 122
5.1 Conclusions 122
5.2 Future work 124
References 126

[1]P. Elias, "Coding for noisy channels," IRE Convention Record, part 4, pp. 37−46, 1955.
[2]A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inform. Theory, vol. IT-13, no. 2, pp. 260−269, Apr. 1967.
[3]G. D. Forney, Jr., “Review of random tree codes,” NASA Ames Research Centre, Moffett Field, Calif., Appendix A of Final Report on Contract NAS2−3637, NASA CR73176, Dec. 1967.
[4]G. D. Forney, Jr., “Convolutional codes III. Sequential decoding,” Inform. and Control, vol. 25, no. 3, pp. 267–297, Jul. 1974.
[5]L. R. Bahl, C. D. Cullum, W. D. Frazer, and F. Jelinek, “An efficient algorithm for computing the free distance” IEEE Trans. Inform. Theory, vol. IT-18, no. 3, pp. 437−439, Nov. 1972.
[6]K. J. Larsen, “Comments on ‘An efficient algorithm for computing the free distance’ by Bahl et al” IEEE Trans. Inform. Theory, vol. IT-19, no. 4, pp. 577−579, Jul. 1973.
[7]J. P. Odenwalder, “Optimal decoding of convolutional codes,” Ph.D. dissertation, Dep. Syst. Sci., Sch. Eng. Appl. Sci., Univ. California, Los Angeles, 1970.
[8]K. J. Larsen, “Short convolutional codes with maximal free distance for rates 1/2, 1/3, and 1/4,” IEEE Trans. Inform. Theory, vol. IT-19, no. 3, pp. 371–372, May 1973.
[9]3GPP TS45.003, “3rd Generation Partnership Project; Technical Specification Group GSM/EDGE Radio Access Network; Channel Coding (Release 7)”, Feb. 2007.
[10]3GPP TS 36.212 V10.3.0, “3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (E-UTRA); Multiplexing and channel coding (Release 10),” Sep. 2011.
[11]IEEE Std P802.16e/D10, “IEEE Standard for Local and Metropolitan Area Networks – Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems”, Aug. 2005.
[12]L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inform. Theory, vol. 20, no. 2, pp. 284−287, Mar. 1974.
[13]R. Cox and C. W. Sundberg, “An efficient adaptive circular Viterbi algorithm for decoding generalized tailbiting convolutional codes,” IEEE Trans. Veh. Technol., vol. 43, no. 1, pp. 57−68, Feb. 1994.
[14]P. Stahl, J. Anderson, and R. Johannesson, “Optimal and near-optimal encoders for short and moderate-length tailbiting trellises,” IEEE Trans. Inform. Theory, vol. 45, no. 7, pp. 2562–2571, Nov. 1999.
[15]J. B. Anderson and S. M. Hladik, “An optimal circular Viterbi decoder for the bounded distance criterion,” IEEE Trans. Commun., vol. 50, no. 11, pp. 1736–1742, Nov. 2002.
[16]M. Zhang, J. W. Huang, J. Meng, and Q. Deng, “Research on an-based decode of tail-Biting convolutional codes and their performance analyses used in LTE system,” International Forum on Information Technology and Applications, vol. 2, pp. 303–306, May 2009.
[17]R. Y. Shao, S. Lin, and M. P. C. Fossorier, “Two decoding algorithms for tailbiting codes,” IEEE Trans. Commun., vol. 51, no. 10, pp. 1658–1665, Oct. 2003.
[18]J. B. Cain, G. C. Clark, and J. M. Geist, “Punctured Convolutional Codes of Rate (n−1)/n and Simplified Maximum Likelihood Decoding”, IEEE Trans. Inform. Theory, vol. IT-25, no.1, pp. 97–100, Jan. 1979.
[19]I. Habib, O. Paker, and S. Sawitzki, “Design space exploration of hard-decision Viterbi decoding: Algorithm and VLSI implementation,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 18, no. 5, pp. 794–807, May 2010.
[20]S. Bhowal, “Transformation of ACS module to CSA module of low-power Viterbi decoder for digital wireless communication applications,” IEEE Int. Conf. on Advances in Computing, Communications and Informatics (ICACCI), pp. 266–270, 2013.
[21]B. Gao, Z. Xiao, Z. Chen, D. Jin, and L. Zeng, “Multigigabit balanced add-select-register-compare Viterbi decoders architecture in 60 GHz WPAN,” IEEE Asia-Pacific Conference on Communications (APCC), pp. 531–535, 2013.
[22]S. Huang, Y. Yang, and Z. Sun, “Add-select-delay-compare Viterbi decoder for UWB communications in electronic power systems,” IEEE Int. Conf. on Communication Problem-solving, pp. 1–4, 2014.
[23]G. Ungerboeck, “Adaptive maximum-likelihood receiver for carrier modulated data transmission systems,” IEEE Trans. Commun., vol. 22, no. 5, pp. 624−635, May. 1974.
[24]G. D. Forney, Jr., “The Viterbi algorithm,” Proc. IEEE, vol. 61, no. 3, pp. 268−278, Mar. 1973.
[25]C. B. Shung, P. H. Siegel, G. Ungerboeck, and H. K. Thapar, “VLSI architectures for metric normalization in the Viterbi algorithm,” IEEE Int. Conf. Commun., vol. 4, pp. 1723–1728, Apr. 1990.
[26]G. D. Forney, Jr., “Convolutional codes II: Maximum likelihood decoding,” Inform. Control, vol. 25, no. 3, pp. 222–226, 1974.
[27]G. C. Clark, and J. B. Cain, “Error-Correction Coding for Digital Communications,” Applications of Communication Theory, New York: Plenum Press, 1981.
[28]B. Moision, “A truncation depth rule of thumb for convolutional codes,” Inform. Theory Appl., pp. 555–557, Jan. 2008.
[29]H. A. Bustamante, I. Kang, C. Nguyen, and R. E. Peile, “Stanford telecom VLSI design of a convolutional decoder,” Military Commun. Conf., vol. 1, pp. 171−178, Oct. 1989.
[30]R. Cypher and C. B. Shung, “Generalized trace-back techniques for survivor memory management in the Viterbi algorithm,” J. VLSI Signal Process., vol. 5, no. 1, pp. 85–94, Jan. 1993.
[31]O. Collins and F. Pollara, “Memory Management in Traceback Viterbi Decoders,” TDA Prog. Rep., pp. 42−99, Jet Prop. Lab., Pasadena, CA, Nov. 1989.
[32]G. Feygin, G. Gulak, and F. Pollar, “Survivor sequence memory management in Viterbi decoder,” IEEE Int. Sym. Circuits Syst., vol. 5, pp. 2967–2970, Jun. 1991.
[33]P. J. Black and T. H.-Y. Meng, “Hybrid survivor path architectures for Viterbi decoders,” IEEE Int. Conf. Acoust. Speech, Signal Process., vol. 1, pp. 433–436, Apr. 1993.
[34]M. Kamuf, V. Owall, and J. B. Anderson, “Survivor path processing in Viterbi decoders using register exchange and traceforward,” IEEE Trans. Circuits and Syst. II, vol. 54, no. 6, pp. 537–541, 2007.
[35]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, vol. 53, no. 9, pp. 1918–1927, Sep. 2006.
[36]M. D. Shieh, T. P. Wang, and D. W. Yang, “Low-power register-exchange survivor memory architectures for Viterbi decoders,” IET Circuits, Devices, & Systems, vol. 3, pp. 83–90, Apr. 2009.
[37]C. F. Lin and J. B. Anderson, “M-algorithm decoding of channel convolutional codes,” in Proc. Princeton Conf. Inform. Sci. Syst., Princeton, NJ, pp. 362–366, Mar. 1986.
[38]R. Yoshizawa and H. Ochiai, “Peak power reduction of OFDM signals using trellis shaping with M-algorithm,” Proceedings of 1st Workshop on Flexibility in Broadband Wireless Access Network (FlexBWAN), The 20th IEEE International Conference on Computer Communications Networks (ICCCN 2011)., Hawaii, Maui, Aug. 2011.
[39]H. Kato, T. H. Tran, and Y. Nakashima, “ASIC design of a low-complexity K-best Viterbi decoder for IoT applications,” IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), pp. 396–399, Oct. 2016.
[40]S. J. Simmons, “Breadth-first trellis decoding with adaptive effort,” IEEE Trans. Commun., vol. 38, no. 1, pp. 3–12, Jan. 1990.
[41]F. Chan and D. Haccoun, “Adaptive Viterbi decoding of convolutional codes over memoryless channels,” IEEE Trans. Commun., vol. 45, no. 11, pp. 1389–1400, Nov. 1997.
[42]M. Guo, M. O. Ahmad, M. N. S. Swamy, and C. Wang, “FPGA design and implementation of a low-power systolic array-based adaptive Viterbi decoder,” IEEE Trans. Circuits Syst. I, vol. 52, no. 2, pp. 350–365, Feb. 2005.
[43]R. Tessier, S. Swaminathan, R. Ramaswamy, D. Goeckel, and W. Burleson, “A reconfigurable, power-efficient adaptive Viterbi decoder,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 13, no. 4, pp. 484–488, Apr. 2005.
[44]F. Sun and T. Zhang, “Low-power State Parallel Relaxed Adaptive Viterbi Decoder,” IEEE Trans. Circuits and Syst. I, vol. 54, no. 5, pp. 1060−1068, May 2007.
[45]J. He, H. Liu, and Z. Wang, “A fast ACSU architecture for Viterbi decoder using T-algorithm,” 43rd IEEE Asilomar Conf. Signals, Syst. Comput., pp. 231–235, Nov. 2009.
[46]J. He, H. Liu, Z. Wang, X. Huang, and K. Zhang, “High-speed low-power Viterbi decoder design for TCM decoders,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 20, no. 4, pp. 755–759, Apr. 2012.
[47]T. Ishitani, K. Kansho, N. Miyahara, S. Kubota, and S. Kato, “A scarce-state-transition Viterbi-decoder VLSI for bit error correction,” IEEE J. Solid-State Circuits, vol. SC-22, pp. 575–581, Aug. 1987.
[48]S. Kubota, K. Ohtani, and S. Kato, “High-speed and high-coding-gain Viterbi decoder with low power consumption employing SST (scarce state transition) scheme,” Electron. Lett., vol. 22, no. 9, pp. 491–493, Apr. 1986.
[49]S. Kubota, S. Kato, and T. Ishitani, “Novel Viterbi decoder VLSI implementation and its performance,” IEEE Trans. Commun., vol. 41, pp. 1170–1178, Aug. 1993.
[50]J. Jin and C. Tsui, “A low power Viterbi decoder implementation using scarce state transition and path pruning scheme for high throughput wireless applications,” Int. Symp. Low Power Electron. Design (ISLPED), pp. 406–411, Oct. 2006.
[51]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,” IEEE Int. Symp. VLSI Design, Automation and Test (VLSID-DAT ''09), pp. 99–102, Apr. 2007.
[52]D. A. El-Dib and M. I. Elmasry, “Modified register exchange Viterbi decoder for low-power wireless communications,” IEEE Trans. Circuits and Syst. I, vol. 51, no. 2, pp. 371−378, Feb. 2004.
[53]Dalia A. El-Dib and M. I. Elmasry, “Memoryless Viterbi decoder,” IEEE Trans. Circuits and Syst. II, vol. 52, no. 12, pp. 826–830, Dec. 2005.
[54]H. R. Sarrafzadeh, “State transparent convolutional codes and their novel maximum-likelihood decoding algorithm,” IEEE Trans. Commun., vol. 55, no. 10, pp. 1837–1844, Oct. 2007.
[55]Y. H. Shiau, P. Y. Chen, H. Y. Yang, Y. M. Lin, and S. G. Huang, “An efficient VLSI architecture for convolution code decoding,” Int. Symp. Next Generation Electronics, pp. 223–226, 2010.
[56]Y. H. Shiau, H. Y. Yang, P. Y. Chen, S. G. Huang, “Power-efficient decoder implementation based on state transparent convolutional codes,” IET Circuits, Devices & Systems, vol. 6, no. 4, pp. 227–234, Jul. 2012.
[57]Y. C. Tang, D. C. Hu, W. Y. Wei, W. C. Lin, and H. C. Lin, “A memory-efficient architecture for low latency Viterbi decoders,” IEEE Int. Symp. on VLSI Design, Automation and Test (VLSI-DAT ''09), pp. 335–338., 2009.
[58]C. Y. Chu, A. Y. Wu, “Power-efficient state exchange scheme for low-latency SMU design of Viterbi decoder,” Journal of Signal Processing Systems, vol. 68, no. 2, pp. 233–245, Aug. 2012.