Math and science::INF ML AI

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