以性能損失與資源需求為最佳化基礎之霍夫曼樹可變長 度碼解碼架構

Abstract

本博士論文旨在研究能應用於處理以霍夫曼樹為基礎之熵函數快速解碼技 術。一般說來，在早期的熵函數快速解碼技術中可概略的分為兩種方式：於位元 串流中(一)一次讀取一個位元數，以及(二)一次讀取數個位元數。一次讀取一個 位元數的方式只需要相當少的資料結構即可處理可變長度解碼，但是解碼的速度 較為緩慢。而一次讀取數個位元數的方式是一種特別的關連記憶體資料結構，我 們於位元串流中一次讀取數個位元數的值當作在關連記憶體資料結構中的索 引，並儲存適當的資訊於關連資料結構中，每當索引到正確的位置時即回覆其相 關資訊。這種關連資料結構的方式能快速的索引到正確的值，但是帶來的缺點卻 是大量的浪費記憶體使用空間。本論文即針對快速處理之需求與所需使用之資源 設計出一具有最佳化之架構，此架構之特點是可以於有限資源內尋找出最為快速 的可變長度碼解碼方法。同時，由於一次讀取一個位元數的方法於實際應用中不 易達到即時處理之需求，本論文發展出一種新式的關連索引技術，其可一次讀取 數個位元數的方式並且相當節省的使用所需之記憶體，並於文末實驗中證明與其 他方式比較下，所提出的架構能夠達到快速索引與資源需求最低的最佳化。於霍 夫曼樹為基礎之熵函數快速解碼技術中本研究共有兩大貢獻：(一)定義出合適的 公制標準用以評量解熵函數之演算法，以及(二)發展出一階層式之關連式索引技 術其可適應於不同結構之霍夫曼樹。

Due to its sequential nature, speeding up Variable Length Decoding(VLD) is not as straightforward as to speed up the other modules of a decoding process by issuing several independent instructions simultaneously. The conservative VLD approaches restricted in a fixed algorithmic realization which might not be suitable for different applications’ need. In this dissertation, we design an algorithmic level VLD optimization framework on the basis of penalty and resource, which can be automatically synthesized to match the resource constraints of target applications. More specifically, this work demonstrates an optimization methodology for minimizing the number of memory access subject to a memory size constraint for any Huffman-based variable length code decoding. We also propose a structure of memory-efficient hierarchical lookup table which can adapt to arbitrary-side growing Huffman-trees adopted in current CODECs. The proposed design decomposes theVLDinto a combination of multiple table lookups and imperative operations. A Viterbi-like algorithm is also proposed to efficiently find the optimal hierarchical table. More importantly, the Viterbi-like algorithm obtains the same results as that of the brute-force search algorithm. Simulation results show that the proposed hierarchical table outperforms previous methods. To provide explicit illustration of hierarchical tables we also sketch the optimal solution for Huffman-trees adopted in current CODECs.