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 .

Aplicaciones e intuiciones

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.

Declaración formal

Deje que cada símbolo fuente del alfabeto

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

ser codificado en un código decodificable único sobre un alfabeto de tamaño con longitudes de palabras de código ${\displaystyle 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}}$ ${\displaystyle r}$

Ejemplo: árboles binarios

9, 14, 19, 67 y 76 son nodos de hojas a profundidades de 3, 3, 3, 3 y 2, respectivamente.

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{leaves}}}2^{-{\text{depth}}(\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.}$

Prueba

Prueba de códigos de prefijo

Ejemplo de árbol binario. Los nodos rojos representan un árbol de prefijos. Se muestra el método para calcular la cantidad de nodos de hojas descendientes en el árbol completo.

Primero, demostremos que la desigualdad de Kraft se cumple siempre que el código sea un código de prefijo. ${\displaystyle 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}}$ ${\displaystyle A}$ ${\displaystyle r}$ ${\displaystyle \ell _{n}}$ ${\displaystyle A}$ ${\displaystyle <\ell _{n}}$ ${\displaystyle r}$ ${\displaystyle \ell _{n}}$ ${\displaystyle \ell \leqslant \ell _{n}}$ ${\displaystyle r}$ ${\displaystyle \ell }$ ${\displaystyle i}$ ${\displaystyle v_{i}}$ ${\displaystyle A_{i}}$ ${\displaystyle \ell _{n}}$ ${\displaystyle A}$ ${\displaystyle 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, ${\displaystyle 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}}$ ${\displaystyle 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}}}$ ${\displaystyle 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.

Prueba del caso 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]} ${\displaystyle 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=\sum _{i=1}^{n}r^{-l_{i}}}$ ${\displaystyle C^{m}}$ ${\displaystyle m\in \mathbb {N} }$ ${\displaystyle m}$ ${\displaystyle C\leq 1}$ ${\displaystyle 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 ${\displaystyle S^{m}}$ ${\displaystyle s_{i_{1}}s_{i_{2}}\dots s_{i_{m}}}$ ${\displaystyle i_{1},i_{2},\dots ,i_{m}}$ ${\displaystyle n}$ ${\displaystyle s_{i_{1}}s_{i_{2}}\dots s_{i_{m}}=s_{j_{1}}s_{j_{2}}\dots s_{j_{m}}}$ ${\displaystyle i_{1}=j_{1},i_{2}=j_{2},\dots ,i_{m}=j_{m}}$ ${\displaystyle S^{m}}$

${\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}$

Construcción alternativa para el recíproco

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}}$

Generalizaciones

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

Teorema  :  Si son decodificables de forma única, y cada palabra de código en es una concatenación de palabras de código en , entonces ${\textstyle C,D}$ ${\textstyle C}$ ${\textstyle D}$ $${\displaystyle \sum _{c\in C}r^{-|c|}\leq \sum _{c\in D}r^{-|c|}}$$

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

Prueba

Sea la función generadora del código, es decir, ${\textstyle Q_{C}(x)}$ $${\displaystyle Q_{C}(x):=\sum _{c\in C}x^{|c|}}$$

