###
Piecewise Integer Mapping for Arithmetic Coding

Lang Stuiver

Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.

Alistair Moffat

Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.

#### Status

Proc. IEEE Data Compression Conference,
Snowbird, Utah, March/April 1998, pages 1-10.

#### Abstract

The principles of arithmetic coding are now well understood.
Despite this understanding, designers of industrial compression
systems continue to prefer bit-based coding methods such as
minimum-redundancy coding.
There are a number of reasons for this, but the principal one is that
arithmetic coding is computationally expensive compared
with static
minimum-redundancy coding.
Indeed, the slow speed of arithmetic coding
has provoked considerable efforts amongst
the compression research community, and a range of schemes
have been proposed to avoid or reduce the cost of the
bottleneck operations required in an arithmetic coder.
In this paper we add another technique.
By asking afresh exactly what it is the coder must do, we show how
much of the complexity of current coders can be dispensed with.
In particular, we eliminate all multiplicative operations in both
encoder and decoder, replacing them by comparisons and additions.
The essence of the proposal is a simple piecewise integer mapping,
hence the title of the paper.

As in all non-exact coders, some inefficiency is introduced.
We give analysis that shows the average loss caused by the revised
coder to be bounded in an expected sense by 0.0861 bits per symbol,
which for most compression applications is just one or two percent.
As an additional modification, we discuss a mechanism that allows multi-bit
output of codewords without compromising the precision of the
probability estimates that may be employed.
Finally, we give performance results that show that in combination
the two improvements yield a coder as much
as 50% faster than previous benchmark arithmetic coders.