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.^[1]^[2]^[3]

Diskretan izvor bez memorije uredi

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 uredi

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 uredi

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 uredi

Ne postoji slučaj da je

$<l_{n}><NH$

Dokaz uredi

Pozitivan stav uredi

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 uredi

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