A greedy renormalization method for arithmetic coding

Abstract

A typical arithmetic coder consists of three steps: range calculation, renormalization, and probability model updating. In this paper, we propose and analyze from an information theoretic point of view a greedy renormalization method, which has two components: greedy thresholding and greedy outputting. The method significantly reduces the computational complexity of the renormalization step of arithmetic coding by 1) using the greedy thresholding to minimize the number of renormalizations required to encode a sequence and 2) using the greedy outputting to minimize the number of operations within each renormalization. The method is particularly suitable for binary arithmetic coding (BAC). Two BAC algorithms based on this method are presented. The first algorithm replaces the renormalization method in the TOIS BAC [2] with the greedy renormalization method, and keeps other parts of the TOIS BAC unchanged. For binary independent and identically distributed (i.i.d.) sources with the probability of the less probable symbol ranging from 0.01-0.45, over 20% gain in speed (on average), and less than 1% loss in compression rate (in the worst case) are observed in the experiments. The second algorithm combines the greedy renormalization method with the QM-Coder. On an average, 30% gain in speed and 3% gain in compression rate are observed in the experiments. © 2007 IEEE.