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​ 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 $n$ símbolos a codificar con un alfabeto de $r$ símbolos utilizando un conjunto de $n$ palabras de longitudes $l_{1}$ a $l_{n}$, la desigualdad de Kraft corresponde a:

$\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: $l_{1}$... $l_{n}$.
• Dado un código conocido $C$, con longitudes $l_{1}$ a $l_{n}$, que cumple la desigualdad de Kraft, NO podemos afirmar que $C$ es instantáneo (pues $C$ no tiene por qué cumplir la regla del prefijo). Sin embargo, sabemos que existe algún código instantáneo con longitudes $l_{1}$... $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).

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