Mediante un argumento de conteo, el coeficiente -ésimo de es el número de cadenas de longitud con longitud de código . Es decir, de manera similar, ${\textstyle k}$ ${\textstyle Q_{C}^{n}}$ ${\textstyle n}$ ${\textstyle k}$ $${\displaystyle Q_{C}^{n}(x)=\sum _{k\geq 0}x^{k}\#({\text{strings of length }}n{\text{ with }}C{\text{-codes of length }}k)}$$
$${\displaystyle {\frac {1}{1-Q_{C}(x)}}=1+Q_{C}(x)+Q_{C}(x)^{2}+\cdots =\sum _{k\geq 0}x^{k}\#({\text{strings with }}C{\text{-codes of length }}k)}$$

Dado que el código es decodificable de forma única, cualquier potencia de está absolutamente limitada por , por lo que cada uno de y es analítico en el disco . ${\textstyle Q_{C}}$ ${\textstyle r|x|+r^{2}|x|^{2}+\cdots ={\frac {r|x|}{1-r|x|}}}$ ${\textstyle Q_{C},Q_{C}^{2},\dots }$ ${\textstyle {\frac {1}{1-Q_{C}(x)}}}$ ${\textstyle |x|<1/r}$

Afirmamos que para todos , ${\textstyle x\in (0,1/r)}$ $${\displaystyle Q_{C}^{n}\leq Q_{D}^{n}+Q_{D}^{n+1}+\cdots }$$

El lado izquierdo es y el lado derecho es $${\displaystyle \sum _{k\geq 0}x^{k}\#({\text{strings of length }}n{\text{ with }}C{\text{-codes of length }}k)}$$

$${\displaystyle \sum _{k\geq 0}x^{k}\#({\text{strings of length}}\geq n{\text{ with }}D{\text{-codes of length }}k)}$$

Ahora bien, dado que cada palabra de código en es una concatenación de palabras de código en , y es decodificable de forma única, cada cadena de longitud con -código de longitud corresponde a una cadena única cuyo -código es . La cadena tiene una longitud de al menos . ${\textstyle C}$ ${\textstyle D}$ ${\textstyle D}$ ${\textstyle n}$ ${\textstyle C}$ ${\textstyle c_{1}\dots c_{n}}$ ${\textstyle k}$ ${\textstyle s_{c_{1}}\dots s_{c_{n}}}$ ${\textstyle D}$ ${\textstyle c_{1}\dots c_{n}}$ ${\textstyle n}$

Por lo tanto, los coeficientes de la izquierda son menores o iguales que los coeficientes de la derecha.

Así, para todos , y todos , tenemos Tomando límite, tenemos para todos . ${\textstyle x\in (0,1/r)}$ ${\textstyle n=1,2,\dots }$ $${\displaystyle Q_{C}\leq {\frac {Q_{D}}{(1-Q_{D})^{1/n}}}}$$ ${\textstyle n\to \infty }$ ${\textstyle Q_{C}(x)\leq Q_{D}(x)}$ ${\textstyle x\in (0,1/r)}$

Como y ambos convergen, tenemos tomando el límite y aplicando el teorema de Abel . ${\textstyle Q_{C}(1/r)}$ ${\textstyle Q_{D}(1/r)}$ ${\textstyle Q_{C}(1/r)\leq Q_{D}(1/r)}$

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

Notas

1. Portada, Thomas M.; Thomas, Joy A. (2006), "Compresión de datos", Elementos de la teoría de la información (2.ª ed.), John Wiley & Sons, Inc, págs. 108-109, doi :10.1002/047174882X.ch5, ISBN 978-0-471-24195-9
2. De Rooij, Steven; Grünwald, Peter D. (2011), "SUERTE Y ARREPENTIMIENTO EN LA INFERENCIA DE LONGITUD MÍNIMA DE DESCRIPCIÓN", Filosofía de la estadística (1.ª ed.), Elsevier, pág. 875, ISBN 978-0-080-93096-1
3. Karush, J. (abril de 1961). "Una prueba simple de una desigualdad de McMillan (Corresp.)". IEEE Transactions on Information Theory . 7 (2): 118. doi :10.1109/TIT.1961.1057625. ISSN  0018-9448.
4. Portada, Thomas M.; Thomas, Joy A. (2006). Elementos de la teoría de la información (2.ª ed.). Hoboken, Nueva Jersey: Wiley-Interscience. ISBN 978-0-471-24195-9.
5. Foldes, Stephan (21 de junio de 2008). "Sobre el teorema de McMillan sobre códigos descifrables de forma única". arXiv : 0806.3277 [math.CO].
6. Schumacher, Benjamin; Westmoreland, Michael D. (10 de septiembre de 2001). "Codificación cuántica de longitud indeterminada". Physical Review A . 64 (4): 042304. arXiv : quant-ph/0011014 . Código Bibliográfico :2001PhRvA..64d2304S. doi :10.1103/PhysRevA.64.042304. S2CID  53488312.

Referencias

• 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.

Véase también

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