Rescaling of Symbol Counts for Adaptive rANS Coding

Abstract

The abbreviation rANS stands for a relatively new method of arithmetic coding based on asymmetric numeral systems (ANS) which combines the advantages of arithmetic coding in terms of performance and the advantages of Huffman coding in terms of speed.
Compared to conventional arithmetic coding methods, the mathematical apparatus is slightly different which has the consequence that the decoding order is reversed to the encoding order, i.e. the processing follows the last-in-first-out principle.
This makes it somewhat difficult to design the coding process to adapt to changing symbol statistics, and therefore rANS coding has so far only been applied in settings with fixed statistics.
In particular, the frequent rescaling of statistics required to reduce the influence of old symbols becomes a problem when the order of processing is different on the encoder and decoder sides.

This paper proposes a new method that allows adaptive coding within the framework of rANS coding and additionally offers the possibility of rescaling the symbols frequencies. Investigations show that this method enables the same compression performance for rANS as for conventional arithmetic coding.

Mehr zum Titel