3
$\begingroup$

This question is about the Kraft-McMillan inequality:

If $w_1,\ldots,w_n$ are words of lengths $l_1,\ldots,l_n$ from an alphabet with $r$ letters, which form a uniquely decodable code, then $$ \sum_{i=1}^n \frac{1}{r^{l_i}} \leq 1. $$

(A set of words is uniquely decodable if any word in the alphabet can be broken into words from the set in at most one way.)

Let's say a uniquely decodable set of words is maximal if it is not possible to add another word to this set and still have it uniquely decodable. Also, let's say a uniquely decodable set of words is sharp if it attains equality in the McMillan inequality, i.e. $$ \sum_{i=1}^n \frac{1}{r^{l_i}} = 1. $$

Question. It is obvious that sharp implies maximal. What about the converse: is every maximal uniquely decodable set sharp?

I know how to prove it if we're talking about "prefix-free" (Kraft version) instead of uniquely decodable, but I don't see how to prove this version, if it's even true.

$\endgroup$

1 Answer 1

5
$\begingroup$

Maximal implies sharp, even for uniquely decodable codes.

Proof: If there is some sequence of letters which will never appear in the middle of a concatenation of codewords, then we can add this sequence as a codeword, and we're done.

So let us prove the theorem by contradiction. Let us assume that every codeword can appear in the middle of a concatenation of codewords, and show Kraft-McMillan holds with equality. We will break the theorem into two cases.

Case 1: the greatest common divisors of the lengths of the codewords is 1.
Choose $m$ large. We have $r^m$ possible sequences of length $m$, and they can all appear as interior sequences in concatenations of codewords. We would like to make them line up, so as to find $r^m$ concatenations of codewords where each of these sequences appears starting with the $C$'th letter. By number theory (see the Frobenius coin problem), there is some constant $C$ so that we can arrange this independent of $m$. Let $\ell$ be the maximum codeword length. We thus have $r^m$ different sequences of length at most $m+C+\ell$, none of which is a prefix of another one, and which are all in the code. We can use these $r^m$ sequences of codewords to transmit information at rate at least $$\frac{m \log_2 r}{m+C+\ell}$$ bits per symbol. Since $C+\ell$ is fixed, then for any $\alpha < 1$, we can find $m$ large enough so that $$\frac{m \log_2 r}{m+C+\ell} > {\alpha} \log r,$$ showing that the information transmission rate for our original codewords is $\log r$. However, if the Kraft inequality is not sharp, then there is an $\alpha<1$ such that $$ \sum_{i=1}^n \frac{1}{r^{\alpha \ell_i}} = 1\,. $$ And one can show that if this equation holds, then the code can only transmit information at a rate of $\alpha \log r$ bits per symbol. (It's possible to check this with calculus, although if you try to derive it with calculus the equations get really ugly.)

Case 2: the greatest common divisors of the lengths of the codewords is $g>1$.
Consider the new code formed by replacing every $g$ letters of the original code with a new letter in an alphabet of size $r^g$. We are now in case 1, so the Kraft-McMillan inequality holds with equality. The codeword lengths in our new code are $\ell_i/g$, so we have $$ 1 = \sum_i (r^g)^{\ell_i/g} = \sum_i r^{\ell_i}, $$ proving the theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.