克拉夫特不等式

克拉夫特不等式对码字限制长度以保证前缀编码的可能性。这个不等式说明码字长度指数的倒数的分布和概率质量函数很相似。克拉夫特不等式can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive.

如果克拉夫特不等式中严格成立，相应的编码有冗余（redundancy）。

如果克拉夫特不等式中等式成立，相应的编码被称作complete code。

如果克拉夫特不等式不成立，相应的编码不是唯一可解编码（uniquely decipherable）。

定义

设符号表中的原始符号为 （公式略）

在大小为 r 的字符集上编码为唯一可解编码的码字长度为 ℓ ₁,ℓ ₂,…,ℓ ₙ.

则 （公式略）

反之, 给定一个满足上述不等式的自然数集合 ℓ ₁,ℓ ₂,…,ℓ ₙ, 则在大小为 r 字符集上，存在一组唯一可解编码符合相应的码字长度。

In coding theory, the Kraft–McMillan inequality gives a necessary and sufficient condition for the existence of a prefix code (in Leon G. Kraft's version) or a uniquely decodable code (in Brockway McMillan's version) for a given set of codeword lengths. Its applications to prefix codes and trees often find use in computer science and information theory. The prefix code can contain either finitely many or infinitely many codewords.

Kraft's inequality was published in Kraft (1949). However, Kraft's paper discusses only prefix codes, and attributes the analysis leading to the inequality to Raymond Redheffer. The result was independently discovered in McMillan (1956). McMillan proves the result for the general case of uniquely decodable codes, and attributes the version for prefix codes to a spoken observation in 1955 by Joseph Leo Doob.

Applications and intuitions

Kraft's inequality limits the lengths of codewords in a prefix code: if one takes an exponential of the length of each valid codeword, the resulting set of values must look like a probability mass function, that is, it must have total measure less than or equal to one. Kraft's inequality can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive. Among the useful properties following from the inequality are the following statements:

If Kraft's inequality holds with strict inequality, the code has some redundancy.

If Kraft's inequality holds with equality, the code in question is a complete code.

If Kraft's inequality does not hold, the code is not uniquely decodable.

For every uniquely decodable code, there exists a prefix code with the same length distribution.

Formal statement

Let each source symbol from the alphabet （公式略）

be encoded into a uniquely decodable code over an alphabet of size r with codeword lengths ℓ ₁,ℓ ₂,…,ℓ ₙ.

Then （公式略）

Conversely, for a given set of natural numbers ℓ ₁,ℓ ₂,…,ℓ ₙ satisfying the above inequality, there exists a uniquely decodable code over an alphabet of size r with those codeword lengths.

Example: binary trees

Any binary tree can be viewed as defining a prefix code for the leaves of the tree. Kraft's inequality states that （公式略）

Here the sum is taken over the leaves of the tree, i.e. the nodes without any children. The depth is the distance to the root node. In the tree to the right, this sum is （公式略）

Proof

Proof for prefix codes

First, let us show that the Kraft inequality holds whenever the code for S is a prefix code.

Suppose that （公式略）. Let A be the full r -ary tree of depth ℓ ₙ (thus, every node of A at level <ℓ ₙ has r children, while the nodes at level ℓ ₙ are leaves). Every word of length （公式略） over an r -ary alphabet corresponds to a node in this tree at depth ℓ. The i th word in the prefix code corresponds to a node vᵢ; let Aᵢ be the set of all leaf nodes (i.e. of nodes at depth ℓ ₙ) in the subtree of A rooted at vᵢ. That subtree being of height ℓ ₙ-ℓ ᵢ, we have |Aᵢ|=r^ℓ ₙ-ℓ ᵢ.

Since the code is a prefix code, those subtrees cannot share any leaves, which means that Aᵢ∩ Aⱼ=∅, i≠ j.

Thus, given that the total number of nodes at depth ℓ ₙ r^ℓ ₙ, we have （公式略）

from which the result follows.

Conversely, given any ordered sequence of n natural numbers, （公式略）

satisfying the Kraft inequality, one can construct a prefix code with codeword lengths equal to each ℓ ᵢ by choosing a word of length ℓ ᵢ arbitrarily, then ruling out all words of greater length that have it as a prefix. There again, we shall interpret this in terms of leaf nodes of an r -ary tree of depth ℓ ₙ. First choose any node from the full tree at depth ℓ ₁; it corresponds to the first word of our new code. Since we are building a prefix code, all the descendants of this node (i.e., all words that have this first word as a prefix) become unsuitable for inclusion in the code. We consider the descendants at depth ℓ ₙ (i.e., the leaf nodes among the descendants); there are r^ℓ ₙ-ℓ ₁ such descendant nodes that are removed from consideration. The next iteration picks a (surviving) node at depth ℓ ₂ and removes r^ℓ ₙ-ℓ ₂ further leaf nodes, and so on. After n iterations, we have removed a total of ∑ ᵢ₌₁ⁿr^ℓ ₙ-ℓ ᵢ

nodes. The question is whether we need to remove more leaf nodes than we actually have available — r^ℓ ₙ in all — in the process of building the code. Since the Kraft inequality holds, we have indeed （公式略）

Generalizations

The following generalization is found in.

The previous theorem is the special case when （公式略）.There is a generalization to quantum code.