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.

Mas 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  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).

Notes[editar]

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

References[editar]

External links[editar]