be the
cumulative probability of 
.
Then associate to a source sequence the source interval
.
Note that all source intervals 
are disjoint, and that their
union is [0,1).
Also to a codeword there corresponds an interval.
To codeword c having length L there corresponds an interval
, where .c is the number obtained by
considering c as a binary fraction.
Note that a codeword can only be the prefix of another codeword if
its code interval contains the code interval of the other codeword.
The idea of arithmetic coding is to choose for a given source sequence
the codeword 
with a code interval 
inside
.
This is obtained by taking
where 
is the smallest integer 
.
This follows from
in which we simplified the notation a little bit.
Example:Let T=2 and consider again a memoryless source with
. The source intervals, codewords, and redundancies are
put in the table.
Since 
we may
conclude that arithmetic coding achieves codeword lengths within
2 bit from the ideal codeword length, or 
for all
.
This implies also that 
or 
.
For the cumulative probability we can write (Elias):
This makes it easy to compute this probability (and 
) if,
after knowing 
and 
we can easily compute 
and
.
Example:For T=3 and a memoryless source having we
get e.g. 
and 
.
If we use, instead of the actual distribution , an arbitrary
coding distribution 
, we obtain codeword lengths for
which
We say that the coding redundancy is smaller than 2 bits.
Note that it is necessary that 
for such
that 
.
Note that arithmetic coding achieves codeword lengths that are very
close to what we want (i.e. 
) and that no tables are
needed to store the code (the codeword is computed from the source
sequence and vice versa).
Issues regarding implementation of this technique are considered e.g.
by Rissanen[4] and Pasco[3].
We now have to concentrate on constructing good coding distributions.
