Talk:Kraft–McMillan inequality/Archive 1

This is an archive of past discussions about Kraft–McMillan inequality. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Formulation

This page contains the following itemized list:

If Kraft's inequality holds with strict inequality, the code has some redundancy.
If Kraft's inequality holds with strict equality, the code in question is a complete code.
If Kraft's inequality does not hold, the code is not uniquely decodable.

I suggest changing it to the following:

If Kraft's inequality holds with strict inequality, the code is incomplete and therefore has some redundancy.
If Kraft's inequality holds with strict equality, the code in question is a complete code. It may or may not be redundant, however, depending on whether or not the code is optimal for the source in the sense of Shannon's source-coding theorem.
If Kraft's inequality does not hold, the code is not uniquely decodable.

To put it more concisely completeness is necessary but not sufficient for a code to be non-redundant.

I am posting this here rather than changing the page itself because I'm a Wikipedia novice (I just created my account a few minutes ago) and I don't consider myself an expert in Information Theory, though I do have some knowledge of it.

 - - Byron Dom ( Byrondom (talk) 21:19, 8 July 2010 (UTC) )

Definition not correct

The first paragraph, "...gives a sufficient condition for the existence of a prefix code[1] and necessary condition for the existence of a uniquely decodable code for a given set of codeword lengths": Kraft's inequality is a necessary and sufficient condition for existence of a prefix code, and since a prefix code is a uniquely decodable code, it is a sufficient (and necessary?) condition for existence of a uniquely decodable code too. Cover & Thomas (citation 1) provides the proofs.Lordfkiller (talk) 11:19, 28 March 2015 (UTC)

Agree! Even if you do not know anything about Kraft's inequality, but you know that every prefix code is a uniquely decodable code aswell, then you must know that if a condition is sufficient for the existance of a prefix code then it is also sufficient for the existance of a uniquely decodable code, not necessary!