2
$\begingroup$

Li and Vitanyi define a complete code as a uniquely decodable code to which no codeword can be added while keeping it uniquely decodable. They claim that this is easily seen to be equivalent to equality holding in the Kraft inequality. I can see that equality in the Kraft inequality is clearly a necessary condition, and the other direction is obvious to me for prefix codes, but otherwise it does not seem so easy to me.

$\endgroup$
2
  • $\begingroup$ It seems like you need McMillan's theorem (which says that the Kraft inequality also holds for uniquely decodable codes; this is why sometimes this is called the Kraft-McMillan inequality instead). Cover and Thomas have a proof of McMillan's theorem, and the pertinent wikipedia page also gives most of the same (see the section on "proof of the general case." The only thing they miss is when the input alphabet is infinite, which is not too hard to get from the finite alphabet case by truncating the code and then taking a limit). $\endgroup$ Commented Jan 23, 2023 at 20:45
  • $\begingroup$ I know that. Perhaps I'm not seeing something, but I still don't see where this gets me. Just because there is "space" for a codeword which does not start the same way as any other codeword doesn't seem to mean you can just add it to the uniquely decodable code. $\endgroup$ Commented Jan 24, 2023 at 3:00

1 Answer 1

1
$\begingroup$

A late but detailed answer to your question. In this answer, "code" means "uniquely decodable code".

Short answer. If you consider only finite codes (prefix or not) or even regular codes, then equality in the Kraft inequality implies maximality. It is no longer true for non-regular codes, although it holds for a large family of non-regular codes, the thin codes. See details below.

Long answer. This answer is entirely based on [1], the bible on this topic. Let me first slightly modify your terminology. A code is maximal if it is not properly contained in another code. As you will see below, the term complete is used for a related, but different property. However, for finite codes, maximal and complete are two equivalent notions.

Notation. Let $A$ be an alphabet. The length of a word $u$ is denoted by $|u|$. If $a$ is a letter of $A$, the number of occurrences of $a$ in $u$ is denoted by $|u|_a$. Thus $|u| = \sum_{a \in A} |u|_a$.

Definition 1. A Bernoulli distribution on $A^*$ is a monoid morphism $\pi: A^* \to [0,1]$ such that $\sum_{a \in A} \pi(a) = 1$. It is positive if $\pi(a) > 0$ for all $a \in A$. If $A$ is a $k$-letter alphabet, the uniform distribution is defined by $\pi(a) = k^{-1}$ for each letter $a$, and hence by $\pi(x) = k^{-|x|}$ for each word $x$.

The first result is true without any assumption on the code, which can be finite or infinite.

Proposition 1. If $X$ is a code over $A$, then $\pi(X) \leqslant 1$ for every Bernoulli distribution $\pi$ over $A$.

Corollary (Kraft). If $X$ is a code over a $k$-letter alphabet, then $$ \sum_{x \in X} k^{-|x|} \leqslant 1 $$ The following result gives a first partial answer to your question:

Proposition 2. Let $X$ be a code over $A$. If there exists a positive Bernoulli distribution $\pi$ on $A^*$ such that $\pi(X) = 1$, then $X$ is maximal.

Example 1. Let $\pi:\{a, b\}^* \to \Bbb Z$ be the monoid morphism defined by $\pi(u) = |u|_a - |u|_b$. Then $\pi^{-1}(0)$ is a submonoid of $A^*$. The base of this submonoid is a prefix code denoted by $D$, called the Dyck code. Let $\pi$ is a Bernoulli distribution $\pi$ on $\{a, b\}^*$. Setting $p = \pi(a)$ and $q = \pi(b)$, one can show that $\pi(D) = 1 - |p-q|$. In particular, if $p = q = 1/2$, then $\pi(D) = 1$. It follows from Proposition 2 that $D$ is maximal, but it is interesting to note that $\pi(D) < 1$ for every non-uniform distribution.

A few definitions are required to give a more detailed answer to your question.

Definition. A subset $X$ of $A^*$ is dense if every word of $A^*$ is a factor of some word of $X$. A non-dense set is called thin. A code $C$ of $A^*$ is complete if $C^*$ is dense, that is, if every word of $A^*$ is a factor of some word of $C^*$.

Thin codes form a rather large class of codes, which includes in particular all regular codes (and hence, all finite ones).

Proposition 3. Every regular code is thin.

The converse is not true. The code $X = \{a^nb^n \mid n > 0\}$ is thin (for example, $ba$ is not a factor of $X$), but is not regular.

The next result summarizes the connections between maximal and complete codes.

Theorem 1.

  1. Every maximal code is complete.
  2. Every thin and complete code is maximal.
  3. A code is complete if and only if it is dense or maximal.

The following theorem shows that, for thin codes, your question admits a positive answer.

Theorem 2. Let $X$ be a thin code. The following conditions are equivalent:

  1. $X$ is a maximal code.
  2. There exists a positive Bernoulli distribution $\pi$ with $\pi(X) = 1$.
  3. For each positive Bernoulli distribution $\pi$, one has $\pi(X) = 1$.
  4. $X$ is complete.

Let me finish with two examples, which explain why it might be difficult to go beyond Theorem 2.

Example 2. The dense code $$\bigcup_{n \geqslant 0}a^nb\{a,b\}^n$$ also satisfies the four conditions of Theorem 2.

Example 3. The Dyck code $D_2$ over two letters is defined as follows. Let $F_2$ be the free group on two letters $a$ and $b$ and let $\delta: \{ a,b, \bar a, \bar b\} \to F_2$ be the monoid morphism defined by $\delta(a) = a$, $\delta(b) = b$, $\delta(\bar a) = a^{-1}$ and $\delta(\bar b) = b^{-1}$. Then $\delta^{-1}(1)$ is a submonoid of $\{ a,b, \bar a, \bar b\}^*$ whose basis is a prefix code, denoted by $D_2$. One can show that $D_2$ is a dense maximal code. However, one has $\pi(D) < 1$ for every Bernouilli distribution and in particular $\pi(D) = 1/3$ for the uniform distribution.

[1] J. Berstel, D. Perrin and C. Reutenauer, Codes and automata. Encyclopedia of Mathematics and its Applications, 129. Cambridge University Press, Cambridge, 2010. xiv+619 pp. ISBN: 978-0-521-88831-8

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .