Teoremele lui Shannon pentru o sursă fără memorie

Teoremele lui Shannon pentru o sursă fără memorie raportează entropia sursei și posibilitatea comprimării prin codificare cu pierderi urmată de decodificare ambiguă .

Teorema directă arată că cu codare cu pierderi este posibil să se obțină un raport de compresie

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

în mod arbitrar apropiat de entropia sursei, dar tot mai mare decât cea din urmă. Reversul arată că cel mai bun rezultat nu este atins.

Enunțul teoremelor

Lasă dat:

$U$ - unele surse de mesaje, precum și setul tuturor mesajelor sale $u_{1},u_{2},...,u_{K)$
$\Omega$ este setul tuturor secvențelor de intrare de lungime , care este împărțit în: $L$
- $M_{L}$ este setul de secvențe de intrare de decodificare fără ambiguitate
- $M_{L}^{C)$ este setul de secvențe de intrare de decodificare ambiguă
$D$ — numărul de litere din alfabetul codificatorului (în mesaje după codare)
$N$ — lungimea mesajului după codificare

Teorema directă

Pentru o sursă fără memorie cu entropie și oricare , există o secvență de seturi de decodare unice de putere , astfel încât probabilitatea unui set de decodare ambiguu tinde spre zero pe măsură ce lungimea blocului crește . Cu alte cuvinte, compresia este posibilă. $U$ $H\stanga(U\dreapta)$ $\varepsilon >0$ $M_{L}$ $2^{L\left({1+\varepsilon}\right)H\left(U\right))$ $P\stanga({M_{L}^{C}}\dreapta)\la 0$ $L\la \infty$

Teorema inversă

Fie o sursă fără memorie cu entropie și orice . Pentru orice secvență de seturi de decodare de putere fără ambiguitate, probabilitatea unui set de decodare ambiguu tinde spre unitate pe măsură ce lungimea blocului crește . Cu alte cuvinte, compresia nu este posibilă. $U$ $H\stanga(U\dreapta)$ $\varepsilon _{1}>0$ $M_{L}$ $2^{L\left({1-\varepsilon _{1}}\right)H\left(U\right))$ $P\stanga({M_{L}^{C}}\dreapta)\la 1$ $L\la \infty$

Literatură

Gabidulin E. M. , Pilipchuk N. I. Capitolul 6. Codarea cu pierderi // Prelegeri despre teoria informației - MIPT , 2007. - P. 89-93. — 214 p. — ISBN 978-5-7417-0197-3