Daniel S. Hirschberg
Abstract
A special case of the data compression problem is presented, in which a powerful encoder transmits a coded file to a decoder that has severely constrained memory. A data structure that achieves minimum storage is presented, and alternative methods that sacrifice a small amount of storage to attain faster decoding are described.
- 1 Apostolico, A., and Fraenkel, A. S. Robust transmission of unbounded strings using Fibonacci representations. IEEE Tra,s. Inf. Theory 33, 2 (Mar. a987). 238-245. Google Scholar
Digital Library
- 2 Choueka, Y., et al. Huffman coding without bit-manipulation. Tech. Rep. CS86-05, Weizmann In_stitute of Scien_ce, Dept. of Applied Mathematics, Rehovot, Israel, 1986.Google Scholar
- 3 Connell, J. B, A Huffman-Shannon-Fano code. Proc. IEEE 61, 7 (July (1973), I046-1047.Google Scholar
- 4 Hankamer, M. A modified Huffman procedure with reduced memory requirements. IEEE Trans. Commun. 27, 6 (June 1979), 930-932.Google ScholarCross Ref
- 5 Huffman, D. A. A method for the construction of minimum-redundancy codes. Proc. it~t: ,~u, u t~ept. 1952), 1098-1101.Google ScholarCross Ref
- 6 Lelewer, D. A., and Hirschberg, D. S. Data compression. ACM Comput. Surv. 19, 3 (Sept. 1987), 261-296. Google ScholarDigital Library
- 7 Schwartz, E, S., and Ka!!ick, B. Generati_n_g a canonica! prefix encoding. Commun. ACM 7, 3 (Mar. 1964), 166-169. Google ScholarDigital Library
- 8 Sieminski, A. Fast decoding of the Huffman codes. In/. Process. Lett. 26, 5 (May 1988), 237-241. Google ScholarDigital Library
- 9 Storer, J. A. Data Compression Methods and TheorF. Computer Science Press, Rockville, Md., 1988. Google ScholarDigital Library
- 10 Tanaka, H. Data structure of Huffman codes and its application to efficient encoding and decoding, iEEE Trans. infi Theory 33, i (jan. 1987), 154-156. Google ScholarDigital Library
- 11 Witten. I. H., Neal. R. M., and Cleary, J. G. Arithmetic coding for rtnta t~nmnroccicsn (-'nmnTun A("M '20 6 flllno 1 qR7l 520-.qz~fl Google ScholarDigital Library
Index Terms
- Efficient decoding of prefix codes
Recommendations
Complexity Reduction in SISO Decoding of Block Codes
SISO decoding for block codes can be carried out based on a trellis representation of the code. However, the complexity entailed by such decoding is most often prohibitive and thus prevents practical implementation. This paper examines a new decoding ...
Efficient maximum-likelihood decoding of LDPC codes over the binary erasure channel
We propose an efficient maximum-likelihood (ML) decoding algorithm for decoding low-density parity-check (LDPC) codes over the binary-erasure channel (BEC). We also analyze the computational complexity of the proposed algorithm.
Reviews
R. Nigel Horspool
The authors consider the problem of decoding Huffman codes (or prefix codes in general) using space-efficient data structures. Considered as a practical exercise in choosing and adapting tree structures to the needs of a particular problem, the paper has a modest contribution to make. The authors succeed in their particular purpose, and other implementers who need to attack a similar problem should find the material useful. I found the writing style to be too detailed and too focused on a relatively narrow problem. If the goal of using minimal storage is relaxed somewhat, other much faster decoding algorithms and better compression methods than Huffman coding become more attractive. For example, to decode Huffman codes, the method given by Choueka et al . [1] is much faster. Finally, the authors' claim that their Huffman coding can attain compression performance comparable with that of the UNIX compress program is not supported by any experimental data that I have ever seen.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments