Kraftinegyenltlenség

Kraftinegyenltlenség is a fundamental result in information theory that gives a bound on the possible lengths of codewords for uniquely decodable codes over a D-ary alphabet. It is commonly referred to as the Kraft–McMillan inequality, named after Reinhold Kraft and Robert McMillan.

Statement. Let a code over an alphabet with size D (D ≥ 2) have codeword lengths l1, l2, ..., where each li is a positive integer. Then the Kraft–McMillan inequality states that the sum of D raised to the negative lengths does not exceed 1: sum_i D^{-li} ≤ 1. In the special case of prefix (instantaneous) codes, this inequality is not only necessary but also sufficient: there exists a prefix code with the given lengths if and only if sum_i D^{-li} ≤ 1. If the code is complete (no more codewords can be added without violating the prefix property), the sum equals 1.

Consequences and usage. The inequality provides a necessary condition for the existence of a uniquely decodable or prefix code with specified lengths and serves as a constructive criterion in code design. It is used to bound achievable average codeword lengths and to justify optimal coding schemes, such as Huffman coding, which aim to minimize expected length under the Kraft constraint.

History. The result is attributed to Kraft and McMillan, who established the inequality independently in the 1950s. It applies to arbitrary D-ary alphabets and underpins much of source coding and data compression theory.