Shannonovy teorémy pro zdroj bez paměti

Shannonovy teorémy pro zdroj bez paměti se týkají entropie zdroje a možnosti komprese ztrátovým kódováním následovaným nejednoznačným dekódováním .

Přímá věta ukazuje, že se ztrátovým kódováním je možné dosáhnout kompresního poměru

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

libovolně blízko k entropii zdroje, ale stále větší než ten druhý. Opak ukazuje, že nejlepšího výsledku nelze dosáhnout.

Prohlášení teorémů

Nechte si dát:

$U$ - nějaký zdroj zpráv, stejně jako soubor všech jeho zpráv ${\displaystyle u_{1},u_{2},...,u_{K))$
$\Omega$ je množina všech vstupních sekvencí délky , která se dělí na: $L$
- $M_{L}$ je množina vstupních sekvencí jednoznačného dekódování
- ${\displaystyle M_{L}^{C))$ je množina vstupních sekvencí nejednoznačného dekódování
$D$ — počet písmen v abecedě kodéru (ve zprávách po zakódování)
$N$ — délka zprávy po zakódování

Přímá věta

Pro bezpaměťový zdroj s entropií a kterýkoli jiný existuje posloupnost výkonově jedinečných dekódovacích sad tak, že pravděpodobnost nejednoznačné dekódovací sady má sklon k nule , jak se délka bloku zvětšuje . Jinými slovy, komprese je možná. $U$ $H\left(U\right)$ $\varepsilon >0$ $M_{L}$ ${\displaystyle 2^{L\left({1+\varepsilon }\right)H\left(U\right)))$ $P\left({M_{L}^{C}}\right)\to 0$ $L\to \infty$

Inverzní věta

Nechte zdroj bez paměti s entropií a jakýmkoliv . Pro libovolnou sekvenci jednoznačných výkonových dekódovacích sad má pravděpodobnost nejednoznačné dekódovací množiny tendenci k jednotce , jak se zvyšuje délka bloku . Jinými slovy, komprese není možná. $U$ $H\left(U\right)$ $\varepsilon _{1}>0$ $M_{L}$ ${\displaystyle 2^{L\left({1-\varepsilon _{1}}\right)H\left(U\right)))$ $P\left({M_{L}^{C}}\right)\to 1$ $L\to \infty$

Literatura

Gabidulin E. M. , Pilipchuk N. I. Kapitola 6. Ztrátové kódování // Lectures on Information Theory - MIPT , 2007. - S. 89-93. — 214 s. — ISBN 978-5-7417-0197-3