TY - JOUR
T1 - Low-memory, fixed-latency Huffman encoder for unbounded-length codes
AU - Freking, R. A.
AU - Parhi, Keshab K
PY - 2000
Y1 - 2000
N2 - The Huffman compression algorithm makes reference to a binary tree abstraction that can be employed directly as a data structure for decoding. Unfortunately, the same convenient arrangement has heretofore not served the encoding task. In this paper, the tree structure is revived in an enhanced form that allows encoding to progress naturally from root to leaf. Because this solution is tree based, code-words are not subject to length limitation. Yet, in marked contrast with other unbounded encoders, memory outlay is fixed by the size of the alphabet. Moreover, this storage expense is low in comparison with non-tree-based solutions. Also unlike previous tree structures, no post-encoding reversal is demanded resulting in constant-latency operation regardless of codeword length. Furthermore, only simple addition operators are required at each step. Despite its advantages, implementation is uncomplicated and codebook formatting is trivial.
AB - The Huffman compression algorithm makes reference to a binary tree abstraction that can be employed directly as a data structure for decoding. Unfortunately, the same convenient arrangement has heretofore not served the encoding task. In this paper, the tree structure is revived in an enhanced form that allows encoding to progress naturally from root to leaf. Because this solution is tree based, code-words are not subject to length limitation. Yet, in marked contrast with other unbounded encoders, memory outlay is fixed by the size of the alphabet. Moreover, this storage expense is low in comparison with non-tree-based solutions. Also unlike previous tree structures, no post-encoding reversal is demanded resulting in constant-latency operation regardless of codeword length. Furthermore, only simple addition operators are required at each step. Despite its advantages, implementation is uncomplicated and codebook formatting is trivial.
UR - http://www.scopus.com/inward/record.url?scp=0034441810&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034441810&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:0034441810
SN - 1058-6393
VL - 2
SP - 1031
EP - 1034
JO - Conference Record of the Asilomar Conference on Signals, Systems and Computers
JF - Conference Record of the Asilomar Conference on Signals, Systems and Computers
T2 - 34th Asilomar Conference
Y2 - 29 October 2000 through 1 November 2000
ER -