請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40365
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳少傑(Sao-Jie Chen) | |
dc.contributor.author | Ya-Nan Wen | en |
dc.contributor.author | 文亞南 | zh_TW |
dc.date.accessioned | 2021-06-14T16:45:47Z | - |
dc.date.available | 2011-08-16 | |
dc.date.copyright | 2011-08-16 | |
dc.date.issued | 2011 | |
dc.date.submitted | 2011-08-12 | |
dc.identifier.citation | [1] Huffman, D.A., “A Method for Construction of Minimum Redundancy Code,” IRE Proceedings, vol. 40, no. 9, Sept. 1952, pp. 1098-1110.
[2] “Information Technology - Digital Compression and Coding of Continuous-tone Still Images,” Standard ISO/IEC 10918, 1994. [3] ”Information Technology -- Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1,5 Mbit/s,” Standard ISO/IEC 11172. [4] Lin, H.-D. and Messerschmitt, D.G, “Finite State Machine has Unlimited Concurrency,” IEEE Trans. Circuits and Systems, vol. 38, no 5, May 1991, pp. 465-475. [5] Chang, S.-F. and Messerschmitt, D.G, “Designing High-Throughput VLC Decoder Part I - Concurrent VLSI Architectures,” IEEE Trans. Circuits and Systems for Video Technology, vol. 2, no. 2, June 1992, pp. 187-196. [6] “Advanced Video Coding for Generic Audiovisual Services,” Recommendation ITU-T H.264. [7] “Information Technology -- Coding of Audio-visual Objects -- Part 2: Visual,” Standard ISO/IEC 14492 [8] Lei, S.-M. and Sun, M.-T, “An Entropy Coding System for Digital HDTV Applications,” IEEE Trans. Circuits and Systems for Video Technology, vol. 1, no. 1, March 1991, pp. 147-155. [9] Lei, S.-M., Sun, M.-T., Ramachandran, and K., Palaniraj, S., 'VLSI Implementation of an Entropy Coder and Decoder for Advanced TV Applications,' in Proc. 1990 IEEE International Symposium on Circuits and Systems, Red Bank, NJ, May 1990, pp.3030-3033. [10] Lin, H.-D. and Messerschmitt, D.G, “Designing a High-Throughput VLC Decoder. Part II - Parallel Decoding Methods,” IEEE Trans. Circuits and Systems for Video Technology, vol. 2, no. 2, June 1992, pp. 197-206. [11] Hashemian, R., “Memory Efficient and High-speed Search Huffman Coding,” IEEE Trans. Communications, vol. 43, no. 10, Oct. 1995, pp. 2576 – 2581. [12] Choi, S. B. and Lee, M. H., “High Speed Pattern Matching for a Fast Huffman Decoder,” IEEE Trans. Consumer Electronics, vol. 41, no. 1, Jan. 1995, pp. 97-103. [13] Nikara, J.; Vassiliadis, S.; Takala, J.; and Liuha, P., 'Multiple-Symbol Parallel Decoding for Variable Length Codes,' IEEE Trans.Very Large Scale Integration Systems, vol.12, no.7, July 2004, pp. 676- 685. [14] Jiang, J. H., Chang, C. C. and Chen, T. S., “An Efficient Huffman Decoding Method based on Pattern Partition and Look-up Table,” in Proc. Fifth Asia-Pacific Conference on Communications and Fourth Optoelectronics and Communications Conference, Beijing, China, Oct. 1999, vol. 2, pp. 904–907. [15] Wang, S. –W., Wu, J. –L., Chuang, S. –C., Hsiao, C. –C. and Tung, Y. –S., “Memory Efficient Hierarchical Lookup Tables for Mass Arbitrary-Side Growing Huffman Trees Decoding,” IEEE Trans. Circuits and Systems for Video Technology, vol. 18, no. 10, Oct. 2008, pp. 1335-1346. [16] Rudberg, M.K. and Wanhammar, L., “New Approaches to High Speed Huffman Decoding” in Proc. IEEE International Symposium on Circuits and Systems, May 1996, pp. 149-152. [17] Chung, K. L. and Wu, J. G., “Level-compressed Huffman Decoding,” IEEE Trans. Communications, vol. 47, no. 10, Oct. 1999, pp. 1455–1457. [18] Chen, H.-C., Wang, Y. –L. and Lan, Y. –F., “A Memory-efficient and Fast Huffman Decoding Algorithm,” Information Processing Letters, vol. 69, no. 3, Feb. 1999, pp. 119-122. [19] Lin, Y. K. and Chung, K. L., “A Space-efficient Huffman Decoding Algorithm and its Parallelism,” Theoretical Computer Science., vol. 246, no. 1, Sept. 2000, pp. 227–238. [20] Aggarwal, M. and Narayan, A., “Efficient Huffman Decoding,” in Proc. 2000 International Conference on Image Processing, Vancouver, Canada, vol. 1, Sept. 2000, pp. 936-939. [21] Moffat, A. and Turpin, A., “On the Implementation of Minimum Redundancy Prefix Codes,” IEEE Trans. Communications, vol. 45, no. 10, Oct. 1997, pp. 1200–1207. [22] Hashemian, R., “Condensed Table of Huffman Coding, a new Approach to Efficient Decoding,” IEEE Trans. Communications, vol 52, no 1, Jan. 2004, pp. 6-8. [23] Wang, P. C., Yang, Y. R., Lee, C. L. and Chang, H. Y., “A Memory Efficient Huffman Decoding Algorithm,” in Proc. 19th International Conference on Advanced Information Networking and Applications, Taipei, Taiwan, vol. 2, March 2005, pp. 475–479. [24] Hsieh, C.-T. T., 'The Systematic Approach for Concurrent VLC Decoder,' IEEE Trans. Consumer Electronics, vol. 43, no. 3, Aug 1997, pp.918-924. [25] Shannon, C. E. 'A Mathematical Theory of Communication', Bell System Technical Journal, vol. 27, July , 1948, pp. 379-423 [26] Chung, K. L., Markov Chains with Stationary Transition Probabilities, 2nd ed, New York: Springer-Verlag, 1967, part I. [27] Friedberg, S. H., Insel, A. J., Spence, L. E., Linear Algebra, 4nd ed, New Jersey: Prentice Hall, 2002. [28] Meyn, S. and Tweedie, R. L., Markov Chains and Stochastic Stability, 2nd ed, New York : Cambridge University Press, 2009 [29] Wen, Y. -N., Chen, S. -J. and Hu, Y. H., “Optimal Multiple-Bit Huffman Decoding,” in Proc. 2006 IEEE International SOC Conference, Austin, TX, Sept. 2006, pp. 79-82. [30] Wen, Y.-N., Lin, G.-H., Chen, S.-J. and Hu, Y. H, “Optimal Multiple-Bit Huffman Decoding,” IEEE Trans. Circuits and Systems for Video Technology, vol. 20, no. 5, May 2010, pp. 621-631. [31] Kullback, S. and Leibler, R. A., 'On Information and Sufficiency,' Annals of Mathematical Statistics, vol. 22, no. 1, 1951, pp. 79–86. [32] Hopcroft, J. E. and Ullman, J. D., Introduction to Automata Theory, Languages, and Computation, Massachusetts: Addison-Wesley, 1979. [33] Kam, T., Villa, T., Brayton, R. and Sangiovannii-Vincentelli, A., Synthesis of Finite State Machine: Function Optimization, Netherland: Kluwer Acadamic, 1997, Chapter 6, pp 177-189. [34] Chen, Y.-F., Clarke, E., Farzan, A., Tsai, M.-H., Tsay, Y.-K. and Wang, B.-Y., 'Automated Assume-Guarantee Reasoning through Implicit Learning,' 22nd International Conference on Computer Aided Verification (CAV 2010), Lecture Notes in Computer Science, 2010 | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40365 | - |
dc.description.abstract | 在本論文中我們探討了變動位元先行霍夫曼解碼器的問題,我們將這樣的解碼器用狀態機來表示。文中我們發現,對於特定的霍夫曼解碼樹來說,其對應的變動位元先行狀態機並不唯一。我們將這個發現定義為LABSHTD問題。在一個LABSHTD問題的解空間中的任意一個解,都可以對應到霍夫曼解碼器的實作。
為了尋找最好的實作方法,我們必須在解空間中尋找最佳解,這表示我們必須能夠評估每個解的效能。我們利用馬可夫鏈,並發現了一個方法讓變動位元先行的狀態機得以適用馬可夫鏈。進而透過計算馬可夫鏈的收斂狀態,來達到評估LABSHTD問題的解的效能。 除此之外,我們利用解的複雜度來估算我們實作這個解所需要的硬體花費,有了效能與硬體花費兩項評估標準,我們發展了一套啟發式演算法在解空間中探索解,該演算法的目標函數是在特定的硬體花費下,尋找效能最好的解。由於解空間的成長數度是指數型態,我們的啟發式演算法能在多項式時間內得到相當不錯的結果。最後,我們也討論了如何將此演算法應用到算數編碼器上。 | zh_TW |
dc.description.abstract | A variable-bit look-ahead Huffman decoding problem is investigated in this Dissertation. When we used state diagrams to represent a variable-bit look-ahead Huffman decoder, we found that these state diagrams are not unique. Thus, we need to formulate the finding of state diagrams in a given variable-bit look-ahead Huffman decoding tree as a general look-ahead barrel-shift Huffman tree decomposition (LABSHTD) problem, such that many other variable-bit look-ahead Huffman decoding methods are just instances of this LABSHTD problem.
First, an important procedure that helps to build a correct mapping between a Huffman decoding state diagram and a Markov chain model is presented. The mapping makes it feasible to estimate the decoding throughput rate of an instance of the LABSHTD problem. Then, we use the implementation complexity to estimate the hardware resources required by a decoder instance and calculate the decoding throughput rate from the obtained Markov chain, which will be defined as an optimization problem. The objective of optimization is to maximize the decoding throughput rate by exploiting the solution space of a LABSHTD problem. Since the number of candidate solutions to the LABSHTD problem is growing exponentially, we propose an efficient algorithm to search for a heuristic solution that usually yields a very good optimization result in polynomial computation time. Finally, we show that this algorithm can be extended to solve the Arithmetic Decoding problem. | en |
dc.description.provenance | Made available in DSpace on 2021-06-14T16:45:47Z (GMT). No. of bitstreams: 1 ntu-100-D91921016-1.pdf: 869740 bytes, checksum: a69eb53e313a4536a2fe9b2e273994a2 (MD5) Previous issue date: 2011 | en |
dc.description.tableofcontents | ABSTRACT i
TABLE OF CONTENTS iii LIST OF FIGURES vii LIST OF TABLES ix CHAPTER 1 INTRODUCTION 1 1.1. Classical Implementation of Huffman Decoding 1 1.2. Privious Work Survey 3 1.3. Contribution 7 1.4. Organization 8 CHAPTER 2 BACKGROUND 9 2.1. Deterministic Finite State Machine 9 2.2. Variable-bit Look-ahead Implementation of DFSM 10 2.3. Machine Composition 11 2.4. Barrel Shifter 12 2.5. Markov Chain 13 2.6. Markov Chain Steady State Probability 14 CHAPTER 3 PERFORMANCE EVALUATION OF LOOK-AHEAD HUFFMAN DECODER 17 3.1. Decoding Throughput of Fixed-bit Look-Ahead 17 3.2. Decoding Throughput Problem of Variable-bit Look-Ahead 18 3.3. Look-ahead Barrel Shift Huffman Tree Decomposition Problem 19 3.4. Markov Chain Model for LABSHTD Problem 19 3.5. Expected Throughput Derived by Markov Chain Model 20 3.6. Applying Markov Chain to a Machine with Barrel Shifter 20 3.7. Average Throughput for a Long Period 24 3.8. Existence of Average Throughput for a Long Period 25 3.8.1. Existence of Eigenvector Corresponding to Eigenvalue 1 25 3.8.2. Single-Signed Eigenvector Corresponding to Eigenvalue 1 26 3.8.3. Jordan Canonical Form 28 3.8.4. Jordan Canonical Form of a Transition Probability Matrix 30 3.8.5. Proof of the Existence of Average Throughput 32 3.8.6. Average Throughput for a Long Period 34 3.8.7. Program to Approximate the Average Throughput 39 CHAPTER 4 OPTIMAL HUFFMAN DECODING 41 4.1. Notations 41 4.2. Making a State Machine from a Given States Set 43 4.3. Obtaining an Arbitrary Solution of the Kb-LABSHTD Problem 45 4.4. Derivation of Transition Matrics to Build a Markov Chain 46 4.5. Measurement of the Throughput of a Solution 50 CHAPTER 5 HEURISTIC OF OPTIMAL SOLUTION EXPLORATION 53 5.1. The Main Algorithm 53 5.2. Applying Main Algorithm on a Small Example 54 5.3. Further Optimization with Variable-bit Look-ahead Length 58 5.4. The Ultima Algorithm 60 5.5. Experiments for the Accuracy of Main Algorithm 61 5.6. Monte Carlo Simulation for the Cases Whose Distribution is not a Fair Coin 62 5.7. Some Discussion about the Non-Hit Cases 63 CHAPTER 6 THEORETIC DETAIL OF MACHINE AUTOMATA AND 71 EXTENSION TO ARITHMETIC CODING 71 6.1. Equivalent 73 6.2. Timeless Equivalent 74 6.3. Base Machine of Timeless Equivalent 75 6.4. A Simple Case to Verify Two Timeless Equivalent Machines 76 6.4.1. Building a Base Machine 77 6.4.2. Tranforming a Base Machine from NDFSM to DFSM 79 6.4.3. Simplifying the Base Machine 80 6.5. Extension to Arithmetic Coding 82 6.5.1. Look-up Table of Machine M1 83 6.5.2. Base Machine of Machine M1 86 6.5.3. Performance Analysis of an Arithmetic Decoder Instance 87 CHAPTER 7 CONCLUSION 89 REFERENCE 91 | |
dc.language.iso | en | |
dc.title | 多位元霍夫曼解碼器 | zh_TW |
dc.title | Multi-bit Huffman Decoder | en |
dc.type | Thesis | |
dc.date.schoolyear | 99-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 周哲民(Jer Min Jou),熊博安(Bo-An Xiong),何建明(Jan-Ming Ho),郭斯彥(Sy-Yen Kuo),李宗演(Trong-Yen Lee) | |
dc.subject.keyword | 霍夫曼解碼器, | zh_TW |
dc.subject.keyword | Huffman decoding,Huffman decoder,variable length coding,barrel shifter, | en |
dc.relation.page | 93 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2011-08-12 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-100-1.pdf 目前未授權公開取用 | 849.36 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。