Teorema de codificación de fuente: ¿número óptimo de bits?

Question

La codificación de fuente teorema dice que la transferencia de información con la variable longitud de código utiliza menos bits y es igual a la entropía de la distribución. También dice que no hay ningún código que utiliza el menor número de bits ( o no? He entendido mal). Mi pregunta es, no es, obviamente, una forma de transmitir la misma información usando el menor número de bits de la entropía. Por ejemplo:

Vamos

$P(x) = \frac{1}{2}, \frac{1}{4}, \frac{1}{16}, \frac{1}{32}, \frac{1}{64},\frac{1}{64}$ , respectivamente, para x= 1,2,3,4,5,6.

Si mediante el uso de codificación de fuente teorema, una variable de código de longitud = $log_2(p(x))$ es usado, entonces

el promedio de bits que se utiliza es $1*\frac{1}{2} + 2*\frac{1}{4} + 4*\frac{1}{16} + 5*\frac{1}{32} + 6*\frac{1}{64} + 6*\frac{1}{64}$ = 1.5938.

Pero obviamente, hay una manera mejor de hacer esto:

Sólo utilice los siguientes códigos: 0,1,10,11,100,101.

Esto sin duda utiliza menos bits en promedio ( bits $\lt 1.5938$). Entonces, ¿cuál es el significado real de la fuente teorema de codificación?

Answer 1

El origen del teorema de codificación restringe a unívocamente decodificable códigos, que en la práctica son la única utilidad de los códigos.

Para ver que el código no es unívocamente decodificable, y por lo tanto prácticamente inútil, imagine que usted reciba la secuencia de $01$: usted no puede saber lo que corresponde a una concatenación de $0|1$ (los dos primeros símbolos) o $01$ (el tercer símbolo).

Generalmente, se restringe aún más el conjunto de códigos aceptables, por la restricción para el prefijo de códigos. Se puede demostrar que, al hacerlo, uno no pierde nada (en términos de longitud media), y el prefijo de códigos que son más prácticos para decodificar y más fáciles de analizar.