Coding and Information Theory Crash Course

Encoding

Let $A,B$ be two finite sets with size $a,b$ respectively.

Let $S(A)=\bigcup_{r=1}^{\infty}A^r$ be the word semigroup generated by $A$.

A one-to-one mapping $f:A\to S(B)$ is called a code with message alphabet $A$ and encoded alphabet $B$.

Example:

• $A=$ RGB color space
• $B=\{0\sim 255\}$
• $f:A\to B^n$ is a code

For example, $f(white)=(255,255,255)$, $f(green)=(0,255,0)$

Uniquely decipherable codes

A code $f:A\to S(B)$ is called uniquely decipherable if the extension code

is one-to-one.

Example:

• $A=\{a,b,c,d\}$
• $B=\{0,1\}$
• $f(a)=00$, $f(b)=01$, $f(c)=10$, $f(d)=11$

is uniquely decipherable.

• $f(a)=0$, $f(b)=1$, $f(c)=10$, $f(d)=11$

is not uniquely decipherable.

Since $\tilde{f}(ba)=10=\tilde{f}(c)$

Irreducible codes

A code $f:A\to S(B)$ is called irreducible if for any $x,y\in A$, $f(y)\neq f(x)w$ for some $w\in S(B)$.

This condition ensures that every message used in the encoding process is uniquely decipherable.

Means that there is no ambiguity in the decoding process.

Theorem 1.1.1 Sardinas and Patterson Theorem

Let $A,B$ be alphabet sets of size $a,b$ respectively.

Let $f:A\to S(B)$ be a code that is uniquely decipherable.

Then

where $l(f(x))$ is the length of the codeword $f(x)$. (Number of elements used in the codeword for $x$)

Proof:

Let $L$ denote the max length of the codeword for any $x\in A$.

$L=\max\{l(f(x))|x\in A\}$

Let $c_r$ be the number of codewords of length $r$.

Then

Note that $r$ is the length of the codeword.

The max number of elements that can be represented by $r$ elements in $B$ is $b^r$, so $c_r\leq b^r$.

This gives that the power series

converges to $R=\frac{1}{\limsup_{r\to\infty}\sqrt[r]{c_r}}\leq 1$.

So the sum of the probabilities of all the codewords must be less than or equal to 1.

Sardinas and Patterson Algorithm

Let $A=\{a_1,a_2,\cdots,a_n\}$ be the message alphabet and $B=\{b_1,b_2,\cdots,b_m\}$ be the encoded alphabet.

We test whether the code $f:A\to S(B)$ is uniquely decipherable.

def is_uniquely_decipherable(f):
    contain_common_prefix = 
    message_space=set()
    for x in A:
        if f(x) in message_space:
            return False
        message_space.add(f(x))
        for i in range(1,len(f(x))):
            if f(x)[:i] in message_space:
                contain_common_prefix = True
 
    while contain_common_prefix:
        contain_common_prefix = False
        for x in message_space:
            for y in message_space:
                code_length = min(len(x),len(y))
                if x[:code_length] == y[:code_length]:
                    contain_common_prefix = True
                    if len(x) < len(y):
                        message_space.add(y[code_length:])
                    else:
                        message_space.add(x[code_length:])
                    break
    return True

Shannon’s source coding theorem

Definition 1.1.4

An elementary information source is a pair $(A,\mu)$ where $A$ is an alphabet and $\mu$ is a probability distribution on $A$. $\mu$ is a function $\mu:A\to[0,1]$ such that $\sum_{a\in A}\mu(a)=1$.

The mean code word length of an information source $(A,\mu)$ given a code $f:A\to S(B)$ is defined as

The $L(\mu)$ of the mean code word length is defined as

Lemma: Jenson’s inequality

Let $f$ be a convex function on the interval $(a,b)$. Then for any $x_1,x_2,\cdots,x_n\in (a,b)$ and $\lambda_1,\lambda_2,\cdots,\lambda_n\in [0,1]$ such that $\sum_{i=1}^{n}\lambda_i=1$, we have

$f(\sum_{i=1}^{n}\lambda_ix_i)\leq \sum_{i=1}^{n}\lambda_if(x_i)$

Proof:

If $f$ is a convex function, there are three properties that useful for the proof:

1. $f''(x)\geq 0$ for all $x\in (a,b)$
2. For any $x,y\in (a,b)$, $f(x)\geq f(y)+(x-y)f'(y)$ (Take tangent line at $y$)
3. For any $x,y\in (a,b)$ and $0<\lambda<1$, we have $f(\lambda x+(1-\lambda)y)\leq \lambda f(x)+(1-\lambda)f(y)$ (Take line connecting $f(x)$ and $f(y)$)

