On the Finite-Precision Implementation of Arithmetic Codes

✍ Scribed by Shaw-Min Lei

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 439 KB
• Volume: 6
• Category: Article
• ISSN: 1047-3203
• DOI: 10.1006/jvci.1995.1007

✦ Synopsis

Arithmetic coding is a powerful lossless data compression technique that has attracted much attention in recent years. It provides more flexibility and better efficiency than the celebrated Huffman coding does. In this paper, we discuss many issues on the finite-precision implementation of arithmetic codes. Two main themes of the paper are: (1) unique decodability, and (2) the performance degradation due to the finite word-length effects. The necessary and sufficient conditions for unique decodability are presented. Four sources of performance degradation 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 analysis and computer simulation of this effect are presented. It is found that the degradation of algorithm I (using truncation) is much greater than that of algorithm II (using rounding or truncation). The degradation 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 other hand, the degradation of algorithm II is reduced to a quarter for every increased bit of word length and only increases slightly when rounding is replaced by truncation. O 1995 Academic Prese, Inc.