# Kraft–McMillan inequality

From WikiCoder

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:

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

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.