Data Compression

Examples of Codes

Definition

A source code $C$ for a random variable $X$ is a mapping from $\mathcal{X}$, the range of $X$, to ${\mathcal{D}}^{\ast }$, the set of finite-length strings of symbols from a $D$-ary alphabet. Let $C(x)$ denote the codeword corresponding to $x$ and let $l(x)$ denote the length of $C(x)$.

For example, $C(\text{red})=00$, $C(\text{blue})=11$ is a source code for $\mathcal{X}=\left\{\text{red},\text{blue}\right\}$ with alphabet $\mathcal{D}=\left\{0,1\right\}$.

Length

The expected length $L(C)$ of a source code $C(x)$ for a random variable $X$ with PMF $p(x)$ is given by

$$L(C)=\mathbb{E}\left[l(x)\right]=\sum _{x\in \mathcal{X}}p(x)l(x)$$

where $l(x)$ is the length of the codeword associated with $x$.

Singularity

A code is said to be non-singular if every element of the range of $X$ maps into a different string in ${\mathcal{D}}^{\ast }$ (Injection); this is,

$$x\ne x^{\prime }⟹C(x)\ne C(x^{\prime })$$

Extension

The extension $C^{\ast }$ of a code $C$ is the mapping from finite-length strings of $\mathcal{X}$ to finite-length strings of $\mathcal{D}$, defined by

$$C(x_1{x}_2\cdots x_n):=C(x_1)C(x_2)\cdots C(x_n)$$

Example

If $C(x_1)=00$ and $C(x_2)=11$, then $C(x_1{x}_2)=0011$

Uniquely Decodable

A code is called uniquely decodable is its extension in non-singular.

Prefix Code

A code is called a prefix code or an instantaneous code if no codeword is a prefix of any other codeword.

Note

Instantaneous codes $\subset$ Uniquely decodable codes $\subset$ Nonsingular codes $\subset$ All codes

Summary

$X$	Singular	Nonsingular, But Not Uniquely Decodable	Uniquely Decodable, But Not Instantaneous	Instantaneous
1	0	0	10	0
2	0	010	00	10
3	0	01	11	110
4	0	10	110	111

Tip

The crucial difference of non-instantaneous code and instantaneous ones lies in the delay and complexity of decoding. While both can be decoded eventually, the non-instantaneous code incurs additional costs:

• For non-instantaneous code: Every encoded bitstream has only one possible original sequence of symbols. However, you might have to look ahead in the stream before you can definitively decode a symbol. It requires buffering bits and delaying the output.
• For instantaneous code: You can decode each symbol immediately as you read the bits. No lookahead is needed

Kraft Inequality

Motivation

We want to construct instantaneous codes of minimum expected length to describe a given source.

Definition

For any instantaneous code (prefix code) over an alphabet of size $D$, the codeword lengths $l_1,l_2,\dots ,l_m$ must satisfy the inequality

$$\sum _i{D}^{-l_i}\le 1$$

Conversely, given a set of codeword lengths that satisfy this inequality, there exists an instantaneous code with these word lengths.

Intuition

For an alphabet of size $D$, the tree is $D$-ary (each node has $D$ children). The "space" taken by a codeword of length $l_i$ id $D^{-l_i}$ (since it occupies one of the $D^{l_i}$ possible leaves at depth $l_i$). And the Kraft inequality ensures that the total "space" occupied by all codewords does not exceed the tatal available space (1).

Proof

Necessity: If a prefix code exists, then Kraft holds.

• Consider the full $D$-ary tree of depth $l_{\text{max}}$ (the longest codeword)
• A codeword of length $l_i$ blocks $D^{l_{\text{max}}-l_i}$ leaves (all its descendants)
• Since no two codewords share a leaf, the total number of blocked leaves is

$$\sum _i{D}^{l_{\text{max}}-l_i}\le D^{l_{\text{max}}}$$

• Dividing both sides by $D^{l_{\text{max}}}$ gives the inequality

Sufficiency: If Kraft holds, a prefix code exists.

• Sort the lengths $l_1\le l_2\le \cdots \le l_m$
• For each length $l_i$, pick any unused node at depth $l_i$ and block all its descendants.
• The Kraft Inequality ensures that there is always enough "space" to assign the next codeword without violating the prefix-free property.

Extended Kraft Inequality

For any countably infinite set of codewords that form a prefix code, the codeword lengths satisfy the extended Kraft inequality

