Contents

1 How they work

• We can compress if each symbol is translated by code-words and, in average, the lengths of the code-words are smaller than the length of the symbols.
• The encoder and the decoder have a probabilistic model $M$ which says to the variable-length encoder ($C$)/decoder($C^{-1}$) the probability $p\left(s\right)$ of each symbol $s$ (see Figure 1).
• The most probable symbols are represented by the shorter code-words and viceversa.

2 Bit of data and bit of information

• Data is the representation of the information.
• Lossless data compression uses a shorter representation of the information.
• By definition, a bit of data stores a bit of information if and only if it represents the occurrence of an equiprobable event (an event that can be true or false with the same probability).
• By definition, a symbol $s$ with probability $p\left(s\right)$ stores

  $$I\left(s\right)=-{log}_{2}p\left(s\right)$$

  (Eq:symbol_information)

  bits of information.

• The length of the code-word depends on the probability as:

3 Entropy of a information source

• The entropy $H\left(S\right)$ measures the amount of information per symbol that a source of information $S$ produces, in average, i.e.

  $$H\left(S\right)=\frac{1}{N}\sum _{s=1}^{N}p\left(s\right)\times I\left(s\right)$$

  (1)

  bits-of-information/symbol, where $N$ is the size of the source alphabet (number of different symbols).

4 Algorithms

1. Universal coding.
2. Shannon-Fano coding.
3. Huffman coding.
4. Arithmetic coding.
5. Probabilistic models.
6. The move-to-front transform.
7. The prediction-based transform
8. Unitary coding.
9. Golomb coding.