- Desigualdad de Kraft
-
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 l1 a ln, 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 : l1... ln.
- Dado un código conocido C, con longitudes l1 a ln, 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 l1... ln, 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).
Categorías:- Teoría de códigos
- Desigualdades
Wikimedia foundation. 2010.
