¿Cómo hacer que la codificación de símbolos necesite sólo 1,58496 bits/símbolo como se realiza en teoría?

Question

Estoy leyendo el tutorial de obtención de información y veo la siguiente página:

Sé que en el ejemplo anterior, puedo codificar de esta manera:

A 0
B 10
C 11

y entonces esto necesitará $1/3*1+1/3*2+1/3*2=1.6667$ bits por símbolo. Pero, ¿cómo puedo codificar para alcanzar el objetivo de 1,58 en teoría ? ¿Es posible en la práctica?

Answer 1

No se puede hacer eso utilizando palabras clave binarias para símbolos individuales A, B y C.

Como se menciona en los comentarios, por ejemplo, codificación aritmética puede utilizarse para acercarse al límite cuando la secuencia de entrada es larga.

Otro ejemplo sencillo: Se pueden considerar "supersímbolos" que consten de 100 As, Bs y Cs y codificar un supersímbolo cada vez, de modo que cada uno de los $3^{100}$ posibles supersímbolos corresponde a un $159$ -bit binary codeword ( $3^{100}\leq 2^{159}$ ), lo que le da efectivamente $1.59$ bits por símbolo original. O secuencias de $10000$ símbolos, de modo que cada secuencia corresponda a un $15850$ bit codeword ( $3^{10000}\leq 2^{15850}$ ), dando efectivamente $1.585$ bits por símbolo.

Answer 2

La longitud óptima viene dada por el código Huffman. En este caso, corresponde a la codificación que propones, con una longitud media de código de 1,6667. Por lo tanto, esto es óptimo ... si se restringe a un single symbol=>single codeword codificación. Pero puedes hacerlo mejor si, en lugar de codificar cada símbolo por separado, codificas los pares, o los tripletes, o... Es decir, si codificas la "fuente ampliada".

Por ejemplo, tomando la extensión de orden $2$ Tendrías $3\times 3=9$ símbolos, cada uno con probabilidad $1/9$ y podrías codificarlos así:

 AA 000
 AB 001
 AC 010
 BA 011
 BB 100 
 BC 101
 CA 110
 CB 1110
 CC 1111

Esto da una duración media de $(3 \times 7/9 + 4 \times 2/9)/2=1.6111\cdots$ . Esto es mejor, pero sigue sin alcanzar el límite de Shannon.

Para la extensión tres, tendríamos 27 símbolos y el código Huffman sería

         n   L 
00**    (4)  4
0100    (1)  4
0101*   (2)  5 
011**   (4)  5
1****  (16)  5

con una longitud media $[ 4 \times (4+1)/27 + 5 \times (2+4+16)/27]/3=1.605...$

Puedes hacerlo aún mejor -y aproximarte asintóticamente al valor teórico- tomando extensiones de orden cada vez más alto. O puedes utilizar la codificación aritmética, que, en esencia, hace precisamente eso.

Una codificación sencilla -subóptima pero sencilla, y que logra el objetivo en el ejercicio original- sería la extensión de pedido 5 lo que da $3^5=243$ símbolos. Esto se puede codificar trivialmente con 8 bits cada uno ( $2^8=256 < 243$ ), lo que da $8$ bits/ $5$ símbolos = 1,6 bits por símbolo .