Kraft–McMillan inequality

Kraft–McMillan inequality (Redirected from Kraft–McMillan theorem) Jump to navigation Jump to search In coding theory, the Kraft–McMillan inequality gives a necessary and sufficient condition for the existence of a prefix code[1] (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.

Kraft's inequality was published in Kraft (1949). Cependant, 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.

Contenu 1 Applications and intuitions 2 Déclaration formelle 3 Exemple: binary trees 4 Preuve 4.1 Proof for prefix codes 4.2 Proof of the general case 4.3 Alternative construction for the converse 5 Remarques 6 Références 7 See also 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, C'est, 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.[2] 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 {style d'affichage S={,s_{1},s_{2},ldots ,s_{n},}} be encoded into a uniquely decodable code over an alphabet of size {style d'affichage r} with codeword lengths {style d'affichage ell _{1},euh _{2},ldots ,euh _{n}.} Alors {somme de style d'affichage _{je=1}^{n}r ^{-euh _{je}}leqslant 1.} inversement, for a given set of natural numbers {style d'affichage ell _{1},euh _{2},ldots ,euh _{n}} satisfying the above inequality, there exists a uniquely decodable code over an alphabet of size {style d'affichage r} with those codeword lengths.

Exemple: binary trees 9, 14, 19, 67 et 76 are leaf nodes at depths of 3, 3, 3, 3 et 2, respectivement.

Any binary tree can be viewed as defining a prefix code for the leaves of the tree. Kraft's inequality states that {somme de style d'affichage _{ell in {texte{leaves}}}2^{-{texte{depth}}(aune )}leqslant 1.} Here the sum is taken over the leaves of the tree, c'est à dire. the nodes without any children. The depth is the distance to the root node. In the tree to the right, this sum is {style d'affichage {frac {1}{4}}+4la gauche({frac {1}{8}}droit)={frac {3}{4}}leqslant 1.} Proof Proof for prefix codes Example for binary tree. Red nodes represent a prefix tree. The method for calculating the number of descendant leaf nodes in the full tree is shown.

Première, let us show that the Kraft inequality holds whenever the code for {style d'affichage S} is a prefix code.

Supposer que {style d'affichage ell _{1}leqslant ell _{2}leqslant cdots leqslant ell _{n}} . Laisser {style d'affichage A} be the full {style d'affichage r} -ary tree of depth {style d'affichage ell _{n}} (Donc, every node of {style d'affichage A} at level {style d'affichage je, the first {style d'affichage ell _{je}} digits of Cj form a larger number than Ci, so the code is prefix free.

Notes ^ Cover, Thomas M.; Thomas, Joy A. (2006), "Compression des données", Éléments de la théorie de l'information (2sd éd.), John Wiley & Sons, Inc, pp. 108–109, est ce que je:10.1002/047174882X.ch5, ISBN 978-0-471-24195-9 ^ De Rooij, Steven; Forêt verte, Peter D. (2011), "LUCKINESS AND REGRET IN MINIMUM DESCRIPTION LENGTH INFERENCE", Philosophy of Statistics (1st ed.), Elsevier, p. 875, ISBN 978-0-080-93096-1 References Kraft, Leon G. (1949), A device for quantizing, grouping, and coding amplitude modulated pulses, Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology, hdl:1721.1/12390. McMillan, Brockway (1956), "Two inequalities implied by unique decipherability", IEEE Trans. Inf. La théorie, 2 (4): 115–116, est ce que je:10.1109/TIT.1956.1056818. See also Chaitin's constant Canonical Huffman code Categories: Coding theoryInequalities