Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40365
Title: | 多位元霍夫曼解碼器 Multi-bit Huffman Decoder |
Authors: | Ya-Nan Wen 文亞南 |
Advisor: | 陳少傑(Sao-Jie Chen) |
Keyword: | 霍夫曼解碼器, Huffman decoding,Huffman decoder,variable length coding,barrel shifter, |
Publication Year : | 2011 |
Degree: | 博士 |
Abstract: | 在本論文中我們探討了變動位元先行霍夫曼解碼器的問題,我們將這樣的解碼器用狀態機來表示。文中我們發現,對於特定的霍夫曼解碼樹來說,其對應的變動位元先行狀態機並不唯一。我們將這個發現定義為LABSHTD問題。在一個LABSHTD問題的解空間中的任意一個解,都可以對應到霍夫曼解碼器的實作。
為了尋找最好的實作方法,我們必須在解空間中尋找最佳解,這表示我們必須能夠評估每個解的效能。我們利用馬可夫鏈,並發現了一個方法讓變動位元先行的狀態機得以適用馬可夫鏈。進而透過計算馬可夫鏈的收斂狀態,來達到評估LABSHTD問題的解的效能。 除此之外,我們利用解的複雜度來估算我們實作這個解所需要的硬體花費,有了效能與硬體花費兩項評估標準,我們發展了一套啟發式演算法在解空間中探索解,該演算法的目標函數是在特定的硬體花費下,尋找效能最好的解。由於解空間的成長數度是指數型態,我們的啟發式演算法能在多項式時間內得到相當不錯的結果。最後,我們也討論了如何將此演算法應用到算數編碼器上。 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40365 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 電機工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-100-1.pdf Restricted Access | 849.36 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.