顧孟愷臺灣大學：資訊工程學研究所簡用典Jian, Yong-DianYong-DianJian2007-11-262018-07-052007-11-262018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/53770Convolutional codes and Viterbi decoders were extensively used in error control systems. The survivor memory management (SMM) unit of Viterbi decoder is extremely important in determining the throughput, hardware area and coding gain performance of the whole system. Many SMM architectures were proposed in the past, but we lack an unifying metric to compare the coding gain performance of them. In this thesis, we define a metric, average traceback depth (ATBD), to unify the diversity of different SMM architectures. The ATBD metric can be used to equalize different SMM architectures and predict the optimal traceback depth (TBD) of them. The optimality is in terms of coding gain performance and hardware cost. We perform extensive computer simulations with three popular convolutional codes (DVB, DCII and UMTS) and many SMM architectures to verify the validity of the ATBD metric. Simulation results show that the difference between optimal TBD and ATBD is at most 10%. With this unifying metric, we can estimate the hardware cost of different SMM architectures under fixed coding gain performance. Besides, system architects can use it to fast evaluate the tradeoff among hardware cost, throughput and coding gain performance because the calculation of ATBD metric is very simple.1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Convolutional Code & Viterbi Algorithm 5 2.1 Convolutional Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 The Viterbi Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Punctured Convolutional Codes . . . . . . . . . . . . . . . . . . . . . 14 2.4 Communication Channel Models . . . . . . . . . . . . . . . . . . . . . 17 3 Viterbi Decoder Architecture 21 3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Register Exchange Architecture . . . . . . . . . . . . . . . . . . . . . 24 3.3 Modified Register Exchange architecture . . . . . . . . . . . . . . . . 27 3.3.1 Comment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Traceback Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.5 One-Pointer Traceback . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.6 Multiple Pointer Traceback . . . . . . . . . . . . . . . . . . . . . . . . 36 3.7 Traceforward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.8 Sliding Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.9 Best State Traceback Architecture . . . . . . . . . . . . . . . . . . . . 46 3.10 Comparison of Architectures . . . . . . . . . . . . . . . . . . . . . . . 48 4 Performance Analysis and Metric 53 4.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 Coding Gain Analysis of Viterbi Algorithm . . . . . . . . . . . . . . . 57 4.2.1 Simple Traceback Architecture . . . . . . . . . . . . . . . . . . 57 4.2.2 Register Exchange Architecture . . . . . . . . . . . . . . . . . 59 4.2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.3 Equalization of SMM Architectures . . . . . . . . . . . . . . . . . . . 62 4.3.1 DCII & UMTS . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.3.2 Best State Architecture . . . . . . . . . . . . . . . . . . . . . . 63 4.4 Hardware Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.5 Coding Gain Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 72 5 Conclusion & Future Work 73 5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 A Acronyms & Abbreviations 75 B Glossary of Notation 771035048 bytesapplication/pdfen-US維特比測度Viterbi Metricthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53770/1/ntu-93-R91922018-1.pdf