¿En qué consiste la desigualdad de Kraft?

Desigualdad de Kraft


En la teoria de codigos, '''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 arboles 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.


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





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

Su explicación en el siguiente link: https://youtu.be/QM_B681Q6hw