Contents

1 Limits of the Huffman code

• Any Huffman code satisfies that

  $$l\left(\right.c\left(s\right)\left)\right.=\lceil I\left(s\right)\rceil ,$$

  (Eq:Huffman)

  where $l\left(\right.c\left(s\right)\left)\right.$ is the length of the code-word assigned to the symbol $s$.

• This implies that, with every encoded symbol, up to 1 bit of redundant data can be introduced.
• This is a problem that grows when the size of the alphabet is small. In the extreme case, for binary source alphabets, the Huffman coding does not change the length of the original representation.

2 Achivements

• The arithmetic coding relaxes the Equation Eq:Huffman, verifying that, for every encoded symbol,

  $$l\left(\right.c\left(s\right)\left)\right.=I\left(s\right),$$

  (Eq:arithmetic)

  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, the 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.

3 The ideal encoder

1. Let $\left[L,H\right)\leftarrow \left[0.0,1.0\right)$ an interval of real numbers.
2. While the input is not exhausted:
   1. Split $\left[L,H\right)$ 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 $\left[L^{\prime },H^{\prime }\right)$ associated with the encoded symbol.
   3. $\left[L,H\right)\leftarrow \left[L^{\prime },H^{\prime }\right)$.
3. Output a real number $x\in \left[L,H\right)$ (the arithmetic code-stream). The number of decimals of $x$ should be large enough to distinguish the final sub-interval $\left[L,H\right)$ from the rest of possibilities.

Example

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

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 are identical as the interval is reduced. These bits are going to contribute to the arithmetic code, therefore, they can be output as soon as they are known.

  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 by 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 $\left[0.50,1.00\right)$ interval to the $\left[0.00,1.00\right)$.

5 The ideal decoder

1. Let $\left[L,H\right)\leftarrow \left[0.0,1.0\right)$ the initial interval.
2. While the input is not exhausted:
   1. Split $\left[L,H\right)$ 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. Input so many bits of $x$ as they are needed to:
      1. Select the sub-interval $\left[L^{\prime },H^{\prime }\right)$ that contains $x$.
      2. Output the symbol that $\left[L^{\prime },H^{\prime }\right)$ represents.
      3. $\left[L,H\right)\leftarrow \left[L^{\prime },H^{\prime }\right)$.