Прва Шенонова теорема

Прва Шенонова теорема је успоставља границе могуће компресије података, и даје практично значење Шенонове ентропије. Ову теорему је 1948. доказао Клод Елвуд Шенон, и закључио је да је немогуће извршити компресију а да просечан број бита по симболу буде мањи од ентопије извора датих симбола, или ће доћи до губитка информације. Међутим могуће је вршити компресију где ће број бита по симболу бити приближан ентропији извора са мало вероватноћом губитка информације. Тачније, ова теорема показује да кодовањем секвенци са извора помоћу кода са одређеним алфабетом можемо сигурно декодовањем добити изворне симболе.

Дискретан извор без меморије

Дискретан извор без меморије (енгл. discrete memoryless source - DMS) чији излаз је случајна промјењива a, која узима реализације из коначног алфабета А=(а1, а2... ар) са вероватноћама P[i], i=1,2...n. Симболи се појављују неким случајним распоредом, у константним или промењивим временским размацима.

Кодовање

Код је превођење низа улазних симбола у низ излазних симбола. Код је једнозначно декодабилан уколико не постоје две кодне речи коначне дужине које чине исту секвенцу, блажи критеријум је да ни једна реч није префикс друге.

Позитиван став

За DMS са алфабетом А и ентропијом Н(А)=Н за свако N из скупа природних бројева постоји једнозначно декодабилан код који се састоји од бинарних секвенци дужине $l_{n}[{\overrightarrow {a}}]$, a је вектор из $A_{n}$(n-торка из A) $<l_{n}>=$ Σ$P_{n}[{\overrightarrow {a}}]l_{n}[{\overrightarrow {a}}]$$\leq$$NH+o(N)$

где сума иде по $A_{n}$

Очекивана дужина кодних речи. о(N) представља члан који са N расте спорије од линеарно.

Негативан став

Не постоји случај да је

$<l_{n}><NH$

Доказ

Позитиван став

Све N-торке из $A_{n}$ могу се једнозначно кодовати бинатним $l_{n}'$-торкама уколико је

$2^{ln'-1}<r^{N}$ $\leq$ $2^{ln'}$

одакле следи да

$l_{n}'=Nld(r)$

Поделимо $A_{n}$ на подскупове $S(N,e)$ и ${\overline {S(N,e)}}$

као у АЕР леми сваки елемент из $S(N,e)$ можемо кодовати са $l_{n}$

где према АЕP то износи

$l_{n}=N(H+e)$

да би сигурно добили префиксан код сваком елементу из $S(N,e)$ доделимо 0, а елементу из ${\overline {S(N,e)}}$ 1.

Просечна дужина овако добијеног кода је:

$<l_{n}>=(l_{n}+1)P[{\overrightarrow {a}}\in S(N,e)]+(l_{n}'+1)P[{\overrightarrow {a}}\in {\overline {S(N,e)}}]$

$=1+(l_{n})P[1-{\overrightarrow {a}}\in {\overline {S(N,e)}}]+(l_{n}')P[{\overrightarrow {a}}\in {\overline {S(N,e)}}]$

$\leq 1+(l_{n})+(l_{n}')P[{\overrightarrow {a}}\in {\overline {S(N,e)}}]$

па добијамо

$\leq NH+Ne+2+Nldr\sigma ^{2}/Ne^{2}$

и за е=$N^{1/3}$ добијемо

$<l_{n}>\leq NH+N^{2/3}+2+(N^{2/3}ldr+N^{-1/3}ldr)\sigma ^{2}$

па је

o(N)$=N^{2/3}+2+(N^{2/3}ldr+N^{-1/3}ldr)\sigma ^{2}$

функција која расте спорије него линеарно и следи да је

$<l_{n}>=\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]l_{n}[{\overrightarrow {a}}]\leq NH+o(N)$

Негативан став

Дефинишимо расподелу

$Q_{n}[{\overrightarrow {a}}]=2^{-l_{n}[{\overrightarrow {a}}]}/\sum _{A}^{}2^{-l_{n}[{\overrightarrow {a'}}]}$

и следи

$NH(A)=\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]*ld(1/P_{n}[{\overrightarrow {a}}])$

$\leq \sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]*ld(1/Q_{n}[{\overrightarrow {a}}])$

$=\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]*ld\sum _{A}^{}2^{-l_{n}[{\overrightarrow {a'}}]}/2^{-l_{n}[{\overrightarrow {a}}]}$

$=\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]l_{n}[{\overrightarrow {a}}]+\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]ld\sum _{A}^{}2^{-l_{n}[{\overrightarrow {a'}}]}$

познато је да $<l_{n}>=\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]l_{n}[{\overrightarrow {a}}]$

$\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]ld\sum _{A}^{}2^{-l_{n}[{\overrightarrow {a'}}]}\leq 1$

према Крафт МакМилановој неједнакости следи

$NH\leq <l_{n}>$

Литература

• Cover, Thomas M. (2006). „Chapter 5: Data Compression”. Elements of Information Theory. John Wiley & Sons. ISBN 978-0-471-24195-9. 

Спољашње везе

• FTN Novi Sad, Teorija informacija i komunikacija