We use $f(x)\geq f(y)+(x-y)f'(y)$, we replace $y=\sum_{i=1}^{n}\lambda_ix_i$ and $x=x_j$, we have

$f(x_j)\geq f(\sum_{i=1}^{n}\lambda_ix_i)+(x_j-\sum_{i=1}^{n}\lambda_ix_i)f'(\sum_{i=1}^{n}\lambda_ix_i)$

We sum all the inequalities, we have

Theorem 1.1.5

Shannon’s source coding theorem

Let $(A,\mu)$ be an elementary information source and let $b$ be the size of the encoded alphabet $B$.

Then

where $L(\mu)$ is the minimum mean code word length of all uniquely decipherable codes for $(A,\mu)$.

Entropy

Let $A$ be an alphabet and let $\mathcal{P}(A)$ be the set of all probability distributions on $A$. Any element $\mu\in \mathcal{P}(A)$ is thus a map from $A$ to $[0,1]$ such that $\sum_{a\in A}\mu(a)=1$.

Thus $\mathcal{P}(A)$ is a compact conves subset of real linear space $\mathbb{R}^A$.

We define the map $H:\mathcal{P}(A)\to\mathbb{R}$ as

Basic properties of $H$

1. $H(\mu)\geq 0$
2. $H(\mu)=0$ if and only if $\mu$ is a point mass.
3. $H(\mu)=\log_2|A|$ if and only if $\mu$ is uniform.

Huffman’s coding algorithm

Huffman’s coding algorithm is a greedy algorithm that constructs an optimal prefix code for a given probability distribution.

The algorithm is as follows:

1. Sort the symbols by their probabilities in descending order.
2. Merge the two symbols with the smallest probabilities and assign a new codeword to the merged symbol.
3. Repeat step 2 until there is only one symbol left.

import heapq
 
def huffman(frequencies):
    class Node:
        def __init__(self, symbol=None, freq=0, left=None, right=None):
            self.symbol = symbol
            self.freq = freq
            self.left = left
            self.right = right
        def __lt__(self, other):  # For priority queue
            return self.freq < other.freq
        def is_leaf(self):
            return self.symbol is not None
 
    # Build the Huffman tree
    heap = [Node(sym, freq) for sym, freq in frequencies.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(freq=left.freq + right.freq, left=left, right=right)
        heapq.heappush(heap, merged)
    root = heap[0]
 
    # Assign codes by traversing the tree
    codebook = {}
    def assign_codes(node, code=""):
        if node.is_leaf():
            codebook[node.symbol] = code
        else:
            assign_codes(node.left, code + "0")
            assign_codes(node.right, code + "1")
    assign_codes(root)
 
    # Helper to pretty print the binary tree
    def tree_repr(node, prefix=""):
        if node.is_leaf():
            return f"{prefix}→ {repr(node.symbol)} ({node.freq})\n"
        else:
            s = f"{prefix}• ({node.freq})\n"
            s += tree_repr(node.left, prefix + "  0 ")
            s += tree_repr(node.right, prefix + "  1 ")
            return s
 
    print("Huffman Codebook:")
    for sym in sorted(codebook, key=lambda s: frequencies[s], reverse=True):
        print(f"{repr(sym)}: {codebook[sym]}")
    print("\nCoding Tree:")
    print(tree_repr(root))
 
    return codebook

Definition 1.2.1

Let $A=\{a_1,a_2,\cdots,a_n\}$ be an alphabet and let $\mu=(\mu(a_1),\mu(a_2),\cdots,\mu(a_n))$ be a probability distribution on $A$.

Proof:

We use mathematical induction on the number of symbols $n$.

Base Case: $n=2$

Only two symbols — assign one “0”, the other “1”. This is clearly optimal (only possible choice).

Inductive Step:

Assume that Huffman’s algorithm produces an optimal code for $n-1$ symbols.

Now, given $n$ symbols, Huffman merges the two least probable symbols $a,b$ into $c$, and constructs an optimal code recursively for $n-1$ symbols. n−1 symbols.

By the inductive hypothesis, the code on $A'$ is optimal. is optimal.

By Step 2 above, assigning the two merged symbols $a$ and $b$ codewords $w_0$ and $w_1$ (based on 1.1.4) results in the optimal solution for $A$.

Therefore, by induction, Huffman’s algorithm gives an optimal prefix code for any $n$.