ON THE FINITE-PRECISION IMPLEMENTATION OF ARITHMETIC CODES

Arithmetic coding is a powerful lossless data compression technique th at has attracted much attention in recent years. It provides more flex ibility and better efficiency than the celebrated Huffman coding does. In this paper, we discuss many issues on the finite-precision impleme ntation of arithmetic codes. Two main themes of the paper are: (1) uni que decodability, and (2) the performance degradation due to the finit e word-length effects. The necessary and sufficient conditions for uni que decodability are presented. Four sources of performance degradatio n are identified and quantitative analyses of three of them are given. Special attention is put on the degradation caused by the finite word -length registers used to compute the arithmetic codes. Theoretical an alysis and computer simulation of this effect are presented. It is fou nd that the degradation of algorithm I (using truncation) is much grea ter than that of algorithm II (using rounding or truncation). The degr adation of algorithm I is proportional to the size of the alphabet and is reduced by half for every increased bit of word length. On the oth er hand, the degradation of algorithm II is reduced to a quarter for e very increased bit of word length and only increases slightly when rou nding is replaced by truncation. (C) 1995 Academic Press, Inc.