En teoría de la información , el teorema de codificación de fuente de Shannon (o teorema de codificación silenciosa ) establece los límites a la posible compresión de datos y el significado operativo de la entropía de Shannon .
Nombrado en honor a Claude Shannon , el teorema de codificación de fuente muestra que (en el límite, como la longitud de un flujo de datos de variables aleatorias (iid) independientes e idénticamente distribuidos tiende a infinito) es imposible comprimir los datos de manera que la tasa de código (número medio de bits por símbolo) es menor que la entropía de Shannon de la fuente, sin que sea prácticamente seguro que se perderá información. Sin embargo, es posible conseguir que la tasa de código se acerque arbitrariamente 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ímbolo coloca un límite superior e inferior en la longitud mínima esperada posible de palabras de código en función de la entropía de la palabra de entrada (que se considera una variable aleatoria ) y del tamaño del alfabeto de destino.
Declaraciones
La codificación de origen es un mapeo de (una secuencia de) símbolos de una fuente de información a una secuencia de símbolos alfabéticos (generalmente bits) de modo que los símbolos de origen se pueden recuperar exactamente de los bits binarios (codificación de origen sin pérdidas) o recuperar con cierta distorsión ( codificación de fuente con pérdida). Este es el concepto detrás de la compresión de datos .
Teorema de codificación de fuente
En la teoría de la información, el teorema de la codificación de la fuente (Shannon 1948) [1] establece informalmente que (MacKay 2003, pág. 81, [2] Cover 2006, Capítulo 5 [3] ):
N i.id variables aleatorias, cada una con entropía H ( X ) se puede comprimir en más de N H ( X ) bits con un riesgo insignificante de pérdida de información, ya que N → ∞ ; pero a la inversa, si se comprimen en menos de N H ( X ) bits, es prácticamente seguro que se perderá información.
Teorema de codificación fuente para códigos de símbolos
Deje Σ 1 , Σ 2 denotan dos alfabetos finitos y dejar Σ∗
1y Σ∗
2denotar el conjunto de todas las palabras finitas de esos alfabetos (respectivamente).
Suponga que X es una variable aleatoria que toma valores en Σ 1 y sea f un código decodificable unívocamente de Σ ∗
1a Σ∗
2donde | Σ 2 | = a . Sea S la variable aleatoria dada por la longitud de la palabra de código f ( X ) .
Si f es óptimo en el sentido de que tiene la longitud de palabra mínima esperada para X , entonces (Shannon 1948):
Dónde denota el operador de valor esperado .
Prueba: teorema de codificación de fuentes
Dado que X es una fuente iid , su serie de tiempo X 1 , ..., 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. La Fuente teorema de codificación indica que para cualquier ε > 0 , es decir, para cualquier tasa de H ( X ) + ε mayor que la entropía de la fuente, no es lo suficientemente grande n y un codificador que toma n repetición iid de la fuente, X 1: n , y lo asigna a n ( H ( X ) + ε ) bits binarios de modo que los símbolos de origen X 1: n sean recuperables de los bits binarios con una probabilidad de al menos 1 - ε .
Prueba de alcanzabilidad. Arregle algunos ε > 0 y deje
El conjunto típico, Aε
n, se define de la siguiente manera:
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, como definido se acerca a uno. En particular, para n suficientemente grande , puede hacerse arbitrariamente cerca de 1, y específicamente, mayor que (Ver AEP para una prueba).
La definición de conjuntos típicos implica que aquellas secuencias que se encuentran en el conjunto típico satisfacen:
Tenga en cuenta que:
- La probabilidad de una secuencia siendo extraído de Aε
nes mayor que 1 - ε . - , que sigue desde el lado izquierdo (límite inferior) para .
- , que se sigue del límite superior para y el límite inferior de la probabilidad total de todo el conjunto Aε
n.
Desde los bits son suficientes para apuntar a cualquier cadena de este conjunto.
El algoritmo de codificación: el codificador comprueba si la secuencia de entrada se encuentra dentro del conjunto típico; si es así, genera el índice de la secuencia de entrada dentro del conjunto típico; si no, el codificador genera un número arbitrario de n ( H ( X ) + ε ) dígitos. Siempre que la secuencia de entrada se encuentre dentro del conjunto típico (con probabilidad de al menos 1 - ε ), el codificador no comete ningún error. Entonces, la probabilidad de error del codificador está acotada arriba por ε .
Prueba de Converse. Lo contrario se demuestra al mostrar que cualquier conjunto de tamaño menor que Aε
n(en el sentido de exponente) cubriría un conjunto de probabilidad limitada a 1 .
Prueba: teorema de codificación fuente para códigos de símbolos
Para 1 ≤ i ≤ n, denotemos s i la longitud de palabra de cada posible x i . Definir, donde C se elige de modo que q 1 + ... + q n = 1 . Luego
donde la segunda línea se sigue de la desigualdad de Gibbs y la quinta línea se sigue de la desigualdad de Kraft :
entonces log C ≤ 0 .
Para la segunda desigualdad podemos establecer
así que eso
y entonces
y
y así, por la desigualdad de Kraft, existe un código sin prefijo que tiene esas longitudes de palabra. Así, el mínimo S satisface
Extensión a fuentes independientes no estacionarias
Codificación de fuente sin pérdidas de tasa fija para fuentes independientes no estacionarias de tiempo discreto
Definir el conjunto típico Aε
n como:
Entonces, para dado δ > 0 , para n lo suficientemente grande, Pr ( Aε
n)> 1 - δ . Ahora solo codificamos las secuencias en el conjunto típico, y los métodos habituales en la codificación fuente muestran que la cardinalidad de este conjunto es menor que. Por tanto, en promedio, H n ( X ) + ε bits son suficientes para codificar con probabilidad mayor que 1 - δ , donde ε y δ pueden hacerse arbitrariamente pequeños, haciendo n más grande.
Ver también
Referencias
- ^ CE Shannon , " Una teoría matemática de la comunicación ", Bell System Technical Journal , vol. 27, págs. 379–423, 623-656, julio, octubre de 1948
- ^ David JC MacKay. Teoría de la información, inferencia y algoritmos de aprendizaje Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
- ^ Portada, Thomas M. (2006). "Capítulo 5: Compresión de datos". Elementos de la teoría de la información . John Wiley e hijos. ISBN 0-471-24195-4.