McMillan's Theorem

Every Decipherable code satisfies Kraft’s inequality.

Proof

Let be a decipherable code with word lengths and Let

where is the number of ways of choosing codewords with total length .

decipherable (because any word of length in has at most one preimage under and there is such words) Then

Taking we find:

Corollary

A Decipherable code with prescribed word lengths exists if and only if there exists a Prefix-Free Code with the same word lengths.