Force inequality

from Wikipedia, the free encyclopedia

The force inequality , also known as the force-McMillan inequality , is a necessary and sufficient condition in coding theory for the existence of a uniquely decodable code for a given set of key lengths. Its implications for prefix codes and binary trees are widely used in computer science and information theory.

The force inequality was developed in 1949 by Leon G. Kraft , whereby he dealt exclusively with prefix codes in his work. Regardless of Kraft, Brockway McMillan came to identical results in 1956.

statement

Let be a - tree with a maximum of child nodes per node and leaves whose depths are.

Then:

Equality holds if is a complete tree .

proof

It is easy to see that for a tree of depth 0:

Since a node of a -ary tree has a maximum of children or is a leaf, each node distributes its value (depth ) to a maximum of children with the value , which together have a maximum value of . Is the tree incomplete, i.e. H. If one node has fewer than children, the sum even drops below 1. The inequality is violated if and only if inner nodes are used as leaves, because z. B. all nodes on a depth level can be used as code words, but at the same time even longer, deeper code words exist. Since these longer code words then have a code word as a prefix, this also violates the property of freedom from prefixes. It is of course possible and not uncommon for the tree to be unbalanced, i.e. H. a path of length exists, while in another branch there are still deeper leaves to be found.

On the other hand, it is also possible to construct “stupid” codes that satisfy the inequality but still use part of a path to a leaf as a code word.

In the context of coding theory , the lengths of the code words must satisfy the force inequality for each uniquely decodable code above the alphabet of length . Conversely, for every set of code word lengths that satisfy the force inequality, there is a clearly decodable, prefix-free code with these lengths.

Proof of infinite sequences of codeword lengths

Let be a prefix-free binary code for all if and only if

Be prefix-free binary codes with codeword lengths

. Since finite, prefix-free binary code continues to apply to all

Be The sum converges absolutely we can rearrange wlog

Induction after :

OK
have präfixfreien binary code to , representing a binary tree , and then replace each leaf of the current depth by complete binary tree of the height . That doesn't change anything about the "addability", all sheets in have depth and nothing changes to the sum, because .

Be equal to the number of leaves in . Then it is not completely possible to add length codeword def. inductive, resulting in a prefix-free binary code.

literature

  • John G. Proakis, Masoud Salehi: Digital Communications . 5th edition. McGraw Hill, 2008, ISBN 978-0-07-126378-8 , pp. 340-342 .

Individual evidence

  1. ^ Leon G. Kraft: A device for quantizing, grouping, and coding amplitude modulated pulses . Ed .: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology . Cambridge, MA 1949 ( online ).
  2. Brockway McMillan: Two inequalities implied by unique decipherability . In: IEEE Trans. Information Theory . tape 2 , no. 4 , 1956, pp. 115-116 ( online ).