Comparative analysis of arithmetic coding computational complexity
Amir Said · 2004
New hardware is making obsolete previous assumptions about the most demanding computations for arithmetic coding. The important arithmetic coding tasks include: (a) interval update and arithmetic operations; (b) carry propagation and bit moves; (c) interval renormalization; (d) interval search for decoding; (e) probability estimation (source modeling); (f) support for nonbinary symbol alphabets. In this paper, the performance of binary arithmetic coding implemented with 16, 32 bit integer and 48 bit floating-point arithmetic is benchmarked. Results show that significantly faster adaptation, with small coding loss, can be obtained by periodic updates of the probability estimation.