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

Из Википедије, слободне енциклопедије

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

Дискретан извор без меморије[уреди]

Дискретан извор без меморије (енгл. 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}] \le NH+o(N)

где сума иде по A_n

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

Негативан став[уреди]

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

<l_n> < NH

Доказ[уреди]

Позитиван став[уреди]

Све N-торке из A_n могу се једнозначно кодовати бинатним l_n'-торкама уколико је

2^{ln'-1}<r^N  \le 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)}]

\le 1+(l_n)+(l_n')P[\overrightarrow{a}\in \overline{S(N,e)}]

па добијамо

\le NH+Ne+2+ Nldr\sigma^2/Ne^2

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

<l_n> \le 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}]\le 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}])

\le\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'}]}\le1

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

NH\le<l_n>

Извори[уреди]

  1. ^ C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379-423, 623-656, July, October, 1948
  2. ^ David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press. 2003. ISBN 978-0-521-64298-9. pp.
  3. ^ Cover, Thomas M. (2006). „Chapter 5: Data Compression“. Elements of Information Theory. John Wiley & Sons. ISBN 978-0-471-24195-9. 

Литература[уреди]

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

Спољашње везе[уреди]