Shannonin lauseet muistittomasta lähteestä

Shannonin lauseet muistittomasta lähteestä liittyvät lähteen entropiaan ja mahdollisuuteen pakkaamiseen häviöisellä koodauksella , jota seuraa epäselvä dekoodaus .

Suora lause osoittaa, että häviöisellä koodauksella on mahdollista saavuttaa pakkaussuhde

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

mielivaltaisen lähellä lähteen entropiaa , mutta silti suurempi kuin jälkimmäinen. Käänteinen osoittaa, että paras tulos ei ole saavutettavissa.

Lauseet

Anna annettu:

$U$ - jokin viestilähde sekä kaikki sen viestit ${\displaystyle u_{1},u_{2},...,u_{K))$
$\Omega$ on kaikkien pituisten syötesekvenssien joukko , joka on jaettu: $L$
- $M_{L}$ on yksiselitteisen dekoodauksen tulosekvenssien joukko
- ${\displaystyle M_{L}^{C))$ on joukko monitulkintaisen dekoodauksen tulosekvenssejä
$D$ — kirjaimien lukumäärä kooderiaakkosissa (viesteissä koodauksen jälkeen)
$N$ — viestin pituus koodauksen jälkeen

Suora lause

Muistittomalle lähteelle , jolla on entropia ja mikä tahansa , on olemassa joukko ainutlaatuisia dekoodausjoukkoja siten , että moniselitteisen dekoodausjoukon todennäköisyys pyrkii nollaan lohkon pituuden kasvaessa . Toisin sanoen pakkaus on mahdollista. $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$

Käänteinen lause

Olkoon muistiton lähde , jossa on entropia ja mikä tahansa . Millä tahansa yksiselitteisten tehodekoodausjoukkojen sekvenssillä moniselitteisen dekoodausjoukon todennäköisyydellä on taipumus olla yhtenäinen lohkon pituuden kasvaessa . Toisin sanoen pakkaus ei ole mahdollista. $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$

Kirjallisuus

Gabidulin E. M. , Pilipchuk N. I. Luku 6. Häviöllinen koodaus // Luentoja informaatioteoriasta - MIPT , 2007. - S. 89-93. — 214 s. — ISBN 978-5-7417-0197-3