ARITHMETIC CODING-Students Report

Overview
Arithmetic coding is especiallyuseful when dealing with sources with small alphabets, such as binary sources, and alphabets with highly skewed probabilities. It is also a very useful approach when, for various reasons, the modeling and coding aspects of lossless compression are to be
kept separate
Introduction
Recall that the coding rate is the average number of bits used. Huffman algorithm will generate a code whose rate is within pmax+0.086of the entropy, where pmax is the probability of the most frequently occurring symbol.
Coding a Sequence
In order to distinguish a sequence of symbols from another sequence of symbols we need to
tag it with a unique identifier. One possible set of tags for representing sequences of symbols
are the numbers in the unit interval [0,1). Because the number of numbers in the unit interval
is infinite. To use this technique, we need to map the source symbols or letters to numbers.
For convenience, in the discussion in this chapter we will use the mapping

and the cumulative density function can be defined as

Generating a Tag
The procedure for generating the tag works by reducing the size of the interval.We start out by first dividing the unit interval into subintervals of the form [FX (i ? 1),FX (i )), i = 1, . . ., m. Because the minimum value of the cdf is zero and the maximum value
is one, this exactly partitions the unit interval. We associate the subinterval [FX (i ?1), FX (i ))