Teorema de codificación de fuentes de Shannon

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]

Declaraciones

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 .

Teorema de codificación de fuentes

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 \to \infty$ ; 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)$ $NH(X)+(fuente inf.)$

Teorema de codificación de fuentes para códigos de símbolos

Sean $Σ 1, Σ 2$ dos alfabetos finitos y sea $Σ * 1$ y $Σ * 2$ denotan el conjunto de todas las palabras finitas de esos alfabetos (respectivamente).

Supongamos que $X$ es una variable aleatoria que toma valores en $Σ 1$ y sea $f$ un código decodificable de forma única de $Σ$ $* 1$ a $Σ * 2$ donde $|Σ 2 | = 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):

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

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

Prueba: teorema de codificación de fuentes

Dado que $X$ es una fuente iid , su serie temporal $X 1, ..., 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

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:

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). $P((X_{1},X_{2},\cdots ,X_{n})\en A_{n}^{\varepsilon })$ $1-\varepsilon$

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

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$ $(X_{1},X_{2},\cdots X_{n})$ $ε n$ es mayor que $1 - ε$ .
$\left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}$ , que se sigue del lado izquierdo (límite inferior) para . $p(x_{1},x_{2},\cpuntos x_{n})$
$\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$ $p(x_{1},x_{2},\cpuntos x_{n})$ $ε n$ .

Dado que los bits son suficientes para apuntar a cualquier cadena en este conjunto. $\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$ .

Demostración: Teorema de codificación de fuentes para códigos de símbolos

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

{\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 :

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

por lo tanto $log C \leq 0$ .

Para la segunda desigualdad podemos establecer

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

de modo que

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

y entonces

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

\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

{\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}}

Extensión a fuentes independientes no estacionarias

Codificación de fuente sin pérdida de velocidad fija para fuentes independientes no estacionarias de tiempo discreto

Definir el conjunto típico $A ε n$ como:

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. $2^{n({\overline {H_{n}}}(X)+\varepsilon )}$

Véase también

Referencias

^ Shen, A. y Uspensky, VA y Vereshchagin, N. (2017). "Capítulo 7.3. : Complejidad y entropía". Complejidad de Kolmogorov y aleatoriedad algorítmica. American Mathematical Society. pág. 226. ISBN 9781470431822.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ CE Shannon , "Una teoría matemática de la comunicación Archivado el 16 de febrero de 2009 en Wayback Machine ", Bell System Technical Journal , vol. 27, págs. 379-423, 623-656, julio, octubre de 1948
^ David JC MacKay. Teoría de la información, inferencia y algoritmos de aprendizaje. Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
^ Portada, Thomas M. (2006). "Capítulo 5: Compresión de datos". Elementos de la teoría de la información. John Wiley & Sons. págs. 103-142. ISBN 0-471-24195-4.