Kraft’s inequality

Getting round to re-reading Information and Coding Theory- in physical form after the disappointment of the Kindle edition.

Maybe it’s because I’m six months older and wiser, but this time more determined to grasp more of the maths in the book, so came to a basic precept of coding theory – Kraft’s inequality – which states:

There is an instantaneous r-ary code C with word lengths l_1...l_q if and only if :

\sum_{i=1}^q \frac{1}{r^{l_i}} \leq 1

Let’s examine a proof of this: I found the proof in the book a bit difficult to follow, so this is why this follows the ideas in the book but in a little more detail.

So, we can imagine the space of the code words as a triangle (as shown):

code triangle

Creating an instantaneous code from code space S

The triangle S contains the complete range of available code words and the small triangle t shows that picking a non-leaf code word denies us the ability to use leaves that are dominated by the non-leaf code word (in an instantaneous code).

So, if we total levels l and picked a word at level l_x the we would lose access to r^{l_l - l_x} leaves.

Now, we know that r^l\sum_{i=1}^q\frac{1}{r^{l_i}} \leq r^l (as the sum is less than or equal to 1).

But was can also state that r^{l-l_x} < r^l\sum_{i=1}^q\frac{1}{r^{l_i}} because the sum contains the fraction – think of a 32 leaf binary code triangle where we had picked a code word from the third level, then we would have:

2^{5-3} < 2^5\sum_{i=1}^5\frac{1}{2^i}

2^2 < 2^4 + 2^3 + 2^2 + 2^1

We thus see we can keep picking code words on this basis and we will always have an instantaneous code. But we also know that an instantaneous code is a prefix code and thus for a prefix code this inequality applies:

\sum_{i=1}^qr^{l-l_i} \leq r^l

Diving both sides by r^l we get:

\sum_{i=1}^q\frac{r^{l-l_i}}{r^l} \leq 1

\sum_{i=1}^q\frac{1}{r^{l_i}} \leq 1

Related articles
About these ads

2 comments

  1. Pingback: McMillian’s inequality | cartesian product
  2. Pingback: Proof of the existence of an optimal code | cartesian product