Teorema de codificación de fuentes de Shannon

Teoría de la información
Entropía Entropía diferencial Entropía condicional Entropía conjunta Información mutua Información dirigida Información mutua condicional Entropía relativa Tasa de entropía Limitación de la densidad de puntos discretos
Propiedad de equipartición asintótica Teoría de la tasa de distorsión
Teorema de codificación de fuentes de Shannon Capacidad del canal Teorema de codificación de canal ruidoso Teorema de Shannon-Hartley
en a mi

En teoría de la información , el teorema de codificación de fuente de Shannon (o teorema de codificación sin ruido ) establece los límites estadísticos para la posible compresión de datos cuya fuente es una variable aleatoria independiente distribuida de manera idéntica , y el significado operacional de la entropía de Shannon .

El teorema de codificación de la fuente , que debe su nombre a Claude Shannon , muestra que, en el límite, a medida que la longitud de un flujo de datos de variables aleatorias independientes e idénticamente distribuidas (iid) tiende a infinito, es imposible comprimir dichos datos de manera que la tasa de codificación (número promedio de bits por símbolo) sea menor que la entropía de Shannon de la fuente, sin que sea prácticamente seguro que se perderá información. Sin embargo, es posible obtener una tasa de codificación arbitrariamente cercana a la entropía de Shannon, con una probabilidad de pérdida insignificante.

El teorema de codificación de fuentes para códigos de símbolos establece un límite superior y un límite inferior para la longitud mínima posible esperada de las palabras de código en función de la entropía de la palabra de entrada (que se considera una variable aleatoria ) y del tamaño del alfabeto de destino.

Nótese que, para los datos que presentan más dependencias (cuya fuente no es una variable aleatoria iid), la complejidad de Kolmogorov , que cuantifica la longitud mínima de descripción de un objeto, es más adecuada para describir los límites de la compresión de datos. La entropía de Shannon tiene en cuenta solo las regularidades de frecuencia, mientras que la complejidad de Kolmogorov tiene en cuenta todas las regularidades algorítmicas, por lo que en general esta última es menor. Por otro lado, si un objeto es generado por un proceso aleatorio de tal manera que solo tiene regularidades de frecuencia, la entropía está cerca de la complejidad con alta probabilidad (Shen et al. 2017). ^[1]

La codificación de fuente es una asignación de (una secuencia de) símbolos de una fuente de información a una secuencia de símbolos alfabéticos (normalmente bits) de modo que los símbolos de fuente se puedan recuperar exactamente a partir de los bits binarios (codificación de fuente sin pérdida) o recuperarse con cierta distorsión (codificación de fuente con pérdida). Este es un enfoque de la compresión de datos .

En teoría de la información, el teorema de codificación de fuentes (Shannon 1948) ^[2] establece informalmente que (MacKay 2003, pág. 81, ^[3] Cover 2006, Capítulo 5 ^[4] ):

Las variables aleatorias N i.id cada una con entropía H ( X ) se pueden comprimir en más de N H ( X ) bits con un riesgo insignificante de pérdida de información, ya que N → ∞ ; pero a la inversa, si se comprimen en menos de N H ( X ) bits es prácticamente seguro que se perderá información.

La secuencia codificada representa el mensaje comprimido de forma biunívoca, bajo el supuesto de que el decodificador conoce la fuente. Desde un punto de vista práctico, esta hipótesis no siempre es cierta. En consecuencia, cuando se aplica la codificación por entropía el mensaje transmitido es . Habitualmente, la información que caracteriza a la fuente se inserta al principio del mensaje transmitido.$Estilo de visualización NH(X)$${\displaystyle NH(X)+(fuente inf.)}$

Sean Σ ₁ , Σ ₂ dos alfabetos finitos y sea Σ^∗
₁y Σ^∗
₂denotan el conjunto de todas las palabras finitas de esos alfabetos (respectivamente).

Supongamos que X es una variable aleatoria que toma valores en Σ ₁ y sea f un código decodificable de forma única de Σ  ^∗
₁a Σ^∗
₂donde |Σ ₂ | = a . Sea S la variable aleatoria dada por la longitud de la palabra de código f  ( X ) . 

Si f es óptimo en el sentido de que tiene la longitud de palabra mínima esperada para X , entonces (Shannon 1948):  

${\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} [S]<{\frac {H(X)}{\log _{2}a}}+1}$

Donde denota el operador de valor esperado .${\displaystyle \mathbb {E}}$

