Relación entre la desigualdad de Kraft y los códigos de codificación de entropía óptima

Question

Dado un código binario que verifica La desigualdad de Kraft ¿puedo afirmar que este código es óptimo?

Sé que los códigos óptimos verifican esta desigualdad, así $\sum\limits_{i=1}^{M} 2^{-\ell_i} \leq 1$ donde $\ell_i$ es la longitud de una palabra dada. ¿Lo contrario también es cierto?

La condición para que un código sea óptimo es que sea decodificable de forma única e instantánea (que no tenga palabras como prefijos de otra palabra), ¿no?

Por ejemplo, este código binario $\{0,01,110,111\}$ cumple esta condición pero no es instantánea. ¿Sigue siendo óptimo?

Gracias de antemano.

Answer 1

No. Que un código sea óptimo depende de la distribución de probabilidad de los símbolos fuente. Tomemos el código $\{a \mapsto 0,b \mapsto 01,c \mapsto 011,d \mapsto 111\}$ . Es óptimo si $Pr(a) = 1/2,Pr(b)=1/4,Pr(c)=1/8$ y $Pr(d)=1/8$ no es óptimo si $Pr(a) = 1/8,Pr(b)=1/8,Pr(c)=1/4$ y $Pr(d)=1/2$ . En el primer caso, el coste es $(1/2)\cdot 1 + (1/4)\cdot 2 + (1/4)\cdot 3 = 1.75$ ; en el segundo es $(1/8)\cdot 1 + (1/8)\cdot 2 + (1/4)\cdot 3 + (1/2)\cdot 3 = 2.625$ .