請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40365
標題: | 多位元霍夫曼解碼器 Multi-bit Huffman Decoder |
作者: | Ya-Nan Wen 文亞南 |
指導教授: | 陳少傑(Sao-Jie Chen) |
關鍵字: | 霍夫曼解碼器, Huffman decoding,Huffman decoder,variable length coding,barrel shifter, |
出版年 : | 2011 |
學位: | 博士 |
摘要: | 在本論文中我們探討了變動位元先行霍夫曼解碼器的問題,我們將這樣的解碼器用狀態機來表示。文中我們發現,對於特定的霍夫曼解碼樹來說,其對應的變動位元先行狀態機並不唯一。我們將這個發現定義為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 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-100-1.pdf 目前未授權公開取用 | 849.36 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。