Teoremas de Shannon para una fuente sin memoria

Los teoremas de Shannon para una fuente sin memoria relacionan la entropía de la fuente y la posibilidad de compresión por codificación con pérdida seguida de decodificación ambigua .

El teorema directo muestra que con codificación con pérdida es posible lograr una relación de compresión

{\frac {N}{L}}\approx {\frac {H\left(U\right)\left({1+\varepsilon }\right)}{\log _{2}D}}

arbitrariamente cerca de la entropía de la fuente, pero aún mayor que la última. Lo contrario muestra que el mejor resultado no es alcanzable.

Enunciado de los teoremas

Sea dado:

$tu$ - alguna fuente de mensajes, así como el conjunto de todos sus mensajes ${\displaystyle u_{1},u_{2},...,u_{K))$
$\Omega$ es el conjunto de todas las secuencias de entrada de longitud , que se divide en: $L$
- ${\ estilo de visualización M_ {L}}$ es el conjunto de secuencias de entrada de decodificación inequívoca
- $M_{L}^{C}$ es el conjunto de secuencias de entrada de decodificación ambigua
$D$ — número de letras en el alfabeto del codificador (en mensajes después de la codificación)
$norte$ — longitud del mensaje después de la codificación

teorema directo

Para una fuente sin memoria con entropía y cualquiera , hay una secuencia de conjuntos de decodificación únicos de potencia tal que la probabilidad de un conjunto de decodificación ambiguo tiende a cero a medida que aumenta la longitud del bloque . En otras palabras, la compresión es posible. $tu$ ${\ estilo de visualización H \ izquierda (U \ derecha)}$ $\varepsilon >0$ ${\ estilo de visualización M_ {L}}$ ${\displaystyle 2^{L\left({1+\varepsilon }\right)H\left(U\right)))$ $P\left({M_{L}^{C}}\right)\to 0$ $L\a\infty$

teorema inverso

Deje que una fuente sin memoria con entropía y cualquier . Para cualquier secuencia de conjuntos de decodificación de potencia inequívocos, la probabilidad de un conjunto de decodificación ambiguo tiende a la unidad a medida que aumenta la longitud del bloque . En otras palabras, la compresión no es posible. $tu$ ${\ estilo de visualización H \ izquierda (U \ derecha)}$ ${\ estilo de visualización \ varepsilon _ {1}> 0}$ ${\ estilo de visualización M_ {L}}$ ${\displaystyle 2^{L\left({1-\varepsilon _{1}}\right)H\left(U\right)))$ $P\left({M_{L}^{C}}\right)\to 1$ $L\a\infty$

Literatura

Gabidulin E. M. , Pilipchuk N. I. Capítulo 6. Codificación con pérdida // Conferencias sobre teoría de la información - MIPT , 2007. - P. 89-93. — 214 págs. — ISBN 978-5-7417-0197-3