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

editar

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
donde2| = a. Sea S la variable aleatoria dada por la longitud de la palabra clavef (X).

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

 

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-ε.
  •  
  •     

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.

Véase también

editar

Referencias

editar
  1. Claude Shannon (julio de 1948). «A Mathematical Theory of Communication». Bell Labs Technical Journal. .
  2. 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
  3. David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
  4. Cover, Thomas M. (2006). «Chapter 5: Data Compression». Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4. 

Enlaces externos

editar