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.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.En la Teoría de la Información, el primer teorema de Shannon (Shannon 1948)[2]​ informalmente expresa que: (MacKay 2003, p.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.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): Sea X una fuente de variables aleatorias independientes idénticamente distribuidas (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 abits 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 dejal o g p (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: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.representa la longitud de la palabra para cadaDonde la segunda línea viene dada por la desigualdad de Gibbs y la quinta por la desigualdad de Kraft.Para la segunda desigualdad, se establece que:y por la desigualdad de Kraft, hay un código sin prefijo que tiene esa longitud de palabra.En primer lugar definimos una base típica comol o g ( p ) (Entonces, dada una δ >0, con n suficientemente grandeAhora 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 queDe esta forma, en promedio bitsson suficientes para codificar con probabilidad mayor que 1- δ, dondey δ pueden escogerse tan pequeños como se quiera, para un n muy grande.