Loading...
Thumbnail Image
Item

Arithmetic coding revisited

Abstract
Over the last decade, arithmetic coding has emerged as an important compression tool. It is now the method of choice for adaptive coding on multisymbol alphabets because of its speed, low storage requirements, and effectiveness of compression. This article describes a new implementation of arithmetic coding that incorporates several improvements over a widely used earlier version by Witten, Neal, and Cleary, which has become a de facto standard. These improvements include fewer multiplicative operations, greatly extended range of alphabet sizes and symbol probabilities, and the use of low-precision arithmetic, permitting implementation by fast shift/add operations. We also describe a modular structure that separates the coding, modeling, and probability estimation components of a compression system. To motivate the improved coder, we consider the needs of a word-based text compression program. We report a range of experimental results using this and other models. Complete source code is available.
Type
Journal Article
Type of thesis
Series
Citation
Moffat, A., Neal, R. M. & Witten, I. H. (1998). Arithmetic coding revisited. ACM Transactions on Information Systems, 16(3) 256-294.
Date
1998-07-01
Publisher
ASSOC COMPUTING MACHINERY
Degree
Supervisors
Rights
This document is available online at ACM Transactions on Information Systems.