Kraft Inequality

Source: The Art of Doing Science and Engineering: Learning to learn

The Kraft inequality gives a limit on the lengths lil_i of each symbol in the alphabet.

K=i=1q12li1K = \sum_{i=1}^q \frac{1}{2^{l_i}} \leq 1

Proof

by induction

base case: trivially true for q = 1 and q = 2

  • K=1K = 1 for q=1q = 1
  • K=1K = 1 for q=2q = 2

Induction:

true for KK' and KK''

we join these trees, increasing length of each node by one, adding a factor of two to the denominator.

K2+K21\frac{K'}{2} + \frac{K''}{2} \leq 1

Backlinks