Memory Efficient Hierarchical Lookup Tables for Mass Arbitrary-Side Growing Huffman Trees Decoding
| Autor: | Ja-Ling Wu, Chuang Shang-Chih, Chih-chieh Hsiao, Sung-Wen Wang, Yi-Shin Tung |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Theoretical computer science
Computer science Data_CODINGANDINFORMATIONTHEORY Data structure Huffman coding symbols.namesake Tree structure Canonical Huffman code Viterbi decoder Search algorithm Computer Science::Multimedia Lookup table Media Technology symbols Codec Entropy (information theory) Electrical and Electronic Engineering Algorithm Decoding methods Computer Science::Information Theory |
| Zdroj: | IEEE Transactions on Circuits and Systems for Video Technology. 18:1335-1346 |
| ISSN: | 1558-2205 1051-8215 |
| DOI: | 10.1109/tcsvt.2008.920968 |
| Popis: | This paper addresses the optimization problem of minimizing the number of memory access subject to a rate constraint for any Huffman decoding of various standard codecs. We propose a Lagrangian multiplier based penalty-resource metric to be the targeting cost function. To the best of our knowledge, there is few related discussion, in the literature, on providing a criterion to judge the approaches of entropy decoding under resource constraint. The existing approaches which dealt with the decoding of the single-side growing Huffman tree may not be memory-efficient for arbitrary-side growing Huffman trees adopted in current codecs. By grouping the common prefix part of a Huffman tree, in stead of the commonly used single-side growing Huffman tree, we provide a memory efficient hierarchical lookup table to speed up the Huffman decoding. Simulation results show that the proposed hierarchical table outperforms previous methods. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|