McMillian’s inequality

Standard

Kraft’s inequality states that: There is an instantaneous r-ary code C with word lengths l_1...l_q if and only if :sigma

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

But what of codes that are merely uniquely decodable, and not necessarily instantaneous?

There number is given to us by McMillian’s inequality and the surprising thing is that, despite the looser bound this is:

There is a uniquely decodable 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

And here’s a proof (again drawn from Information and Coding Theory):

We have a code C with word lengths l_1 ... l_q and we define:

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

Additionally we say that x = max(l_1 ... l_q) and y = min(l_1 ... l_q)

Let us now consider K^n or (\sum_{i=1}^q \frac{1}{r^{l_i}})^n where n \geq 1.

This is \sum\sum...\sum \frac{1}{r^{l_i}} and is the sum of a series of products of the form:

\frac{1}{r^{l_1}}\times\frac{1}{r^{l_2}}...\times\frac{1}{r^{l_q}}

(I found this a bit difficult to follow at first, but imagine we had (\frac{1}{A} + \frac{1}{B})(\frac{1}{C} + \frac{1}{D})(\frac{1}{E} + \frac{1}{F}), then we would could expand this as:

(\frac{1}{A}\times\frac{1}{C} + \frac{1}{A}\times\frac{1}{D} + \frac{1}{B}\times\frac{1}{C} + \frac{1}{B}\times\frac{1}{D})(\frac{1}{E} + \frac{1}{F})

\frac{1}{A}\times\frac{1}{C}\times\frac{1}{E} +\frac{1}{A}\times\frac{1}{C}\times\frac{1}{F} + \frac{1}{A}\times\frac{1}{D}\times\frac{1}{E} +\frac{1}{A}\times\frac{1}{D}\times\frac{1}{F} + \frac{1}{B}\times\frac{1}{C} \times\frac{1}{E}+ \frac{1}{B}\times\frac{1}{C}\times\frac{1}{F}+\frac{1}{B}\times\frac{1}{D}\times\frac{1}{E}+\frac{1}{B}\times\frac{1}{D}\times\frac{1}{F}

And we can also write:

\frac{1}{r^{l_1}}\times\frac{1}{r^{l_2}}...\times\frac{1}{r^{l_q}} = \frac{1}{r^j} where j = l_1 + l_2 +...+l_q.

Now yn \leq j \leq xn since y \leq l_i \leq x for all i .

Now, here’s the fancy bit (at least for me!)…

This means we can rewrite K^n as \sum^{xn}_{j=yn}\frac{N_{j,n}}{r^j}

The upper and lower bounds for j follow from the inequalities above (we could sum over a wider range but then the coefficient N_{j,n} would be zero beyond these bounds. And what is this coefficient?

N_{j,n} is the number of ways of writing any given j (or, alternatively, the number of different code word sequences whose total lengths sum to j ).

Let’s take a simple example again – we have a binary code C with code words 0,01,011 (plainly not instantaneous as 01 is a prefix of 011 ).

Here K = \sum_{i=1}^q \frac{1}{r^{l_i}} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} = \frac{7}{8}

But what if we look at K^2?

Then we have:

\frac{1}{2}\times\frac{1}{2} + \frac{1}{2}\times\frac{1}{4} + \frac{1}{2}\times\frac{1}{8} +\frac{1}{4}\times\frac{1}{2} + \frac{1}{4}\times\frac{1}{4} + \frac{1}{4}\times\frac{1}{8} + \frac{1}{8}\times\frac{1}{2} + \frac{1}{8}\times\frac{1}{4} + \frac{1}{8}\times\frac{1}{8}

Writing this out in the form above we then have – and you can see the coefficients:

\frac{1}{2^2} + \frac{2}{2^3} + \frac{3}{2^4} + \frac{2}{2^5} + \frac{1}{2^6}

The coefficient N_{j,n} can never be greater than r^j (as it can never be greater than the number of possible ways to arrange the code), so \frac{N_{j,n}}{r^j} \leq 1 .

We also know that K^n is a sum of xn + 1 - yn terms, so:

K^n \leq(x - y)n + 1.

As n increases, if K > 1 then the left hand side increases exponentially while the right (where x and y are independent of n) increases only linearly, hence K \leq 1.

I am sure this will be one of the less read postings on the blog (congratulations if you got this far), but if it helps just one person get a better undestanding of McMillan’s inequality then it has been worth it!

2 thoughts on “McMillian’s inequality

  1. Pingback: Proof of the existence of an optimal code | cartesian product

  2. Pingback: Two different ways to calculate r-ary Huffman Code | cartesian product

Comments are closed.