Teorema de codificación de fuentes de Shannon

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

El teorema de codificación de fuente , que recibe su nombre de Claude Shannon , demuestra que, en el límite, cuando la longitud de una secuencia de datos de variables aleatorias independientes e idénticamente distribuidas (i.i.d.) tiende al infinito, resulta imposible comprimir dichos datos de forma que la tasa de codificación (número medio de bits por símbolo) sea inferior a 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 fuente para códigos de símbolos establece un límite superior e inferior para la longitud mínima esperada de las palabras clave en función de la entropía de la palabra de entrada (que se considera una variable aleatoria ) y del tamaño del alfabeto objetivo.

Cabe señalar que, para datos que presentan más dependencias (cuya fuente no es una variable aleatoria i.i.d.), 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 solo tiene en cuenta las regularidades de frecuencia, mientras que la complejidad de Kolmogorov considera todas las regularidades algorítmicas, por lo que, en general, esta última es menor. Por otro lado, si un objeto se genera mediante un proceso aleatorio de tal manera que solo presenta regularidades de frecuencia, la entropía se aproxima a 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 del alfabeto (generalmente bits), de manera que los símbolos de la fuente se puedan recuperar con exactitud a partir de los símbolos del alfabeto (codificación de fuente sin pérdidas) o con cierta distorsión (codificación de fuente con pérdidas). Este es un método para la compresión de datos .

Dado que X es una fuente iid , su serie temporal X ₁ , ..., X _n es iid con entropía H ( X ) en el caso de valores discretos y entropía diferencial en el caso de valores continuos. 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, existe un n suficientemente grande y un codificador que toma n repeticiones iid de la fuente, X ^{1: n} , y la mapea a n ( H ( X ) + ε ) bits binarios tales que los símbolos de la fuente X ^{1: n} se pueden recuperar de los bits binarios con una probabilidad de al menos 1 − ε .

Prueba de alcanzabilidad. 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 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 aproxima a uno. En particular, para n suficientemente grande ,${\displaystyle P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })}$puede hacerse arbitrariamente cercano a 1 y, específicamente, mayor que${\displaystyle 1-\varepsilon }$(Véase AEP para una demostración).

La definición de conjuntos típicos implica que aquellas secuencias que pertenecen al 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 una secuencia${\displaystyle (X_{1},X_{2},\cdots X_{n})}$siendo extraído de A ^ε _n es mayor que 1 − ε .
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}}$, que se deduce del lado izquierdo (límite inferior) para${\displaystyle p(x_{1},x_{2},\cdots x_{n})}$.
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}}$, lo cual se deduce del límite superior para${\displaystyle p(x_{1},x_{2},\cdots x_{n})}$ y el límite inferior de la probabilidad total del conjunto completo A ^ε _n .

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

El algoritmo de codificación: el codificador comprueba si la secuencia de entrada pertenece al conjunto típico; si es así, devuelve el índice de la secuencia de entrada dentro del conjunto típico; si no, el codificador devuelve un número arbitrario de n ( H ( X ) + ε ) dígitos. Mientras la secuencia de entrada pertenezca al 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á acotada superiormente por ε .

Prueba del recíproco : el recíproco se prueba mostrando que cualquier conjunto de tamaño menor que A ^ε _n (en el sentido del exponente) cubriría un conjunto de probabilidad acotado lejos de 1 .

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

${\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 deduce de la desigualdad de Gibbs y la quinta línea se deduce 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, según la desigualdad de Kraft, existe un código sin prefijos que tiene esas longitudes de palabra. Por lo tanto, el S mínimo 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}}}$

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