Desigualdad de Kraft-McMillan

En teoría de codificación , la desigualdad de Kraft-McMillan proporciona una condición necesaria y suficiente para la existencia de un código de prefijo ^[1] (en la versión de Leon G. Kraft) o un código decodificable de forma única (en la versión de Brockway McMillan ) para un conjunto dado de longitudes de palabras de código . Sus aplicaciones a los códigos de prefijo y árboles a menudo encuentran uso en la ciencia de la computación y la teoría de la información . El código de prefijo puede contener un número finito o infinito de palabras de código.

La desigualdad de Kraft fue publicada en Kraft (1949). Sin embargo, el artículo de Kraft solo analiza los códigos de prefijo y atribuye el análisis que conduce a la desigualdad a Raymond Redheffer . El resultado fue descubierto de forma independiente en McMillan (1956). McMillan demuestra el resultado para el caso general de códigos decodificables de forma única y atribuye la versión para los códigos de prefijo a una observación oral realizada en 1955 por Joseph Leo Doob .

La desigualdad de Kraft limita la longitud de las palabras clave en un código de prefijo : si se toma una exponencial de la longitud de cada palabra clave válida, el conjunto de valores resultante debe parecerse a una función de masa de probabilidad , es decir, debe tener una medida total menor o igual a uno. La desigualdad de Kraft puede considerarse en términos de un presupuesto limitado que se gastará en palabras clave, siendo más caras las palabras clave más cortas. Entre las propiedades útiles que se desprenden de la desigualdad se encuentran las siguientes afirmaciones:

• Si la desigualdad de Kraft se cumple con la desigualdad estricta, el código tiene cierta redundancia .
• Si la desigualdad de Kraft se cumple con la igualdad, el código en cuestión es un código completo. ^[2]
• Si la desigualdad de Kraft no se cumple, el código no es decodificable de forma única .
• Para cada código decodificable de forma única, existe un código de prefijo con la misma distribución de longitud.

Deje que cada símbolo fuente del alfabeto

${\displaystyle S=\{\,s_{1},s_{2},\ldots ,s_{n}\,\}}$

codificarse en un código decodificable de forma única sobre un alfabeto de tamaño con longitudes de palabras de código${\estilo de visualización r}$

${\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n}.}$

Entonces

${\displaystyle \sum_{i=1}^{n}r^{-\ell_{i}}\leqslant 1.}$

Por el contrario, para un conjunto dado de números naturales que satisfacen la desigualdad anterior, existe un código decodificable de forma única sobre un alfabeto de tamaño con esas longitudes de palabras de código.${\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n}}$${\estilo de visualización r}$

Cualquier árbol binario puede considerarse como la definición de un código de prefijo para las hojas del árbol. La desigualdad de Kraft establece que

${\displaystyle \sum _{\ell \in {\text{hojas}}}2^{-{\text{profundidad}}(\ell )}\leqslant 1.}$

Aquí la suma se toma de las hojas del árbol, es decir, los nodos sin hijos. La profundidad es la distancia al nodo raíz. En el árbol de la derecha, esta suma es

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

Primero, demostremos que la desigualdad de Kraft se cumple siempre que el código sea un código de prefijo.${\estilo de visualización S}$

Supóngase que . Sea el árbol -ario completo de profundidad (por lo tanto, cada nodo de en el nivel tiene hijos, mientras que los nodos en el nivel son hojas). Cada palabra de longitud sobre un alfabeto -ario corresponde a un nodo en este árbol en la profundidad . La palabra n en el código de prefijo corresponde a un nodo ; sea el conjunto de todos los nodos de hoja (es decir, de nodos en la profundidad ) en el subárbol de enraizado en . Como ese subárbol tiene altura , tenemos${\displaystyle \ell _{1}\leqslant \ell _{2}\leqslant \cdots \leqslant \ell _{n}}$${\estilo de visualización A}$${\estilo de visualización r}$${\displaystyle \ell_{n}}$${\estilo de visualización A}$${\displaystyle <\ell _{n}}$${\estilo de visualización r}$${\displaystyle \ell_{n}}$${\displaystyle \ell \leqslant \ell _ {n}}$${\estilo de visualización r}$${\displaystyle \ell}$${\estilo de visualización i}$$estilo de visualización v_{i}}$$Estilo de visualización A_{i}}$${\displaystyle \ell_{n}}$${\estilo de visualización A}$$estilo de visualización v_{i}}$${\displaystyle \ell_{n}-\ell_{i}}$

