The Kraft and McMillan Inequalities for Infinite Codes

Question

I have a copy of the Jones and Jones Information and Coding Theory book. It states the Kraft inequality for instantaneously decodable codes and the McMillan inequality for uniquely decodable codes, both involving codes with a finite source alphabet. The proofs involve the maximum codeword length, which will not exist for infinite codes. Do these results hold for infinite codes? Does anyone know of a textbook with these results for infinite codes?

Edit: Do the Kraft and McMillan theorems hold for infinite codes (codes with an infinite source alphabet)?

Answer 1

You can find a proof of the Kraft–McMillan inequalities in [1, Theorem 2.4.12, p. 75].

[1] J. Berstel, D. Perrin, 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

EDIT. You may prefer reference [2], in which Kraft–McMillan inequality is stated and proved on page 12, Formula (1.4).

[2] M/ P. Béal, J. Berstel, B. H. Marcus, D. Perrin, C. Reutenauer, P. Siegel, Variable-length codes and finite automata. Selected topics in information and coding theory, 505--584, Ser. Coding Theory Cryptol., 7, World Sci. Publ., Hackensack, NJ, 2010.

Answer 2

First note that the cardinality of $\mathbb{N}\times \mathbb{N}$ is the same as that of $\mathbb{N}$ since we can use the zigzag mapping whose beginning is given by the array below:

\begin{array}{c|ccccccc} & 1 & 2 & 3 & 4 & 5 & \\ \hline 1& 1 & 2 & 6 & 7 & 15 & \\ 2& 3 & 5 & 8 & 14 & & \\ 3& 4 & 9 & 13 & & & \\ 4& 10 & 12 & & & & \\ 5& 11 & & & & & \\ \vdots & &&&& \end{array} Therefore it is enough to talk about encoding natural numbers instead of encoding sequences of natural numbers.

There are a number of source codes for integers, the most efficient are Elias' $\gamma$ and $\delta$ codes, the most straightforward but least efficient is the unary code. All these codes are prefix codes and obey the Kraft inequality.

$\textrm{Unary}(n)=1^n 0$

$\textrm{Binary}_k(n)=k~\textrm{bit representation of } n$

Codeword length of the unary code grows too fast for practical use but still satisfies Kraft inequality.

The Golomb-Rice code(word) for any $k\geq 0,$ and any $n$ is given by

$$\textrm{GR}_k(n)=\textrm{unary}(q)\cdot \textrm{binary}_k(n-q2^k) $$ where $q=\lfloor n/2^k \rfloor,$ where $\cdot$ is concatenation. Here are some examples that also include the Elias codes: