Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(1)
Data Structure
Subscribe
Academic
Publications
A MemoryEfficient Huffman Decoding Algorithm
A MemoryEfficient Huffman Decoding Algorithm,10.1109/AINA.2005.33,Pichung Wang,Yuanrung Yang,Chunliang Lee,Hungyi Chang
Edit
A MemoryEfficient Huffman Decoding Algorithm
(
Citations: 5
)
BibTex

RIS

RefWorks
Download
Pichung Wang
,
Yuanrung Yang
,
Chunliang Lee
,
Hungyi Chang
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 predefined value.
Conference:
Advanced Information Networking and Applications  AINA
, vol. 2, pp. 475479, 2005
DOI:
10.1109/AINA.2005.33
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.
(
nclab.cs.nchu.edu.tw
)
(
www.informatik.unitrier.de
)
(
www.csie.nctu.edu.tw
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
(
doi.ieeecomputersociety.org
)
More »
Citation Context
(5)
...Various implementation techniques for Huffman coding have been studied and applied [
17
]...
...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
]...
HoangAnh Pham
,
et al.
An Adaptive Huffman Decoding Algorithm for MP3 Decoder
...Various implementation techniques for Huffman coding have been studied and applied [
17
]...
...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
]...
HoangAnh Pham
,
et al.
An adaptive, memoryefficient 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 Zhang
,
et 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 binarytree memorybased method [
13
]–[15], and the parallel PLAbased method [16]–[18]...
...Table III shows the comparisons of the implementation results of our parallel PLAbased Huffman tables with the binarytree memorybased 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...
TsungHan Tsai
,
et al.
LowPower 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 wellknown 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...
Sungwen Wang
,
et al.
Memory Efficient Hierarchical Lookup Tables for Mass ArbitrarySide Gr...
References
(7)
JPEG  Still Image Data Compression Standard
(
Citations: 1023
)
William B. Pennebaker
,
Joan L. Mitchell
Published in 1993.
A method for the construction of minimumredundancy codes
(
Citations: 1340
)
David A. Huffman
Journal:
Resonance
, vol. 11, no. 2, pp. 9199, 2006
Coding and Information Theory
(
Citations: 155
)
S. Roman
Published in 1992.
Memory efficient and highspeed search Huffman coding
(
Citations: 44
)
Reza Hashemian
Journal:
IEEE Transactions on Communications  TCOM
, vol. 43, no. 10, pp. 25762581, 1995
Efficient Huffman Decoding
(
Citations: 14
)
Kuoling Chung
Journal:
Information Processing Letters  IPL
, vol. 61, no. 2, pp. 9799, 1997
Sort by:
Citations
(5)
An Adaptive Huffman Decoding Algorithm for MP3 Decoder
HoangAnh Pham
,
VanHieu Bui
,
AnhVu DinhDuc
Conference:
Workshop on Electronic Design, Test and Applications  DELTA
, pp. 153157, 2010
An adaptive, memoryefficient and fast algorithm for Huffman decoding and its implementation
(
Citations: 2
)
HoangAnh Pham
,
VanHieu Bui
,
AnhVu DinhDuc
Conference:
International Conference on Interaction Sciences  ICIS
, pp. 275279, 2009
A System for Fast Positioning SLA Violations
Huiji Zhang
,
Zhipeng Gao
,
Wenjing Li
Conference:
International Conference on Wireless Communications, Networking and Mobile Computing  WiCom
, 2009
LowPower System Design for MPEG2/4 AAC Audio Decoder Using Pure ASIC Approach
TsungHan Tsai
,
ChunNan Liu
Journal:
IEEE Transactions on Circuits and Systems Iregular Papers  IEEE TRANS CIRCUIT SYSTI
, vol. 56, no. 1, pp. 144155, 2009
Memory Efficient Hierarchical Lookup Tables for Mass ArbitrarySide Growing Huffman Trees Decoding
Sungwen Wang
,
Jaling Wu
,
Shangchih Chuang
,
Chihchieh Hsiao
,
Yishin Tung
Journal:
IEEE Transactions on Circuits and Systems for Video Technology  TCSV
, vol. 18, no. 10, pp. 13351346, 2008