Primer teorema de Shannon

En teoría de la información, el teorema de codificación de fuentes, primer teorema de Shannon o, menos utilizado, teorema de codificación sin ruido es un teorema enunciado por Claude Shannon en 1948 que establece el límite teórico para la compresión de una fuente de datos,^[1]​ así como el significado operacional de la entropía de Shannon.

El primer teorema de Shannon demuestra que, en el límite de una cadena de variables aleatorias independientes e idénticamente distribuidas de datos que tiende a infinito, es imposible comprimir la información de forma que la relación de codificación (número medio de bits por símbolo) sea menor que la entropía de Shannon de la fuente, si se garantiza que no haya pérdida de información. Sin embargo, sí es posible conseguir una relación de codificación arbitrariamente cerca del valor de la entropía de Shannon.

El primer teorema de Shannon establece una cota inferior y superior de la longitud mínima posible de bits de información como función de la entropía.

Enunciado

La codificación de una fuente es una correspondencia entre una secuencia de símbolos de una fuente de información y una secuencia de símbolos de un alfabeto (generalmente bits) de forma que los símbolos de la fuente pueden ser recuperados posteriormente de forma exacta desde los bits binarios (codificación sin pérdidas) o recuperarla con alguna distorsión (codificación con pérdidas), pero que sigan siendo entendibles. Este es el concepto detrás de la compresión de datos.

Primer teorema de Shannon

En la Teoría de la Información, el primer teorema de Shannon (Shannon 1948)^[2]​ informalmente expresa que: (MacKay 2003, p. 81.^[3]​ Cover 2006, Capítulo 5.^[4]​):

N i.i.d. variables aleatorias cada una con una entropía H(X) puede ser comprimida en más de N H(X) bits con un riesgo despreciable de pérdida de información , segúnN → ∞; pero a la inversa, si son comprimidos en menos de N H(X) bits es prácticamente seguro que se produce pérdida de información.

Primer teorema de Shannon para códigos simbólicos

Sean Σ₁, Σ₂ dos alfabetos finitos y sean Σ∗
1 y Σ∗
2 los conjuntos finitos de palabras de esos alfabetos (respectivamente).

Suponga que X es una variable aleatoria tomando valores en Σ₁ y sea  f  un código singularmente decodificable desdeΣ∗
1 aΣ∗
2 donde|Σ₂| = a. Sea S la variable aleatoria dada por la longitud de la palabra clave f (X).

Si f  es óptimo en el sentido de que tiene la longitud de palabra clave 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}$

Demostración: Teorema de codificación de la fuente

Sea X una fuente de variables aleatorias independientes idénticamente distribuidas (i.i.d.), su serie temporal X₁,…,X_n es también i.i.d. con entropía H(X) en el caso discreto y entropía diferencial en el caso continuo.

El teorema de codificación fuente establece que para cualquier ε>0 hay una cantidad suficientemente grande n y un codificador que toma n i.i.d repeticiones de la fuente, X^1:n, y lo lleva a ${\displaystyle n{\bigl (}H{\bigl (}X{\bigr )}+\varepsilon {\bigr )}}$bits binarios de tal manera que los símbolos fuente X^1:n son recuperables de los bits binarios con probabilidad de al menos 1-ε.

Demostración de su accesibilidad: Arregla algunos  y deja

${\displaystyle p{\bigl (}x_{1},...,x_{n}{\bigl )}=P_{r}[X_{1}=x_{1},...,X_{n}=x_{n}]}$

El conjunto típico ${\displaystyle A_{n}^{\varepsilon }}$se define como:

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

La propiedad de equipartición asintótica muestra que para cantidades suficientemente grandes de n, la probabilidad de que una secuencia generada por la fuente se encuentre en dicho conjunto se acerca a uno.

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

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

Nótese que:

• La probabilidad de que una secuencia  ${\displaystyle (X_{1},...,X_{n})}$ sea extraída de ${\displaystyle A_{n}^{\varepsilon }}$ es mayor que 1-ε.
• ${\displaystyle |A_{n}^{\varepsilon }|\leq 2^{-n(H(X)+\varepsilon )}}$
• ${\displaystyle |A_{n}^{\varepsilon }|\leq (1-\varepsilon )2^{-n(H(X)-\varepsilon )}}$   

