Desigualdad de Kraft-McMillan

En la teoría de la codificación , la desigualdad de Kraft-McMillan proporciona una condición necesaria y suficiente para la existencia de códigos separables y prefijos que tienen un conjunto determinado de longitudes de palabras clave.

Definiciones preliminares

Sean dados dos conjuntos finitos arbitrarios , que se denominan, respectivamente, alfabeto codificado y alfabeto codificado . Sus elementos se denominan caracteres , y las cadenas (secuencias de longitud finita) de caracteres se denominan palabras . La longitud de una palabra es el número de caracteres que la componen.

Como alfabeto de codificación, a menudo se considera un conjunto: el llamado alfabeto binario o binario. $\{0,1\}$

Un esquema de codificación alfabética (o simplemente código (alfabético) ) es cualquier mapeo de los caracteres del alfabeto codificado en palabras del alfabeto de codificación, que se denominan palabras de código . Usando el esquema de codificación, cada palabra del alfabeto codificado se puede asociar con su código , la concatenación de palabras de código correspondientes a cada carácter de esta palabra.

Un código se denomina separable (o únicamente decodificable ) si no se pueden asociar dos palabras del alfabeto codificado con el mismo código.

Un código de prefijo es un código alfabético en el que ninguna de las palabras del código es un prefijo de ninguna otra palabra del código. Cualquier código de prefijo es separable.

Redacción

Teorema de Macmillan (1956) .

Se dan los alfabetos codificados y codificadores que consisten en y símbolos, respectivamente, y se dan las longitudes deseadas de las palabras de código: . Entonces, una condición necesaria y suficiente para la existencia de códigos separables y prefijos con un conjunto dado de longitudes de palabras clave es el cumplimiento de la desigualdad: $norte$ $d$ ${\displaystyle \ell_{1},\ell_{2},\ldots,\ell_{n))$

\sum _{i=1}^{n}d^{\,-\ell _{i}}\leqslant 1.

Esta desigualdad se conoce como desigualdad de Craft-MacMillan . Fue deducida por primera vez por Leon Kraft en su tesis de maestría en 1949 [1] , pero consideró solo los códigos de prefijo, por lo que cuando se analizan los códigos de prefijo, esta desigualdad a menudo se denomina simplemente desigualdad de Kraft . En 1956, Brockway Macmillan demostró la necesidad y suficiencia de esta desigualdad para una clase más general de códigos, los códigos separables. [2]

Ejemplo

Árboles binarios

Cualquier árbol binario arraigado puede verse como una descripción gráfica de un código de prefijo sobre un alfabeto binario: los caracteres del alfabeto codificado corresponden a las hojas del árbol, y la ruta en el árbol desde la raíz hasta la hoja especifica su código ( el camino consiste en una secuencia de movimientos "izquierda" y "derecha" que corresponden a los caracteres 0 y 1).

Para tales árboles, la desigualdad de Kraft-McMillan establece que:

\sum _{x\in {\mathcal {L}}}2^{-\mathrm {profundidad} (x)}\leqslant 1,

donde es el conjunto de hojas del árbol, y es la profundidad de la hoja , el número de aristas en el camino desde la raíz hasta . $\mathcal{L}$ $\mathrm {profundidad} (x)$ $X$ $X$

Para el árbol de la figura de la derecha, tenemos:

{\frac {1}{4}}+4\left({\frac {1}{8}}\right)={\frac {3}{4}}\leqslant 1.

Notas

↑ Kraft, Leon G. (1949), Un dispositivo para cuantificar, agrupar y codificar pulsos modulados en amplitud , Cambridge, MA: tesis de maestría, Departamento de Ingeniería Eléctrica, Instituto de Tecnología de Massachusetts , < http://dspace.mit.edu/ handle/1721.1/12390 > Archivado el 22 de abril de 2009 en Wayback Machine .
↑ McMillan, Brockway (1956), Dos desigualdades implícitas en la descifrabilidad única , IEEE Trans. Teoría de la información Vol . 2 (4 ) : 115–116, doi : 10.1109 /TIT.1956.1056818 ,

Literatura

Gashkov, S. B. Sistemas numéricos y su aplicación . — M. : MTsNMO, 2004. — 52 p. — ISBN 5-94057-146-8 .
Cover, TM, Thomas, JA Elementos de la teoría de la información. - 2006. - Pág. 116. - ISBN 0-471-24195-4 .

Enlaces

Desigualdad de Kraft (NIST) Archivado el 27 de enero de 2009 en Wayback Machine .
http://www.codingtheory.gorodok.net/seminars/seminar%2010.pdf Archivado el 5 de marzo de 2016 en Wayback Machine .