Arithmetic Coding
Arithmetic Coding revealed – A guided tour from theory to praxis
Eric Bodden, Malte Clasen and Joachim Kneis
Technical Report SABLE-TR-2007-5
Sable Research Group, School of Computer Science, McGill University, 2007
Abstract
This document is an updated and translated version of the German paper Arithmetische Kodierung from 2002. It tries to be a comprehensive guide to the art of arithmetic coding. First we give an introduction to the mathematic principles involved. These build the foundation for the next chapters, where we describe the encoding and decoding algorithms for different numerical systems. Here we also mention various problems one can come across as well as solutions for those. This is followed by a proof of uniqueness and an estimation of the efficiency of the algorithm. In the end we briefly mention different kinds of statistical models, which are used to actually gain compression through the encoding. Throughout this paper we occasionally make some comparisons to the related Huffman encoding algorithm. Though, some rudimentary knowledge about Huffman encoding should suffice for the reader to follow the line of reasoning. This paper is mainly based on the works on Sayood and Bell. On the latter we base our implementation which is included in the appendix as full C++ source code. We also make use of parts of this code during some of our examples. The mathematical model we use, however, is strongly based on Sayood and Fano. Also we employ the well-known Shannon-Theorem, which proofs the entropy to be the bound of feasible lossless compression.
Download as PDF