Ya que ${\displaystyle |A_{n}^{\varepsilon }|\leq 2^{-n(H(X)+\varepsilon )}}$, ${\displaystyle n(H(X)+\varepsilon )}$ bits son suficientes para señalar cualquier cadena en este conjunto. La demostración inversa se realiza mostrando que cualquier conjunto menor que ${\displaystyle A_{n}^{\varepsilon }}$ (en el sentido de exponente), cubriría un conjunto de probabilidades limitadas desde 0.

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

Para ${\displaystyle 1\leq i\leq n}$, ${\displaystyle s_{i}}$ representa la longitud de la palabra para cada ${\displaystyle x_{i}}$ posible. Se define ${\displaystyle q_{i}=a^{-s_{i}}/C}$ donde ${\displaystyle C}$ es una constante de normalización elegida de forma que ${\displaystyle q_{i}+...+q_{n}=1}$. Entonces:

${\displaystyle 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\leq \mathbb {E} Slog_{2}a}$

Donde la segunda línea viene dada por la desigualdad de Gibbs y la quinta por la desigualdad de Kraft.

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

Por lo que ${\displaystyle log_{2}C\leq 0}$.

Para la segunda desigualdad, se establece que:

${\displaystyle s_{i}=-log_{a}p_{i}}$

por lo que:

${\displaystyle -log_{a}p_{i}\leq s_{i}\leq -log_{a}p_{i}+1}$

por tanto:

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

y por la desigualdad de Kraft, hay un código sin prefijo que tiene esa longitud de palabra. Esta S mínima satisface:

${\displaystyle \mathbb {E} S=\sum p_{i}s_{i}<\sum p_{i}(-log_{a}p_{i}+1)=\sum -p_{i}{\frac {log_{2}p_{i}}{log_{2}a}}+1}$

Extensión a fuentes independientes no estacionarias

En primer lugar definimos una base típica como ${\displaystyle A_{n}^{\varepsilon }}$

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

Entonces, dada una δ >0, con n suficientemente grande ${\displaystyle P_{r}(A_{n}^{\varepsilon })<1-\delta }$. Ahora solo hay que codificar las secuencias en la base típica, y los métodos más usuales de codificación muestran que la dimensión de esta base es menor que${\displaystyle 2^{n(H(x)+\varepsilon )}}$. De esta forma, en promedio bits ${\displaystyle H(X)+\varepsilon }$ son suficientes para codificar con probabilidad mayor que 1- δ, donde ${\displaystyle \varepsilon }$ y δ pueden escogerse tan pequeños como se quiera, para un n muy grande.

Véase también

• Paradoja de Freedman
• Desigualdad de Jensen
• Segundo teorema de Shannon
• Teorema de Shannon-Hartley

Referencias

Bibliografía

• Cover T. M., Thomas J. A., Elementos of Information Theory, John Wiley & Sonidos, 1991. ISBN 0-471-06259-6
• Fano, R. A., Transmission of information; a statistical theory of communications, MIT Press, 1961. ISBN 0-262-06001-9
• Feinstein, Amiel, "A New basic theorem of information theory", IEEE Transactions donde Information Theory, 4(4): 2-22, 1954.
• MacKay, David J. C., Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003. ISBN 0-521-64298-1 [disponible en línea]
• Shannon, C. E., A Mathematical Theory of Communication Archivado el 31 de enero de 1998 en Wayback Machine. Urbana, IL: University of Illinois Press, 1949 (reprinted 1998).
• Wolfowitz, J., "The coding of messages subject tono chance errores", Illinois J. Math., 1: 591–606, 1957.

Enlaces externos

• Esta obra contiene una traducción derivada de «Théorème du codage de source» de Wikipedia en francés, concretamente de esta versión del 24 de enero de 2010, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.
• CE Shannon, "A Mathematical Theory of Communication", Bello System Technical Journal, vol. 27, pp. 379-423, julio de 1948.
• Donde Shannon and Shannon's law. Archivado el 15 de marzo de 2016 en Wayback Machine.
• Shannon's Noisy Channel Coding Theorem.