Desigualdade de Kraft-McMillan

Desigualdade de Kraft-McMillan (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). No entanto, 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.

Conteúdo 1 Applications and intuitions 2 Declaração formal 3 Exemplo: binary trees 4 Prova 4.1 Proof for prefix codes 4.2 Proof of the general case 4.3 Alternative construction for the converse 5 Notas 6 Referências 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, isso é, 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 {estilo de exibição S={,s_{1},s_{2},ldots ,s_{n},}} be encoded into a uniquely decodable code over an alphabet of size {estilo de exibição r} with codeword lengths {estilo de exibição ell _{1},ell _{2},ldots ,ell _{n}.} Então {soma de estilo de exibição _{i=1}^{n}^{-ell _{eu}}leqslant 1.} Por outro lado, for a given set of natural numbers {estilo de exibição ell _{1},ell _{2},ldots ,ell _{n}} satisfying the above inequality, there exists a uniquely decodable code over an alphabet of size {estilo de exibição r} with those codeword lengths.

Exemplo: binary trees 9, 14, 19, 67 e 76 are leaf nodes at depths of 3, 3, 3, 3 e 2, respectivamente.

Any binary tree can be viewed as defining a prefix code for the leaves of the tree. Kraft's inequality states that {soma de estilo de exibição _{ell in {texto{leaves}}}2^{-{texto{depth}}(bem )}leqslant 1.} Here the sum is taken over the leaves of the tree, ou seja. the nodes without any children. The depth is the distance to the root node. In the tree to the right, this sum is {estilo de exibição {fratura {1}{4}}+4deixei({fratura {1}{8}}certo)={fratura {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.

Primeiro, let us show that the Kraft inequality holds whenever the code for {estilo de exibição S} is a prefix code.

Suponha que {estilo de exibição ell _{1}leqslant ell _{2}leqslant cdots leqslant ell _{n}} . Deixar {estilo de exibição A} be the full {estilo de exibição r} -ary tree of depth {estilo de exibição ell _{n}} (portanto, every node of {estilo de exibição A} at level {estilo de exibição eu, the first {estilo de exibição ell _{eu}} digits of Cj form a larger number than Ci, so the code is prefix free.

Notes ^ Cover, Thomas M.; Thomas, Joy A. (2006), "Compressão de dados", Elementos da Teoria da Informação (2ª edição), John Wiley & Sons, Inc, pp. 108-109, doi:10.1002/047174882X.ch5, ISBN 978-0-471-24195-9 ^ De Rooij, Steven; Floresta verde, 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. Teoria, 2 (4): 115-116, doi:10.1109/TIT.1956.1056818. See also Chaitin's constant Canonical Huffman code Categories: Coding theoryInequalities