Dado que X es una fuente iid , su serie temporal X ₁ , ..., X _n es iid con entropía H ( X ) en el caso de valor discreto y entropía diferencial en el caso de valor continuo. El teorema de codificación de fuente establece que para cualquier ε > 0 , es decir, para cualquier tasa H ( X ) + ε mayor que la entropía de la fuente, hay un n suficientemente grande y un codificador que toma n repeticiones iid de la fuente, X ^{1: n} , y las asigna a n ( H ( X ) + ε ) bits binarios tales que los símbolos de fuente X ^{1: n} son recuperables de los bits binarios con probabilidad de al menos 1 − ε .

Prueba de viabilidad. Fijemos algún ε > 0 y dejemos

${\displaystyle p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].}$

El conjunto típico , A^ε
_n, se define de la siguiente manera:

${\displaystyle A_{n}^{\varepsilon }=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots ,x_{n})-H_{n}(X)\right|<\varepsilon \right\}.}$

La propiedad de equipartición asintótica (AEP) muestra que para un valor n suficientemente grande , la probabilidad de que una secuencia generada por la fuente se encuentre en el conjunto típico, A^ε
_n, tal como se define, se acerca a uno. En particular, para n suficientemente grande , se puede hacer arbitrariamente cercano a 1 y, específicamente, mayor que (ver AEP para una prueba).${\displaystyle P((X_{1},X_{2},\cdots ,X_{n})\en A_{n}^{\varepsilon })}$${\displaystyle 1-\varepsilon}$

La definición de conjuntos típicos implica que aquellas secuencias que se encuentran en el conjunto típico satisfacen:

${\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p\left(x_{1},\cdots ,x_{n}\right)\leq 2^{-n(H(X)-\varepsilon )}}$

• La probabilidad de que una secuencia se extraiga de A${\displaystyle (X_{1},X_{2},\cdots X_{n})}$^ε
  _nes mayor que 1 − ε .
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}}$, que se sigue del lado izquierdo (límite inferior) para .${\displaystyle p(x_{1},x_{2},\cpuntos x_{n})}$
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}}$, que se desprende del límite superior y del límite inferior de la probabilidad total de todo el conjunto A${\displaystyle p(x_{1},x_{2},\cpuntos x_{n})}$^ε
  _n.

Dado que los bits son suficientes para apuntar a cualquier cadena en este conjunto.${\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n(H(X)+\varepsilon )}$

El algoritmo de codificación: el codificador comprueba si la secuencia de entrada se encuentra dentro del conjunto típico; si es así, genera el índice de la secuencia de entrada dentro del conjunto típico; si no, el codificador genera un número arbitrario de n ( H ( X ) + ε ) dígitos. Mientras la secuencia de entrada se encuentre dentro del conjunto típico (con una probabilidad de al menos 1 − ε ), el codificador no comete ningún error. Por lo tanto, la probabilidad de error del codificador está limitada por encima de ε .

Prueba del inverso : el inverso se demuestra mostrando que cualquier conjunto de tamaño menor que A^ε
_n(en el sentido de exponente) cubriría un conjunto de probabilidades acotadas desde 1 .

Para 1 ≤ i ≤ n , sea s _i la longitud de palabra de cada posible x _i . Defina , donde C se elige de modo que q ₁ + ... + q _n = 1 . Entonces${\displaystyle q_{i}=a^{-s_{i}}/C}$

${\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&=\mathbb {E} S\log _{2}a\\\end{aligned}}}$

donde la segunda línea se sigue de la desigualdad de Gibbs y la quinta línea se sigue de la desigualdad de Kraft :

${\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}$

por lo tanto log C ≤ 0 .

Para la segunda desigualdad podemos establecer

${\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }$

de modo que

${\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}$

y entonces

${\displaystyle a^{-s_{i}}\leq p_{i}}$

y

${\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}$

y por lo tanto, por la desigualdad de Kraft existe un código sin prefijo que tiene esas longitudes de palabra. Por lo tanto, la S mínima satisface

${\displaystyle {\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}}$

Definir el conjunto típico A^ε
_ncomo:

${\displaystyle A_{n}^{\varepsilon }=\left\{x_{1}^{n}\ :\ \left|-{\frac {1}{n}}\log p\left(X_{1},\cdots ,X_{n}\right)-{\overline {H_{n}}}(X)\right|<\varepsilon \right\}.}$

Entonces, para un δ dado > 0 , para un valor n suficientemente grande, Pr( A^ε
_n) > 1 − δ . Ahora simplemente codificamos las secuencias en el conjunto típico, y los métodos habituales en codificación de fuentes muestran que la cardinalidad de este conjunto es menor que . Por lo tanto, en promedio, H _n ( X ) + ε bits son suficientes para codificar con probabilidad mayor que 1 − δ , donde ε y δ se pueden hacer arbitrariamente pequeños, haciendo n más grande.${\displaystyle 2^{n({\overline {H_{n}}}(X)+\varepsilon )}}$

• Codificación de canales
• exponente de error
• Teorema de codificación de canal ruidoso