Show Question
Kraft inequality

For any uniquely decodable code C(X) over the binary alphabet {0, 1} the codeword lengths satisfy:

$\sum_{i=1}^{I} 2^{-l_i} \leq 1 \text{, where } I = |A_x|$

If a uniquely decodable code satisfies the Kraft inequality with equality, then it is called a complete code.

The Kraft inequality might be more accurately referred to as the Kraft-McMillan inequality: Kraft proved that if a set of codeword lengths satisfies the inequality, then a prefix code using these lengths must exist. McMillian (1956) proved that that unique decodeability implies that the inequality holds.

### Notation background

A binary symbol code $$C$$ for an ensemble $$X$$ is a mapping from the range of $$x$$, $$A_x = \{a_1, ..., a_n\}$$, to $$\{0, 1\}^+$$. $$c(x)$$ denotes the codeword corresponding to $$x$$ and $$l(x)$$ will denote its length, with shorthand $$l_i = l(a_i)$$.

The extended code $$C^+$$ is a mapping from $$A_x^+$$ to $$\{0,1\}^+$$ obtained by concatenation:

$c^+(x_1x_2...x_N) = c(x_1)c(x_2)...c(x_N)$

A code $$C(X)$$ is said to be uniquely decodable if, under the extended code $$C^+$$, no two distinct strings have the same encoding. So:

$\forall x,y \in A_x^+, x \neq y \implies c^+(x) \neq c^+(y)$

or equivalently:

$\forall x,y \in A_x^+, c^+(x) = c^+(y) \implies x = y$