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.
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
[editar]
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
[editar]
Sean Σ1, Σ2 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 Σ1 y sea f un código singularmente decodificable desdeΣ∗
1 aΣ∗
2 donde|Σ2| = 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7af710c13eb23a7c771ef38abd9939d3fc71e3e8)
Demostración: Teorema de codificación de la fuente
[editar]
Sea X una fuente de variables aleatorias independientes idénticamente distribuidas (i.i.d.), su serie temporal X1,…,Xn 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, X1:n, y lo lleva a
bits binarios de tal manera que los símbolos fuente X1:n son recuperables de los bits binarios con probabilidad de al menos 1-ε.
Demostración de su accesibilidad: Arregla algunos y deja
El conjunto típico
se define como:
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:
Nótese que:
- La probabilidad de que una secuencia
sea extraída de
es mayor que 1-ε.
![{\displaystyle |A_{n}^{\varepsilon }|\leq 2^{-n(H(X)+\varepsilon )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e860893e2bc7b6dcda00506d03330949a5f63a4)
Ya que
,
bits son suficientes para señalar cualquier cadena en este conjunto. La demostración inversa se realiza mostrando que cualquier conjunto menor que
(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
[editar]
Para
,
representa la longitud de la palabra para cada
posible. Se define
donde
es una constante de normalización elegida de forma que
. Entonces:
Donde la segunda línea viene dada por la desigualdad de Gibbs y la quinta por la desigualdad de Kraft.
Por lo que
.
Para la segunda desigualdad, se establece que:
por lo que:
por tanto:
y por la desigualdad de Kraft, hay un código sin prefijo que tiene esa longitud de palabra. Esta S mínima satisface:
Extensión a fuentes independientes no estacionarias
[editar]
En primer lugar definimos una base típica como
Entonces, dada una δ >0, con n suficientemente grande
. 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
. De esta forma, en promedio bits
son suficientes para codificar con probabilidad mayor que 1- δ, donde
y δ pueden escogerse tan pequeños como se quiera, para un n muy grande.
- ↑ Claude Shannon (julio de 1948). «A Mathematical Theory of Communication». Bell Labs Technical Journal. .
- ↑ C.E. Shannon, "A Mathematical Theory of Communication Archivado el 16 de febrero de 2009 en Wayback Machine.", Bell System Technical Journal, vol. 27, pp. 379-423, 623-656, July, October, 1948
- ↑ David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
- ↑ Cover, Thomas M. (2006). «Chapter 5: Data Compression». Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4.
- 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.