Uniquely Decodable Codes

The Kraft-McMillan Inequality

The Kraft-McMillan inequality provides (1) a necessary condition for unique decodability, and (2) a sufficient condition for the existence of uniquely decodable codes.

• (Necessity.) Let ${\mathcal {C}}$ be a $D$-ary uniquely decodable code whose codewords have lengths $l_{1},l_{2},...l_{m}$. Then, $\sum _{i}D^{-l_{i}}\leq 1.$

• (Sufficiency.) Let $l_{1},l_{2},...,l_{m}$ be a sequence of positive integers such that $\sum _{i}D^{-l_{i}}\leq 1.$. Then, there exists a uniquely decodable code $C$ whose codewords have lengths $l_{1},l_{2},...,l_{m}$.

Since all instantaneous/prefix-free codes are uniquely decodable, then the above statements are also true if we replace "uniquely decodable" by "instantaneous." Let us first prove the statements for prefix-free codes, and then we discuss the more general case of uniquely decodable codes.

Proof for Prefix-Free Codes

Prefix-free codes can be visualized as a $D$-ary tree, in which all non-leaf nodes have at most $D$ children. In the figure below, we have a binary (2-ary) prefix-free code where each "left turn" corresponds to 0 and each "right turn" corresponds to 1.

Since no codeword can be a prefix of another codeword, the following (equivalent) properties must be satisfied:

• no codeword can be a descendant of another codeword, and
• no two codewords can share a descendant in the full binary tree.

The first property is a direct consequence of being prefix-free. Essentially, it tells us that once we have assigned a node in the tree as a codeword, all of its descendants in the full binary tree are denied the possibility of being a codeword. The figure illustrates this property using the dashed circles below solid black nodes. The second property requires a bit more thought: if a tree node has codewords A and B are ancestors, then either A is a descendant of B or B is a descendant of A. The proof of this fact is left as an exercise.

We are now ready to prove the necessity condition for prefix-free codes. Let $l_{\text{max}}$ be the maximum codeword length in $l_{1},...,l_{m}$. Construct a full $D$-ary tree with depth $l_{\text{max}}$. At the lowest level, there are $D^{l_{\text{max}}}$ leaf nodes. For example, in the figure we have $D=2$ and $l_{\text{max}}=4$, which corresponds to $2^{4}=16$ leaf nodes.

Each codeword will have some descendants at the lowest level. In the figure, the codeword 01 is at level 2 and it has 4 descendants at the lowest level. In general, a D-ary codeword at level $l_{i}$ will have $D^{l_{\text{max}}-l_{i}}$ descendants at the lowest level, $l_{m}ax$. (If the codeword is itself at the lowest level, then we count that codeword as its own descendant.) Now, since no two codewords can share a descendant, we can obtain the total number of distinct descendants by simply adding them up. The resulting total must be at most equal to number of leaf nodes, which is equal to $D^{l_{\text{max}}}$.

$\sum _{i}D^{l_{\text{max}}-l_{i}}\leq D^{l_{\text{max}}}$.

Dividing both sides by $D^{l_{\text{max}}}$ gives us Kraft's inequality.

Proof for Uniquely Decodable Codes

The proof of the Kraft-McMillan Inequality for uniquely decodable codes is interesting since it starts with evaluating $K^{m}$:

$K^{m}=\left(\sum _{i=1}^{n}{\frac {1}{r^{\ell _{i}}}}\right)^{m}=\sum _{i_{1}=1}^{n}\sum _{i_{1}=1}^{n}\cdots \sum _{i_{m}=1}^{n}{\frac {1}{r^{\ell _{i_{1}}+\ell _{i_{2}}+\ldots +\ell _{i_{m}}}}}$

(2)

Let $\ell =\max \left(\ell _{1},\ell _{2},\ldots ,\ell _{n}\right)$. Thus, the minimum value of $\ell _{i_{1}}+\ell _{i_{2}}+\ldots +\ell _{i_{m}}$ is $m$, when all the codewords are 1 bit long, and the maximum is $m\ell$, when all the codewords have the maximum length. We can then write:

$K^{m}=\sum _{k=m}^{m\ell }{\frac {N_{k}}{r^{k}}}$

(3)

Where $N_{k}$ is the number of combinations of $m$ codewords that have a combined length of $k$. Note that the number of distinct codewords of length $k$ is $r^{k}$. If this code is uniquely decodable, then each sequence can represent one and only one sequence of codewords. Therefore, the number of possible combinations of codewords whose combined length is $k$ cannot be greater than $r^{k}$, or:

$N_{k}\leq r^{k}$

(4)

We can then write:

$K^{m}\leq \sum _{k=m}^{m\ell }{\frac {r^{k}}{r^{k}}}=m\ell -m+1$

(5)

Thus, we can conclude that $K\leq 1$ since if this were not true, $K^{m}$ would exceed $m\ell -m+1$ for large $m$.