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.

See also