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 l₁ 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₁... l_n.
• Dado un código conocido C, con longitudes l₁ 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₁... 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).