Efficient multiplication-free arithmetic codes

Abstract

Arithmetic coding is a powerful lossless data compression technique that has attracted much attention. It provides more flexibility and better efficiency than Huffman coding does. However, the multiplications needed in its encoding and decoding algorithms are very undesirable. Rissanen and Mohiuddin (1989) have proposed a simple scheme to avoid the multiplications. The present authors found that the performance of their proposed scheme might degrade significantly in some cases. They propose a multiplication-free multialphabet arithmetic code which can be shown to have minor performance degradation in all cases. In the proposed scheme, each multiplication is replaced by a single shift-and-add. The authors prove, by both theoretical analysis and simulation results, that the degradation of the proposed multiplication-free scheme is always several times (2-7 times in the present experiments) smaller than that of the Rissanen-Mohiuddin's scheme.