Desigualdad de Kraft

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[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 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

Definición[editar]

Dada una fuente de símbolos a codificar con un alfabeto de 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.
  • Obsérvese que todo código unívocamente decodificable cumple la desigualdad de Kraft (Th. de McMillan).

Notas[editar]

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

Referencias[editar]

Enlaces externos[editar]