Codificación de Shannon

En el campo de la compresión de datos , la codificación de Shannon , que recibe su nombre de su creador, Claude Shannon , es una técnica de compresión de datos sin pérdidas que construye un código de prefijo basado en un conjunto de símbolos y sus probabilidades (estimadas o medidas). Es subóptima en el sentido de que no alcanza la longitud de palabra de código esperada más baja posible, como lo hace la codificación de Huffman , y nunca supera, aunque a veces iguala, la codificación de Shannon-Fano (el método de Fano).

El método fue el primero de su tipo, la técnica se utilizó para demostrar el teorema de codificación sin ruido de Shannon en su artículo de 1948 "Una teoría matemática de la comunicación" ^{[ 1 ]} y, por lo tanto, es una pieza central de la era de la información.

Los métodos de codificación de Shannon-Fano dieron origen al campo de la teoría de la información y, sin sus contribuciones, el mundo no contaría con ninguno de sus muchos sucesores; por ejemplo, la codificación de Huffman o la codificación aritmética . Gran parte de nuestra vida cotidiana está significativamente influenciada por los datos digitales , y esto no sería posible sin la codificación de Shannon-Fano y la continua evolución de sus métodos. ^{[ 2 ]}

En la codificación de Shannon, los símbolos se organizan en orden del más probable al menos probable, y se les asignan palabras clave tomando el primero. ${\displaystyle l_{i}=\left\lceil -\log _{2}p_{i}\right\rceil }$bits de las expansiones binarias de las probabilidades acumuladas${\displaystyle \sum \limits _{k=0}^{i-1}p_{k}.}$Aquí${\displaystyle \lceil x\rceil }$denota la función techo (que redondea${\displaystyle x}$hasta el siguiente valor entero).

En la tabla siguiente se muestra un ejemplo de cómo crear un esquema de código para los símbolos a ₁ a a _6. El valor de l _i indica el número de bits utilizados para representar el símbolo a _i . La última columna muestra el código de bits de cada símbolo.

Shannon, Claude Elwood. "Una teoría matemática de la comunicación". ACM SIGMOBILE mobile computing and communications review 5.1 (2001): 3-55.