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.