Keywords (1)

Academic
Publications
A Memory-Efficient Huffman Decoding Algorithm

A Memory-Efficient Huffman Decoding Algorithm,10.1109/AINA.2005.33,Pi-chung Wang,Yuan-rung Yang,Chun-liang Lee,Hung-yi Chang

A Memory-Efficient Huffman Decoding Algorithm   (Citations: 5)
BibTex | RIS | RefWorks Download
To reduce the memory size and fasten the process of searching for a symbol in a Huffman tree, we exploit the property of the encoded symbols and propose a memory- efficient data structure to represent the Huffman tree, which uses memory nd bits, where n is the number of source sym- bols and d is the depth of the Huffman tree. Based on the proposed data structure, we present an O(logn)-time Huff- man decoding algorithm. An adaptive version for single- side growing Huffman tree is also addressed. This ver- sion could improve the average performance from logn to n i=1� i/(h − 1) �× wilogh/ wi, where wi is the fre- quency for ith symbol and h is a pre-defined value.
Conference: Advanced Information Networking and Applications - AINA , vol. 2, pp. 475-479, 2005
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Various implementation techniques for Huffman coding have been studied and applied [1-7]...
    • ...Wang et al. proposed a new data structure on which the decoding time is O(n) where n is the number of source symbols [5]...

    Hoang-Anh Phamet al. An Adaptive Huffman Decoding Algorithm for MP3 Decoder

    • ...Various implementation techniques for Huffman coding have been studied and applied [1-7]...
    • ...Wang et al. proposed a new data structure on which the decoding time is O(n) where n is the number of source symbols [5]...

    Hoang-Anh Phamet al. An adaptive, memory-efficient and fast algorithm for Huffman decoding ...

    • ...SLA violation querying module, where we store a mapping table called SHT between historical SLA violations and the Huffman codes [9]...

    Huiji Zhanget al. A System for Fast Positioning SLA Violations

    • ...Several methods have been discussed for the implementation of Huffman decoding, including the direct lookup table method, the binary-tree memory-based method [13]–[15], and the parallel PLA-based method [16]–[18]...
    • ...Table III shows the comparisons of the implementation results of our parallel PLA-based Huffman tables with the binary-tree memory-based Huffman tables [13]...
    • ...In [13], each memory required entries, and each entry contains two fields: address and symbol, where is the number of codewords in a table...
    • ...We construct and synthesize the method in [13] with the same environment as ours...

    Tsung-Han Tsaiet al. Low-Power System Design for MPEG2/4 AAC Audio Decoder Using Pure ASIC ...

    • ...A binary search based method was proposed by Wang et al. in [12], where codewords were extended to a unique length (i.e., the depth of the HT)...
    • ...In this section, we focus on two subjects: 1) illustrating the benefit obtained from the prescribed metric and 2) comparing HASGT with previous well-known methods M1 [3], M2 [4], M3 [5], M4 [6], M5 [7], M6 [8], M7 [11] and M8 [12]...
    • ...The objective of this section is to compare the complexity of the previous methods [3]‐[8], [11], [12] and that of HASGT in terms of MA and MS. Moreover, to depict a clear picture, the cost of structure construction (CT) is also included...
    • ...The number of entries in CHT is linearly proportional to the number of various codelengths, so the MA complexity of M7 is . The memory usage of M7 depends directly on the numbers of symbols and different codelengths, so its MS complexity is . The construction of M7 is proportional to the number of entries in CHT, so its CT complexity is . M8 [12] records the starting addresses of symbols, thus both of its MS and CT complexities are . M8 ...
    • ...The objective of this subsection is to compare the performance of HASGT, upon actual data set, with that of previous works: M1 [3], M2 [4], M3 [5], M5 [7], M6 [8], and M8 [12]...
    • ...Under actual data set, the experimental results show that HASGT based approach performs better than previous approaches [3], [4], [7], [8], [12] in terms of memory size and memory access...

    Sung-wen Wanget al. Memory Efficient Hierarchical Lookup Tables for Mass Arbitrary-Side Gr...

Sort by: