Desigualdad de Kraft

En la teoría de códigos, '''la desigualdad de Kraft''', nombrada así debido a Leon Kraft, expresa las condiciones suficientes para la existencia de un código prefijo^[1] y, las condiciones necesarias para la existencia de un código unívocamente decodificable para un grupo dado de longitudes de palabra. Sus aplicaciones a los códigos y árboles prefijos son usualmente empleadas en ciencias de la computación y teoría de la información.

Más específicamente, la desigualdad de Kraft, limita la longitud de las palabras en un código prefijo: si se toma la exponencial de la longitud de cada palabra válida, el grupo resultante de valores debe seguir una función de probabilidad, es decir, su medida total debe ser menor o igual a uno (1). La desigualdad de Kraft puede ser entendida en términos de un presupuesto limitado de palabras a ser empleado, siendo las palabras más cortas, las más caras.

• Si la desigualdad de Kraft se cumple de manera estrictamente desigual (menor a 1), el código tiene alguna redundancia.
• Si la desigualdad de Kraft se cumple de manera que el resultado es exactamente igual a 1, el código en cuestión es un código completo.
• Si la desigualdad de Kraft no se cumple, el código no es unívocamente descodificable.

Definición

Dada una fuente de ${\displaystyle n}$ símbolos a codificar con un alfabeto de ${\displaystyle r}$ símbolos utilizando un conjunto de ${\displaystyle n}$ palabras de longitudes ${\displaystyle l_{1}}$ a ${\displaystyle l_{n}}$, la desigualdad de Kraft corresponde a:

${\displaystyle \sum _{i=1}^{n}\left({\frac {1}{r}}\right)^{\ell _{i}}\leq 1.}$

Hay que tener en cuenta que:

• Es condición necesaria para que un código sea uno de los códigos prefijo (o códigos instantáneos).
• Es condición suficiente para que exista algún código prefijo (o código instantáneo) con la secuencia de longitudes: ${\displaystyle l_{1}}$... ${\displaystyle l_{n}}$.
• Dado un código conocido ${\displaystyle C}$, con longitudes ${\displaystyle l_{1}}$ a ${\displaystyle l_{n}}$, que cumple la desigualdad de Kraft, NO podemos afirmar que ${\displaystyle C}$ es instantáneo (pues ${\displaystyle C}$ no tiene por qué cumplir la regla del prefijo). Sin embargo, sabemos que existe algún código instantáneo con longitudes ${\displaystyle l_{1}}$... ${\displaystyle l_{n}}$, puesto que se verifica la desigualdad de Kraft con dicha secuencia de longitudes.
• Obsérvese que todo código unívocamente decodificable cumple la desigualdad de Kraft (Th. de McMillan).

Notas

1. Cover, Thomas M.; Thomas, Joy A. (2006), Elements of Information Theory (pdf) (2nd edición), John Wiley & Sons, Inc, pp. 108-109, ISBN 0-471-24195-4, doi:10.1002/047174882X.ch5.

Referencias

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

• McMillan, Brockway (1956), «Two inequalities implied by unique decipherability», IEEE Trans. Information Theory 2 (4): 115-116, doi:10.1109/TIT.1956.1056818..

Enlaces externos

• Kraft's inequality (NIST)

• Datos: Q371685