Disuguaglianza di Kraft-McMillan

Disuguaglianza di 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). Tuttavia, 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.

Contenuti 1 Applications and intuitions 2 Dichiarazione formale 3 Esempio: 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 Appunti 6 Riferimenti 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, questo è, 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 {stile di visualizzazione S={,S_{1},S_{2},ldot ,S_{n},}} be encoded into a uniquely decodable code over an alphabet of size {stile di visualizzazione r} with codeword lengths {stile di visualizzazione ell _{1},ell _{2},ldot ,ell _{n}.} Quindi {somma dello stile di visualizzazione _{io=1}^{n}r^{-ell _{io}}leqslant 1.} al contrario, for a given set of natural numbers {stile di visualizzazione ell _{1},ell _{2},ldot ,ell _{n}} satisfying the above inequality, there exists a uniquely decodable code over an alphabet of size {stile di visualizzazione r} with those codeword lengths.

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

Any binary tree can be viewed as defining a prefix code for the leaves of the tree. Kraft's inequality states that {somma dello stile di visualizzazione _{ell in {testo{leaves}}}2^{-{testo{depth}}(ell )}leqslant 1.} Here the sum is taken over the leaves of the tree, cioè. the nodes without any children. The depth is the distance to the root node. In the tree to the right, this sum is {stile di visualizzazione {frac {1}{4}}+4sinistra({frac {1}{8}}Giusto)={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.

Primo, let us show that the Kraft inequality holds whenever the code for {stile di visualizzazione S} is a prefix code.

Supporre che {stile di visualizzazione ell _{1}leqslant ell _{2}leqslant cdots leqslant ell _{n}} . Permettere {stile di visualizzazione A} be the full {stile di visualizzazione r} -ary tree of depth {stile di visualizzazione ell _{n}} (così, every node of {stile di visualizzazione A} at level {stile di visualizzazione io, the first {stile di visualizzazione ell _{io}} digits of Cj form a larger number than Ci, so the code is prefix free.

Notes ^ Cover, Thomas M.; Tommaso, Joy A. (2006), "Compressione dati", Elementi di teoria dell'informazione (2nd ed.), John Wiley & Sons, Inc, pp. 108–109, doi:10.1002/047174882X.ch5, ISBN 978-0-471-24195-9 ^ De Rooij, Stefano; Foresta verde, Pietro D. (2011), "LUCKINESS AND REGRET IN MINIMUM DESCRIPTION LENGTH INFERENCE", Philosophy of Statistics (1st ed.), Altro, 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

Se vuoi conoscere altri articoli simili a Disuguaglianza di Kraft-McMillan puoi visitare la categoria Coding theory.

lascia un commento

L'indirizzo email non verrà pubblicato.

Vai su

Utilizziamo cookie propri e di terze parti per migliorare l'esperienza dell'utente Maggiori informazioni