LOW-PRECISION ARITHMETIC CODING IMPLEMENTATION
Radford M. Neal
Initial release: 8 July 1991
Documentation update: 16 July 1991
Bug fix: 25 July 1991
Bug fix: 16 Sept 1992
Changes for ANSI C compatibility: 29 October 1992
Bug fix: 19 May 1993
This directory contains C source for an implementation of arithmetic
coding using low-precision division. This division can be performed
using shift/add operations, with potential savings in time on any
machine without parallel multiply/divide hardware.
The implementation is based on that in the paper of Witten, Neal, and
Cleary published in the June 1987 Communications of the ACM. Anyone
wishing to understand this program is urged to first read that paper.
Differences in this version are as follows:
1) The arithmetic coding operations have been fiddled so that
the division involved can be done to very low precision.
There is a tradeoff between precision and compression performance,
but nearly optimal results are obtained with a precision of
six bits, and precisions of as low as three bits give reasonable
results. A precision of at least two bits is required for
correct operation.
2) In order for (1) to be possible, the model is now required
to produce "partially normalized" frequencies, in which the
total for all symbols is always more than half the maximum
allowed total. This is not onerous, at least for the models
used here.
3) The model must also now arrainge for the most probable symbol
to have index 1. This was always the case, but previously
this was solely a matter of time efficiency. Now, failure
to do this would impact compression efficiency, though not
correct operation.
4) The precision to which symbol frequencies may be held is much
higher in this implementation - 27 bits with the default
parameter settings. The CACM implementation was restricted
to 14 bit frequencies. This is of significance in applications
where the number of symbols is large, such as with word-based
models.
5) Encode/decode procedures specialized for use with a two-symbol
alphabet have been added. These are demonstrated by a simple
adaptive image compression program.
6) Various minor modifications and structural changes to the
program have been made.
Two versions of the coding procedures are provided - one using C
multiply and divide operators, the other using shifts and adds. These
versions, and the resulting encode/decode programs, are distinguished
by the suffixes "_mul" and "_sft". Which version is fastest will
depend on the particular machine and compiler used. All encode/decode
programs simply read from standard input and write to standard output.
The file 'tstpic' contains a test picture for the image
encoding/decoding programs. The format of such pictures may be
discerned by examination of this example, and of the program code.
A program for calculating a bound on maximum expected redundancy
resulting from low-precision division is included. Typical redundancy
is much less than this bound.
For the multiply/divide version, the requirement that the model
produce partially normalized frequencies is not really necessary.
The program is intended for demonstation purposes. It is not optimized
for time efficiency, and provides little in the way of error checking.
The method used in this program has some resemblences to that presented
by Rissanen and Mohiuddin in "A Multiplication-Free Multialphabet Arithmetic
Code", IEEE Transactions on Communications, February, 1989. The main
similarities are the following:
1) The idea of constraining the size of the coding region and the
range of the occurrence counts so as to allow an approximation.
2) The placement of the most-probable symbol at the top of the
coding region.
There are a number of significant dissimilarities, however. The details
of the constraints mentioned above are different. The low-precision
method implemented here is more general, giving a smooth trade-off between
compression performance and speed through choice of precision for the
multiplication and division. Other unique features of this code include:
1) Incremental maintenance of partialy-normalized occurrence counts,
eliminating the need for such normalization in the coding process,
as is the case with the Rissanen and Mohiuddin method.
2) Merging of multiply and divide operations for faster operation
with serial arithmetic (not relevant in the less-general Rissanen
and Mohiuddin method).
3) A variable-precision computation in order to locate the next
symbol in the non-binary decode procedure (also not relevant in
the Rissanen and Mohiuddin method).
The Rissanen and Mohiuddin method should be somewhat faster than that
used here. Its coding efficiency appears similar to that which would be
obtained with this method if divisions are performed to a precision of
two bits.
The detailed algorithm presented in the paper by Rissanen and Mohiuddin
uses the supposedly patented "bit stuffing" procedure. This procedure
is _not_ used in this code.
This code is public domain, and may be used by anyone for any purpose.
I do, however, expect that distributions utilizing this code will
include an acknowledgement of its source. The program is provided
without any warranty as to correct operation. The Rissanen and
Mohiuddin method is said to be patented, and I can offer no guarantees
as to whether use of the code presented here might infringe those
patents (off hand, this would seem to be a complex question with no
definitive answer). My amateur understanding of patent law leads me to
believe that use for research purposes would be permitted under any
circumstances, but I could well be deluded in this regard.
Address comments to:
Radford Neal
Dept. of Computer Science
University of Toronto
10 King's College Road
Toronto, Ontario, CANADA
M5S 1A4
e-mail: radford@ai.toronto.edu