TEORIA DE LA INFORMACION

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.


Desigualdad de McMillan

La desigualdad de McMillan es un teorema de la teoría de códigos que reduce la existencia de de códigos unívocamente descifrables al cumplimiento de la desigualdad de Kraft. Es decir, si existe un código unívocamente descifrable con longitudes de palabra prescritas entonces es un código instantáneamente descifrable que satisface la desigualdad de Kraft.