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.