<p>Maximal implies sharp, even for uniquely decodable codes.</p>
<p><strong>Proof:</strong> 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.</p>
<p>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.</p>
<p><strong>Case 1:</strong> the greatest common divisors of the lengths of the codewords is 1.<br />
Choose <span class="math-container">$m$</span> large. We have <span class="math-container">$r^m$</span> possible sequences of length <span class="math-container">$m$</span>, and they can all appear as interior sequences in concatenations of codewords. We would like to make them line up, so as to find <span class="math-container">$r^m$</span> concatenations of codewords where each of these sequences appears starting with the <span class="math-container">$C$</span>'th letter. By number theory (<a href="https://en.wikipedia.org/wiki/Coin_problem" rel="nofollow noreferrer">see the <em>Frobenius coin problem</em></a>), there is some constant <span class="math-container">$C$</span> so that we can arrange this independent of <span class="math-container">$m$</span>. Let <span class="math-container">$\ell$</span> be the maximum codeword length. We thus have <span class="math-container">$r^m$</span> different sequences of length at most <span class="math-container">$m+C+\ell$</span>, none of which is a prefix of another one, and which are all in the code. We can use these <span class="math-container">$r^m$</span> sequences of codewords to transmit information at rate at least <span class="math-container">$$\frac{m \log_2 r}{m+C+\ell}$$</span> bits per symbol.
Since <span class="math-container">$C+\ell$</span> is fixed, then for any <span class="math-container">$\alpha &lt; 1$</span>, we can find <span class="math-container">$m$</span> large enough so that <span class="math-container">$$\frac{m \log_2 r}{m+C+\ell} &gt; {\alpha} \log r,$$</span> showing that the information transmission rate for our original codewords is <span class="math-container">$\log r$</span>. However, if the Kraft inequality is not sharp, then there is an <span class="math-container">$\alpha&lt;1$</span> such that
<span class="math-container">$$
\sum_{i=1}^n \frac{1}{r^{\alpha \ell_i}} = 1\,.
$$</span>
And one can show that if
this equation holds,
then the code can only transmit information at a rate of <span class="math-container">$\alpha \log r$</span> 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.)</p>
<p><strong>Case 2:</strong> the greatest common divisors of the lengths of the codewords is <span class="math-container">$g&gt;1$</span>.<br />
Consider the new code formed by replacing every <span class="math-container">$g$</span> letters of the original code with a new letter in an alphabet of size <span class="math-container">$r^g$</span>. We are now in case 1, so the Kraft-McMillan inequality holds with equality.
The codeword lengths in our new code are <span class="math-container">$\ell_i/g$</span>, so we have
<span class="math-container">$$
1 = \sum_i (r^g)^{\ell_i/g} = \sum_i r^{\ell_i},
$$</span>
proving the theorem.</p>

CC BY-SA 4.0
2022-04-21T10:39:16.603Z
2022-04-22T22:34:12.887Z
2022-04-22T22:34:12.887Z
Peter Shor 
<p>This question is about the Kraft-McMillan inequality:</p>
<p>If <span class="math-container">$w_1,\ldots,w_n$</span> are words of lengths <span class="math-container">$l_1,\ldots,l_n$</span> from an alphabet with <span class="math-container">$r$</span> letters, which form a uniquely decodable code, then
<span class="math-container">$$ \sum_{i=1}^n \frac{1}{r^{l_i}} \leq 1. $$</span></p>
<p>(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.)</p>
<p>Let's say a uniquely decodable set of words is <em>maximal</em> 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 <em>sharp</em> if it attains equality in the McMillan inequality, i.e.
<span class="math-container">$$ \sum_{i=1}^n \frac{1}{r^{l_i}} = 1. $$</span></p>
<p><strong>Question.</strong> It is obvious that sharp implies maximal. What about the converse: is every maximal uniquely decodable set sharp?</p>
<p>I know how to prove it if we're talking about &quot;prefix-free&quot; (Kraft version) instead of uniquely decodable, but I don't see how to prove this version, if it's even true.</p>

<co.combinatorics><it.information-theory><coding-theory>
Maximal uniquely decodable codes
aiz89
# Maximal uniquely decodable codes

(Asked by: username_0 on 2022-04-20)

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.

**Tags:** co.combinatorics, it.information-theory, coding-theory


---

## 1 answers

### Answer by username_1 on 2022-04-21. Score: 5 | Accepted answer

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*](https://en.wikipedia.org/wiki/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.


---

