High efficiency, multiplication free approximation of arithmetic coding

Abstract

Arithmetic coding is a compression method that maps a sequence of symbols to an interval of real numbers [1], [2]. If the mapping is so constructed that some initial interval is divided among all possible messages (sequences), allocating to each message a subinterval that is proportional to its probability, compression down to the source entropy is reached. Obviously this can be achieved only if we know the correct probabilities. It was shown in [1] that the issues of determining the probabilities and the coding itself can be separated, and here we deal with the second issue only.