Prva Šenonova teorema

Prva Šenonova teorema je uspostavlja granice moguće kompresije podataka, i daje praktično značenje Šenonove entropije. Ovu teoremu je 1948. dokazao Klod Elvud Šenon, i zaključio je da je nemoguće izvršiti kompresiju a da prosečan broj bita po simbolu bude manji od entopije izvora datih simbola, ili će doći do gubitka informacije. Međutim moguće je vršiti kompresiju gde će broj bita po simbolu biti približan entropiji izvora sa malo verovatnoćom gubitka informacije. Tačnije, ova teorema pokazuje da kodovanjem sekvenci sa izvora pomoću koda sa određenim alfabetom možemo sigurno dekodovanjem dobiti izvorne simbole.

Diskretan izvor bez memorije

Diskretan izvor bez memorije (engl. discrete memoryless source - DMS) čiji izlaz je slučajna promjenjiva a, koja uzima realizacije iz konačnog alfabeta А=(а1, а2... ар) sa verovatnoćama P[i], i=1,2...n. Simboli se pojavljuju nekim slučajnim rasporedom, u konstantnim ili promenjivim vremenskim razmacima.

Kodovanje

Kod je prevođenje niza ulaznih simbola u niz izlaznih simbola. Kod je jednoznačno dekodabilan ukoliko ne postoje dve kodne reči konačne dužine koje čine istu sekvencu, blaži kriterijum je da ni jedna reč nije prefiks druge.

Pozitivan stav

Za DMS sa alfabetom A i entropijom Н(А)=Н za svako N iz skupa prirodnih brojeva postoji jednoznačno dekodabilan kod koji se sastoji od binarnih sekvenci dužine $l_{n}[{\overrightarrow {a}}]$, a je vektor iz $A_{n}$(n-torka iz A) $<l_{n}>=$ Σ$P_{n}[{\overrightarrow {a}}]l_{n}[{\overrightarrow {a}}]$$\leq$$NH+o(N)$

gde suma ide po $A_{n}$

Očekivana dužina kodnih reči. о(N) predstavlja član koji sa N raste sporije od linearno.

Negativan stav

Ne postoji slučaj da je

$<l_{n}><NH$

Dokaz

Pozitivan stav

Sve N-torke iz $A_{n}$ mogu se jednoznačno kodovati binatnim $l_{n}'$-torkama ukoliko je

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

odakle sledi da

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

Podelimo $A_{n}$ na podskupove $S(N,e)$ i ${\overline {S(N,e)}}$

kao u АЕР lemi svaki element iz $S(N,e)$ možemo kodovati sa $l_{n}$

gde prema АЕP to iznosi

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

da bi sigurno dobili prefiksan kod svakom elementu iz $S(N,e)$ dodelimo 0, a elementu iz ${\overline {S(N,e)}}$ 1.

Prosečna dužina ovako dobijenog koda je:

$<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)}}]$

pa dobijamo

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

i za e=$N^{1/3}$ dobijemo

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

pa je

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

funkcija koja raste sporije nego linearno i sledi da je

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

Negativan stav

Definišimo raspodelu

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

i sledi

$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'}}]}$

poznato je da $<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$

prema Kraft MakMilanovoj nejednakosti sledi

$NH\leq <l_{n}>$

Literatura

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

Spoljašnje veze

• FTN Novi Sad, Teorija informacija i komunikacija