INFOTH Note 6: Kraft's Inequality, Shannon Code

6.1 Coding and Compression

Def: Code / Encoding

We define a coding/encoding map as follows:

We say this map is nonsingular iff it’s injective. (thesaurus)

The input is a sequence of source symbols (I call it a source word), and the output (image) is a codeword.

If the < means being a subset of,

• Instantaneous codes < Uniquely decodable codes < Nonsingular codes < All codes
• Nonsingular: injective (again)
• Uniquely decodable: Every sequence concatenated by codewords can only be decoded to only 1 source sequence.
  • The “Kleene Closure” of the map is also injective.
  • 整个由codeword接成的序列也只能被解码成唯一的source word序列。
• If $A\to0,B\to1,C\to01$, we cannot tell the original seq. from 0101 though this coding is nonsingular.

We can process the coding like a path in a binary tree.

Def: Multi-symbol Compression

as a multi-symbol compression of a concatenated source words, equal to a concatenation of codewords.

Def: Code Extension

The extension of predefined $c$ is

• variable finite length
• $\mathcal X=\{A,B\}$ then $\mathcal X^*=\{\empty,A,B,AA,AB,BB,AAA,AAB,ABA,\dots\}$

Def: Uniquely Decodable

$c$ is called uniquely decodable if its extension is nonsingular.

• UD -> Lossless Compression

Def: Prefix-free = Instantaneous

$c$ is called prefix-free or instantaneous if $\forall x\ne x'$, $c(x)$ is not a prefix of $c(x')$.

• UD but not PF codes:
  • $A\to 1,B\to 10$
  • $1\to0,2\to01,3\to11$

Theorem: Kraft’s Inequality

For any prefix free code over $\mathcal X$ i.e. $c:\mathcal X\to\{0,1\}^*-\empty$,

where $l(c(x))$ is the length of $c(x)$.

• The 2-exponentials of negative lengths of codewords sum up less than 1.

We can construct a binary tree for every prefix-free code. Every leaf represents a codeword, we goes left (down) to add 1 and right (up) to add 0, and the codeword is the path from the root to the leaf itself.

In the picture, we have 0,10,110,111 as codewords for a prefix-free code.

Proof. For the case with 2 leaves with length $h$ and value $2^{-h}$, they can be merged into their parents with a summed $2^{-h+1}$, or there are only 1 leaf and we merge $2^{-h}$ as it is. We find the case of max sum is when we reach a full binary tree (every leaf has 0 or 2 children), and the sum is 1. Otherwise, it’s smaller than 1.

6.2 Minimum Expected Length of the Code

For the space $\mathcal X$, every source word $x$ has a probability of appearance. So we want to minimize the expected length of the code over all prefix-free codes.

Converse Kraft’s Inequality

The original Kraft’s Ineq.: For a prefix-free code $c$, $\sum_x 2^{-l(c(x))}\le 1$

Converse:

Given $\mathcal X$ a finite set, given $(l(x),x\in\mathcal X)$ and $l(x)\ge 1$ (integers), $\forall x$ s.t.

then $\exist c:\mathcal X\to \{0,1\}^*-\empty$ s.t. $l(c(x))=l(x),\forall x$ and $c$ is a prefix-free code.

给定一组 $l(x)$ 函数的值，也就是一个正整数向量，如果满足Kraft的不等式则存在PF Code对应这个长度组。

Optimization

Converse Kraft -> We want to find such a collection of $l(x)$ to minimize the expected length (given a fixed $p$ distribution)

Since $\sum_{x}2^{-l(x)}\le 1$ we have already satisfied $l(x)\ge 0$, otherwise one term where $l(x)<0$ will make the sum greater than 1.

This problem is a difficult integer programming, so we do relaxation to real values.

Relaxation of Integer Programming

We relax the lengths to real values

KKT Conditions:

1. Lagrange Multiplier, Stationarity

   $$ L(x,\lambda)=\sum_xp(x)l(x)+\lambda(\sum_{x\in\mathcal X}2^{-l(x)}-1)\\ \nabla_{(l(x),x\in\mathcal X)} L=0 $$

2. Primal Feasibility

   $$ \sum_x 2^{-l(x)}\le 1 $$

3. Dual Feasibility

   $$ \lambda\ge 0 $$

4. Complementary Slackness

   $$ \lambda(\sum_x 2^{-l(x)}-1)=0 $$

(vector perspective)

(one of $l(x)$ perspective)

For any $x$,

Since $\sum_{x} 2^{-l(x)}=1$,

Hence the optimal solution $l^*(x)$ is

and we find that the expected length is the entropy of $p$

Coming back to IP

In integer programming i.e. the original problem, we can then find the solution:

where the ceiling is applied to satisfy the primal feasibility, and we call the code following this length collection a Shannon code.

Note that if we change the log base from 2 to $e$ or any other $D$, the solution still holds with $\log\equiv \log_D$.

6.3 Shannon Code

Def: Shannon Code $c_S$

Define on the finite set $\mathcal X$,

satisfying $\sum_x 2^{-l_S(x)}\le 1$ (converse Kraft’s inequality), therefore, there exists a prefix-free code

with $l(c_S(x))=l_S(x),\forall x$.

We call such a code a Shannon code, where

minimizes the expected length.

If the entropy is small…

If $H(X)$ is small, say, smaller than 1, the code for one symbol may be not so great.

However, we can do this over blocks of symbols (concatenation)

Block Shannon Code

For a block (multiple symbols) with $k$ symbols, i.i.d. the distribution $p$,

Then

So the average expected length for one symbol is

thereby we can use a long block to lower the length bound closer to the entropy.

Compression Rate

Though it’s late, we define the expected length as the compression rate that is

• UD but not Prefix-free is not better.
• Theorem: No UD codes have a better (smaller) compression rate than PF ones.

Kraft-McMillian Inequality

UD codes can also follow Kraft’s Inequality though. This conclusion expands that of PF to UDs.

Proof.

Consider a $k$-length symbol block. We consider the length of its codeword block.

Let $l_{\max}=\max_x l(c(x))$ then for any $k$-length block, since $c(\bold x^k)=c(x_1)+c(x_2)+\dots+c(x_k)$,

and we have

where $N(l)$ is the count of the codewords with length $l$. 某个长度的出现次数

But since the codeword of length $l$ is in $\{0,1\}^l$ with size $2^l$, $N(l)\le 2^l$, hence

Hence

When $k\to \infty$, the RHS approaches to 1, so