# Arithmetic coding for data compression

@article{Witten1987ArithmeticCF, title={Arithmetic coding for data compression}, author={Ian H. Witten and Radford M. Neal and John G. Cleary}, journal={Commun. ACM}, year={1987}, volume={30}, pages={520-540} }

The state of the art in data compression is arithmetic coding, not the better-known Huffman method. Arithmetic coding gives greater compression, is faster for adaptive models, and clearly separates the model from the channel encoding.

#### Figures, Tables, and Topics from this paper

#### 3,154 Citations

Arithmetic coding for data compression

- Computer Science
- 1994

This work shows how arithmetic coding works and describes an efficient implementation that uses table lookup as a first alternative to arithmetic operations that can speed up the implementation further by use of parallel processing. Expand

An Improved Bit-level Arithmetic Coding Algorithm

- Mathematics
- 2010

Arithmetic coding is the most powerful lossless data compression technique that has attracted much attention in recent years. This paper presents a new implementation of bit-level arithmetic coding… Expand

Data Coding and Image Compression

- Computer Science
- 2017

This Chapter provides an introduction to the realm of data compression and to approaches for image compression. Expand

A Faster Arithmetic Coder

- Computer Science
- 2006

This work proposes a novel method for arithmetic coding that runs at a significantly higher speed and can be implemented using simple hardware if required. Expand

A fast and efficient compression method for binary images

- Mathematics, Computer Science
- Signal Process. Image Commun.
- 1994

A composite modelling method is presented that reduces the size of the data to be coded by arithmetic coding and applies arithmetic coding to the areas with more variation to achieve a high compression ratio. Expand

Efficient decoding of prefix codes

- Computer Science
- CACM
- 1990

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… Expand

Introduction to Arithmetic Coding - Theory and Practice

- Mathematics
- 2004

entropy coding, compression, complexity This introduction to arithmetic coding is divided in two parts. The first explains how and why arithmetic coding works. We start presenting it in very general… Expand

An improved arithmetic coding algorithm

- Computer Science
- 2004

A new implementation of bit-level arithmetic coding by use of integer additions and shifts is presented, which has less computation complexity and is more flexible to use, and thus is very suitable for software and hardware design. Expand

Arithmetic Coding for Data Compression

- Computer Science
- Encyclopedia of Algorithms
- 2016

It is shown how arithmetic coding works and an implementation that uses table lookup as a fast alternative to arithmetic operations is described that can speed up the implementation further by use of parallel processing. Expand

Compression Based on Quasi-Arithmetic Coding

- 1994

We give a detailed algorithm for fast text compression. Our algorithm, related to the PPM method, simpliies the modeling phase by eliminating the escape mechanism and speeds up coding by using a… Expand

#### References

SHOWING 1-10 OF 24 REFERENCES

Arithmetic Coding

- Computer Science
- IBM J. Res. Dev.
- 1979

The earlier introduced arithmetic coding idea has been generalized to a very broad and flexible coding technique which includes virtually all known variable rate noiseless coding techniques as… Expand

Arithmetic stream coding using fixed precision registers

- Mathematics, Computer Science
- IEEE Trans. Inf. Theory
- 1979

Algorithms are presented for encoding and decoding strings of characters as real binary fractions, using registers of fixed precision, and have storage requirements and computation time O(n \log_{2}N) for string length n and alphabet size N. Expand

Generalized Kraft Inequality and Arithmetic Coding

- Mathematics, Computer Science
- IBM J. Res. Dev.
- 1976

This coding technique requires no blocking, and the per-symbol length of the encoded string approaches the associated entropy within ∈, which is comparable to that of conventional coding methods. Expand

Compression of Black-White Images with Arithmetic Coding

- Mathematics
- 1981

A new approach for black and white image compression is described, with which the eight CCITT test documents can be compressed in a lossless manner 20-30 percent better than with the best existing… Expand

Data Compression Using Adaptive Coding and Partial String Matching

- Computer Science
- IEEE Trans. Commun.
- 1984

This paper describes how the conflict can be resolved with partial string matching, and reports experimental results which show that mixed-case English text can be coded in as little as 2.2 bits/ character with no prior knowledge of the source. Expand

A locally adaptive data compression scheme

- Mathematics, Computer Science
- CACM
- 1986

A data compression scheme that exploits locality of reference, such as occurs when words are used frequently over short intervals and then fall into long periods of disuse, is described and proves that it never performs much worse than Huffman coding and can perform substantially better. Expand

An Introduction to Arithmetic Coding

- Mathematics, Computer Science
- IBM J. Res. Dev.
- 1984

This paper presents the key notions of arithmetic compression coding by means of simple examples and describes how the encoder must have successively partitioned and retained each nested subinterval. Expand

A Method for the Construction of Minimum-Redundancy Codes

- Mathematics
- 1952

An optimum method of coding an ensemble of messages consisting of a finite number of members is developed. A minimum-redundancy code is one constructed in such a way that the average number of coding… Expand

Data compression - techniques and applications: hardware and software considerations (3. ed.)

- Computer Science
- 1986

From the Publisher:
Provides professionals and students with a path to faster data transmission times and reduced transmission costs with its in-depth examination of practical and easy-to-implement… Expand

Universal modeling and coding

- Computer Science
- IEEE Trans. Inf. Theory
- 1981

A general class of so-called first-in first-out (FIFO) arithmetic codes is described which require no alphabet extension devices and which therefore can be used in conjunction with the best models. Expand