EFFICIENT MULTIPLICATION-FREE 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 Huffman coding does. However, the m ultiplications needed in its encoding and decoding algorithms are very undesirable. Rissanen and Mohiuddin have proposed a simple scheme to avoid the multiplications. We found that the performance of their prop osed scheme might degrade significantly in some cases. In this paper, we propose a multiplication-free multialphabet arithmetic code which c an be shown to have minor performance degradation in all cases, In our proposed scheme, each multiplication is replaced by a single shift-an d-add, We will prove, by both theoretical analysis and simulation resu lts, that the degradation of the proposed multiplication-free scheme i s always several times (2-7 times in our experiments) smaller than tha t of the Rissanen-Mohiuddin's scheme.