Probability estimation in arithmetic and adaptive-Huffman entropy coders
Authors:
- C. ChamzasCCC. Chamzas
- 1 March 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Image Processing
- Vol. 4 (3) , 237-246
Abstract
Entropy coders, such as Huffman and arithmetic coders, achieve compression by exploiting nonuniformity in the probabilities under which a random variable to be coded takes on its possible values. Practical realizations generally require running adaptive estimates of these probabilities. An analysis of the relationship between estimation quality and the resulting coding efficiency suggests a particular scheme, dubbed scaled-count, for obtaining such estimates. It can optimally balance estimation accuracy against a need for rapid response to changing underlying statistics. When the symbols being coded are from a binary alphabet, simple hardware and software implementations requiring almost no computation are possible. A scaled-count adaptive probability estimator of the type described in this paper is used in the arithmetic coder of the JBIG and JPEG image coding standardsKeywords
This publication has 12 references indexed in Scilit:
- Technical features of the JBIG standard for progressive bi-level image compressionSignal Processing: Image Communication, 1992
- The JPEG still picture compression standardCommunications of the ACM, 1991
- An overview of the basic principles of the Q-Coder adaptive binary arithmetic coderIBM Journal of Research and Development, 1988
- Arithmetic coding for data compressionCommunications of the ACM, 1987
- A Double-Adaptive File Compression AlgorithmIEEE Transactions on Communications, 1983
- Compression of Black-White Images with Arithmetic CodingIEEE Transactions on Communications, 1981
- Arithmetic stream coding using fixed precision registersIEEE Transactions on Information Theory, 1979
- Generalized Kraft Inequality and Arithmetic CodingIBM Journal of Research and Development, 1976
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948