${\displaystyle |A_{i}|=r^{\ell _{n}-\ell _{i}}.}$

Dado que el código es un código de prefijo, esos subárboles no pueden compartir ninguna hoja, lo que significa que

${\displaystyle A_{i}\cap A_{j}=\varnothing ,\quad i\neq j.}$

Por lo tanto, dado que el número total de nodos en profundidad es , tenemos${\displaystyle \ell_{n}}$${\displaystyle r^{\ell _{n}}}$

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|=\sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}\leqslant r^{\ell _{n}}}$

de donde se sigue el resultado.

Por el contrario, dada cualquier secuencia ordenada de números naturales,${\estilo de visualización n}$

${\displaystyle \ell _{1}\leqslant \ell _{2}\leqslant \cdots \leqslant \ell _{n}}$

Al satisfacer la desigualdad de Kraft, se puede construir un código de prefijo con longitudes de palabras de código iguales a cada una eligiendo una palabra de longitud arbitrariamente, y luego descartando todas las palabras de mayor longitud que la tengan como prefijo. Nuevamente, interpretaremos esto en términos de nodos de hoja de un árbol -ario de profundidad . Primero elija cualquier nodo del árbol completo en profundidad ; corresponde a la primera palabra de nuestro nuevo código. Dado que estamos construyendo un código de prefijo, todos los descendientes de este nodo (es decir, todas las palabras que tienen esta primera palabra como prefijo) se vuelven inadecuados para su inclusión en el código. Consideramos los descendientes en profundidad (es decir, los nodos de hoja entre los descendientes); hay tales nodos descendientes que se eliminan de la consideración. La siguiente iteración elige un nodo (sobreviviente) en profundidad y elimina más nodos de hoja, y así sucesivamente. Después de las iteraciones, hemos eliminado un total de${\displaystyle \ell _{i}}$${\displaystyle \ell _{i}}$${\estilo de visualización r}$${\displaystyle \ell_{n}}$${\displaystyle \ell _{1}}$${\displaystyle \ell_{n}}$${\displaystyle r^{\ell _{n}-\ell _{1}}}$${\displaystyle \ell_{2}}$${\displaystyle r^{\ell _{n}-\ell _{2}}}$${\estilo de visualización n}$

${\displaystyle \sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}}$

nodos. La pregunta es si necesitamos eliminar más nodos de hoja de los que realmente tenemos disponibles ( en total) en el proceso de creación del código. Dado que la desigualdad de Kraft se cumple, de hecho tenemos${\displaystyle r^{\ell _{n}}}$

${\displaystyle \sum_{i=1}^{n}r^{\ell_{n}-\ell_{i}}\leqslant r^{\ell_{n}}}$

y así se puede construir un código de prefijo. Nótese que, como la elección de nodos en cada paso es en gran medida arbitraria, se pueden construir muchos códigos de prefijo adecuados diferentes, en general.

Ahora demostraremos que la desigualdad de Kraft se cumple siempre que sea un código decodificable de forma única. (No es necesario demostrar la inversa, ya que ya la hemos demostrado para códigos de prefijo, lo que es una afirmación más sólida). La prueba es de Jack I. Karush. ^{[3] [4]}${\estilo de visualización S}$

Solo necesitamos demostrarlo cuando hay un número finito de palabras clave. Si hay un número infinito de palabras clave, entonces cualquier subconjunto finito de ellas también es decodificable de manera única, por lo que satisface la desigualdad de Kraft-McMillan. Si tomamos el límite, tenemos la desigualdad para el código completo.

Denote . La idea de la prueba es obtener un límite superior para y demostrar que solo puede cumplirse para todos si . Reescríbalo como${\displaystyle C=\suma _{i=1}^{n}r^{-l_{i}}}$$Estilo de visualización C^{m}}$${\displaystyle m\in \mathbb {N}}$${\estilo de visualización m}$${\displaystyle C\leq 1}$$Estilo de visualización C^{m}}$

${\displaystyle {\begin{aligned}C^{m}&=\left(\sum _{i=1}^{n}r^{-l_{i}}\right)^{m}\\&=\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{n}\cdots \sum _{i_{m}=1}^{n}r^{-\left(l_{i_{1}}+l_{i_{2}}+\cdots +l_{i_{m}}\right)}\\\end{aligned}}}$

