Kraft Inequality

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

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

Proof

by induction

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

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

Induction:

true for $K'$ and $K''$

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

---

Backlinks

• Comma Codes