Kraft Inequality

Let \(X\) be a discrete memoryless source (DMS) with an alphabet \(\{x_1, x_2, \dots, x_m\}\).
Assume that each symbol \(x_i\) is assigned a binary codeword of length \(n_i\).

Statement:

A necessary and sufficient condition for the existence of an instantaneous (prefix-free) binary code is given by the Kraft inequality:

\[ K = \sum_{i=1}^{m} 2^{-n_i} \leq 1 \]

Interpretation:

  • If the inequality holds, then there exists a prefix-free binary code with the given lengths.
  • The inequality does not guarantee:
    • That such codewords are unique
    • How to construct the codewords
    • That any code satisfying it is automatically uniquely decodable