Contents

1 Basics

• Arithmetic coding [2, 3, 1] relaxes the Eq. (Eq:Huffman), verifying that, for every encoded symbol, \begin {equation} l\big (c(s)\big ) = I(s), \tag {Eq:arithmetic} \end {equation} i.e. the number of bits of data (code-word) assigned by the encoder is equal to the number of bits of information that the symbol represent.

• It can be said that, arithmetic coding is optimal because the average length of an arithmetic code is equal to the entropy of the information source, measured in bits/symbol.

2 An ideal encoder

1. Let \([L,H)\leftarrow [0.0,1.0)\) an interval of real numbers.

2. While the input is not exhausted:

   1. Split \([L,H)\) into so many sub-intervals as different symbols are in the alphabet. The size of each sub-interval is proportional to the probability of the corresponding symbol.
   2. Select the sub-interval \([L',H')\) associated with the encoded symbol.
   3. \([L,H)\leftarrow [L',H')\).
3. Output a real number \(x\in [L,H)\) (the arithmetic code-stream). The number of decimals of \(x\) should be large enough to distinguish the final sub-interval \([L,H)\) from the rest of possibilities.

2.1 Example

• Imagine a binary sequence, where \(p(\text {A})=3/4\) and \(p(\text {B})=1/4\). Compute the arithmetic code of the sequences A, B, AA, AB, BA y BB.

3 An ideal decoder

1. Let \([L,H)\leftarrow [0.0,1.0)\) the initial interval.

2. While the input is not exhausted:

   1. Split \([L,H)\) in so many sub-intervals as different symbols are in the alphabet. The size of each sub-interval is proportional to the probability of the corresponding symbol.

   2. Input so many bits of \(x\) as they are needed to:

      1. Select the sub-interval \([L',H')\) that contains \(x\).
      2. Output the symbol that \([L',H')\) represents.
      3. \([L,H)\leftarrow [L',H')\).

4 Incremental transmission

• It is not necessary to wait for the end of the encoding to generate the arithmetic code. When we work with binary representations of the real numbers \(L\) and \(H\), their most significant bits become identical when the interval is reduced. These bits belong to the output arithmetic code, therefore, they can be output as soon as they match.

  For example, when the symbol B is encoded, a code-bit 1 can be output because any sequence of symbols that start with B have a code-word that begins with 1.

• When the most significant bits of \(L\) and \(H\) are output, the bits of each register are shifted to the left, and new bits need to be inserted. The results is an automatic zoom of the selected sub-interval.

  Following with the previous example, the register shifting generates an ampliation of the \([0.50,1.00)\) interval to the \([0.00,1.00)\).