Shannons teorem för en minneslös källa

Shannons teorem för en minneslös källa relaterar källans entropi och möjligheten till komprimering genom förlustkodning följt av tvetydig avkodning .

Den direkta satsen visar att med förlustkodning är det möjligt att uppnå ett kompressionsförhållande

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

godtyckligt nära källans entropi , men ändå större än den senare. Det omvända visar att det bästa resultatet inte kan uppnås.

Uttalande av satserna

Låt ges:

$U$ - någon källa till meddelanden, såväl som uppsättningen av alla dess meddelanden ${\displaystyle u_{1},u_{2},...,u_{K))$
$\Omega$ är uppsättningen av alla inmatningssekvenser av längd , som är uppdelad i: $L$
- $M_{L}$ är uppsättningen av ingångssekvenser för entydig avkodning
- ${\displaystyle M_{L}^{C))$ är uppsättningen av ingångssekvenser av tvetydig avkodning
$D$ — antal bokstäver i kodaralfabetet (i meddelanden efter kodning)
$N$ — meddelandelängd efter kodning

Direkt sats

För en minneslös källa med entropi och vilken som helst finns det en sekvens av effektunika avkodningsuppsättningar så att sannolikheten för en tvetydig avkodningsuppsättning tenderar till noll när blocklängden ökar . Med andra ord, komprimering är möjlig. $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$

Omvänd teorem

Låt en minneslös källa med entropi och eventuella . För varje sekvens av entydiga effektavkodningsuppsättningar tenderar sannolikheten för en tvetydig avkodningsuppsättning att bli enhet när blocklängden ökar . Med andra ord, komprimering är inte möjlig. $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$

Litteratur

Gabidulin E. M. , Pilipchuk N. I. Kapitel 6. Lossy Coding // Föreläsningar om informationsteori - MIPT , 2007. - P. 89-93. — 214 sid. — ISBN 978-5-7417-0197-3