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 \]