# Kraft–McMillan inequality

The Kraft-McMillan inequality is general, but we'll focus on version that operates on bits.

Let encoding C consists of n symbols encoded in binary with code words having lengths:

${\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n}.}$

The Kraft-McMillan inequality states that: IF C is uniquely (unambigously) decodable, then following holds:

${\displaystyle \sum _{i=1}^{n}2^{-\ell _{i}}\leqslant 1.}$

There are few important conclusions of this:

• If you get a Kraft number strictly less than 1, that means encoding has some redundancy (that means that you are not using all the code space you could be - in essence you could give more code length to some symbols and it can still be decodable).
• If both Kraft number is equal to 1, the code is complete (new codeword cannot be added without changing the length of some other word(s))
• If inequality does not hold, the code is not uniquely decodable.

Important aditional conclusion is following one:

• if the list of lenghts of encoding fulfills K-M inequality, prefix code can be found with words having those lenghts.

That means, the search for perfect encoding (K(C) == 1), can be limited to search of a prefix code.