$$\sum _{i=1}^{\infty }{D}^{-l_i}\le 1$$

Optimal Codes

Minimization via Lagrange multipliers

We want to minimize

$$L=\sum p_i{l}_i$$

over all integers $l_1,l_2,\dots ,l_m$ satisfying

$$\sum D^{-l_i}\le 1$$

We neglect the integer constraint on $l_i$ and assume equality in the constraint. Hence, we can write the constrained minimization using Lagrange multiplier as the minimization of

$$J=\sum p_i{l}_i+\lambda \left(\sum D^{-l_i}\right)$$

Setting $\frac{\partial J}{\partial l_i}=0$, we get $\lambda =\frac{1}{\ln D}$ and

$$p_i=D^{-l_i}⟹l_i^{\ast }=-{\log }_D{p}_i$$

This non-integer choice of codeword lengths yields expected codeword length

$$L^{\ast }=\sum p_i{l}_i^{\ast }=-\sum p_i{\log }_D{p}_i=H_D(X)$$

Lower bound of expected length

The expected length $L$ of any instantaneous $D$-ary code for a random variable $X$ is greater than or equal to the entropy $H_D(X)$; that is

$$L\ge H_D(X)$$

with equality if an only if $D^{-l_i}=p_i$.

Bounds on the Optimal Code Length

Let $l_1^{\ast },l_2^{\ast },\dots ,l_m^{\ast }$ be optimal codeword lengths for a source distribution $p$ and a $D$-ary alphabet, and let $L^{\ast }$ be the associated expected length of an optimal code ($L^{\ast }=\sum p_i{l}_i^{\ast }$). Then

$$H_D(X)\le L^{\ast }<H_D(X)+1$$

Therefore, the minimum expected codeword length per symbol satisfies

$$\frac{1}{n}H(X_1,X_2,\dots ,X_n)\le L_n^{\ast }<\frac{H(X_1,X_2,\dots ,X_n)}{n}+\frac{1}{n}$$

Wrong code

We can not always precisely estimate the real distribution of data. We consider the Shannon code assignment $l(x)=\lceil \log \frac{1}{q(x)}\rceil$ designed for the probability mass function $q(x)$. Suppose that the true probability mass function $p(x)$. Thus, we will not achieve expected length $L\approx H(p)=-\sum p(x)\log p(x)$.

We now show that the increase in expected length due to the incorrect distribution is the relative entropy $\mathbb{D}(p\Vert q)$:

$$H(p)+{\mathbb{D}}_{\text{KL}}(p\Vert q)\le {\mathbb{E}}_{p(x)}l(X)<H(p)+{\mathbb{D}}_{\text{KL}}(p\Vert q)+1$$

Kraft Inequality for Uniquely Decodable Codes

The codeword lengths of any uniquely decodable $D$-ary code must satisfy the Kraft inequality

$$\sum d^{-l_i}\le 1$$

Conversely, given a set of codeword lengths that satisfy this inequality, it is possible to construct a uniquely decodable code with these codeword lengths.

Corollary A uniquely decodable code for an infinite source alphabet $\mathcal{X}$ also satisfies the Kraft inequality.

Huffman Codes

Algorithm

An optimal prefix code for a given distribution can be constructed by a simple algorithm discovered by Huffman.

1. List the symbols and their probabilities in ascending order of probabilities (or any order if probabilities are the same).
2. For every iteration:
   1. Find the two symbols with the lowest probabilities
   2. Combine these two symbols into a new node, with a probability equal to the sum of their probabilities
   3. Assign '0' to the branch leading to the first symbol and '1' to the branch leading to the second symbol in our combined node.

Example

Consider a random variable $X$ taking in the set $\mathcal{X}=\left\{1,2,3,4,5\right\}$ with probabilities $0.25$, $0.25$, $0.2$, $0.15$, $0.15$

Now we get

Codeword Length	Codeword	X
2	11	1
2	00	2
2	01	3
3	100	4
3	101	5

Tip

If $D\ge 3$, we may not have a sufficient number of symbols so that we can always combine them $D$ at a time. In such a case, we add dummy symbols to the end of the set of symbols. The dummy symbols have probability $0$ and are inserted to fill the tree.

Since at each stage of the reduction, the number of symbols is reduced by $D-1$, we want the total number of symbols to be $1+k(D-1)$, where $k$ is the number of merges.