Consideremos todas las m -potencias , en forma de palabras , donde son índices entre 1 y . Nótese que, dado que se supuso que S era decodificable de forma única, implica . Esto significa que cada sumando corresponde exactamente a una palabra en . Esto nos permite reescribir la ecuación a$Estilo de visualización Sm$${\displaystyle s_{i_{1}}s_{i_{2}}\puntos s_{i_{m}}}$${\displaystyle i_{1},i_{2},\puntos ,i_{m}}$${\estilo de visualización n}$${\displaystyle s_{i_{1}}s_{i_{2}}\puntos s_{i_{m}}=s_{j_{1}}s_{j_{2}}\puntos s_{j_{m}}}$${\displaystyle i_{1}=j_{1},i_{2}=j_{2},\puntos ,i_{m}=j_{m}}$$Estilo de visualización Sm$

${\displaystyle C^{m}=\sum _{\ell =1}^{m\cdot \ell _{max}}q_{\ell }\,r^{-\ell }}$

donde es el número de palabras de código en de longitud y es la longitud de la palabra de código más larga en . Para un alfabeto de -letras solo hay palabras posibles de longitud , por lo que . Usando esto, establecemos el límite superior :${\displaystyle q_{\ell }}$${\displaystyle S^{m}}$${\displaystyle \ell }$${\displaystyle \ell _{max}}$${\displaystyle S}$${\displaystyle r}$${\displaystyle r^{\ell }}$${\displaystyle \ell }$${\displaystyle q_{\ell }\leq r^{\ell }}$${\displaystyle C^{m}}$

${\displaystyle {\begin{aligned}C^{m}&=\sum _{\ell =1}^{m\cdot \ell _{max}}q_{\ell }\,r^{-\ell }\\&\leq \sum _{\ell =1}^{m\cdot \ell _{max}}r^{\ell }\,r^{-\ell }=m\cdot \ell _{max}\end{aligned}}}$

Tomando la raíz -ésima, obtenemos${\displaystyle m}$

${\displaystyle C=\sum _{i=1}^{n}r^{-l_{i}}\leq \left(m\cdot \ell _{max}\right)^{\frac {1}{m}}}$

Este límite se cumple para cualquier . El lado derecho es 1 asintóticamente, por lo que debe cumplirse (de lo contrario, la desigualdad se rompería para un suficientemente grande ).${\displaystyle m\in \mathbb {N} }$${\displaystyle \sum _{i=1}^{n}r^{-l_{i}}\leq 1}$${\displaystyle m}$

Dada una secuencia de números naturales,${\displaystyle n}$

${\displaystyle \ell _{1}\leqslant \ell _{2}\leqslant \cdots \leqslant \ell _{n}}$

Al satisfacer la desigualdad de Kraft, podemos construir un código de prefijo como sigue. Defina la i- ^ésima palabra de código, C _i , como los primeros dígitos después del punto decimal en la representación base r de${\displaystyle \ell _{i}}$

${\displaystyle \sum _{j=1}^{i-1}r^{-\ell _{j}}.}$

Nótese que, por la desigualdad de Kraft, esta suma nunca es mayor que 1. Por lo tanto, las palabras clave capturan el valor completo de la suma. Por lo tanto, para j > i , los primeros dígitos de C _j forman un número mayor que C _i , por lo que el código no tiene prefijo.${\displaystyle \ell _{i}}$

La siguiente generalización se encuentra en ^{[5] .}

El teorema anterior es el caso especial cuando .${\displaystyle D=\{a_{1},\dots ,a_{r}\}}$

Existe una generalización para el código cuántico . ^[6]

• Kraft, Leon G. (1949), Un dispositivo para cuantificar, agrupar y codificar pulsos modulados en amplitud (Tesis), Cambridge, MA: Tesis de maestría, Departamento de Ingeniería Eléctrica, Instituto Tecnológico de Massachusetts , hdl :1721.1/12390.

• McMillan, Brockway (1956), "Dos desigualdades implicadas por la descifrabilidad única", IEEE Trans. Inf. Theory , 2 (4): 115–116, doi :10.1109/TIT.1956.1056818.

• La constante de Chaitin
• Código canónico de Huffman