Low-memory, fixed-latency Huffman encoder for unbounded-length codes

R. A. Freking, Keshab K Parhi

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1031-1034
Number of pages4
JournalConference Record of the Asilomar Conference on Signals, Systems and Computers
Volume2
StatePublished - Dec 1 2000

Fingerprint Dive into the research topics of 'Low-memory, fixed-latency Huffman encoder for unbounded-length codes'. Together they form a unique fingerprint.

Cite this