Shannon tételei egy emlékezet nélküli forráshoz

Shannon tételei a memória nélküli forrásra vonatkoznak a forrás entrópiájára és a veszteséges kódolással történő tömörítés lehetőségére, amelyet kétértelmű dekódolás követ .

A direkt tétel azt mutatja, hogy veszteséges kódolással lehet elérni a tömörítési arányt

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

tetszőlegesen közel áll a forrás entrópiájához , de még mindig nagyobb, mint az utóbbi. A fordítottja azt mutatja, hogy a legjobb eredmény nem érhető el.

A tételek állítása

Adva legyen:

$U$ - valamilyen üzenetforrás, valamint annak összes üzenete ${\displaystyle u_{1},u_{2},...,u_{K))$
$\Omega$ az összes hosszúságú bemeneti sorozat halmaza , amely a következőkre oszlik: $L$
- $M_{L}$ az egyértelmű dekódolás bemeneti sorozatainak halmaza
- $M_{L}^{C}$ a kétértelmű dekódolás bemeneti sorozatainak halmaza
$D$ — betűk száma a kódoló ábécéjében (a kódolás utáni üzenetekben)
$N$ — üzenet hossza a kódolás után

Direkt tétel

Egy entrópiával rendelkező memória nélküli forrás esetén létezik egy teljesítmény egyedi dekódoló készlet sorozata, így a kétértelmű dekódoló készlet valószínűsége a blokk hosszának növekedésével nullára hajlik . Más szóval, tömörítés lehetséges. $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$

Inverz tétel

Legyen egy memória nélküli forrás entrópiával és bármilyen . Az egyértelmű teljesítmény- dekódoló készletek bármely sorozata esetén a kétértelmű dekódoló készlet valószínűsége egységnyire hajlamos a blokk hosszának növekedésével . Más szavakkal, a tömörítés nem lehetséges. $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$

Irodalom

Gabidulin E. M. , Pilipchuk N. I. 6. fejezet: Veszteséges kódolás // Előadások az információelméletről - MIPT , 2007. - P. 89-93. — 214 p. — ISBN 978-5-7417-0197-3