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

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

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

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

КодовањеУреди

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

Позитиван ставУреди

За DMS са алфабетом А и ентропијом Н(А)=Н за свако N из скупа природних бројева постоји једнозначно декодабилан код који се састоји од бинарних секвенци дужине  , a је вектор из  (n-торка из A)   Σ   

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

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

Негативан ставУреди

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

 

ДоказУреди

Позитиван ставУреди

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

     

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

 

Поделимо   на подскупове   и  

као у АЕР леми сваки елемент из   можемо кодовати са  

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

 

да би сигурно добили префиксан код сваком елементу из   доделимо 0, а елементу из   1.

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

 

 

 

па добијамо

 

и за е=  добијемо

 

па је

o(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..
  3. ^ Cover 2006

ЛитератураУреди

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

Спољашње везеУреди