Talk:Kraft–McMillan inequality/Archive 1

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!