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

мини|Бинарен канал за бришење
**Првата Шенонова теорема** ги воспоставува границите на можната компресија на податоци, и ѝ дава практично значење на Шеноновата ентропија. Оваа теорема ја докажал Клод Шенон во 1948 година, и заклучил дека не е можно да се изврши компресија, а просечниот број битови по симбол да биде помал од ентропијата на изворот на дадените симболи или ќе дојде до губење на информација. Меѓутоа можно е да се врши компресија при што бројот на битови по симбол ќе биде приближен на ентропијата на  изворот со мала веројатност за губење информација. Поточно, оваа теорема покажува дека со кодирање на секвенци од изворот со помош на код со одреден алфабет може сигурно со декодирање да се добијат изворните симболи.

## Дискретен извор без меморија
Дискретен извор без меморија () чиј излeз е случајна променлива a, која зема реализации од конечен алфабет А=(а1, а2... ар) со веројатности P[i], i=1,2...n. Симболите се појавуваат по некој случаен распоред, во константни или променливи временски растојанија.

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

### Позитивен став
За DMS со алфабет А и ентропија Н(А)=Н за секое N од множеството природни броеви пости еднозначно декодабилен код кој се состои од бинарни секвенци со должина l_n[\overrightarrow{a}], a е вектор од A_n(n-торка од A)
 = *Σ* P_n[\overrightarrow{a}]l_n[\overrightarrow{a}] \le NH+o(N)

каде сумата оди по A_n

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

### Негативен став
Не постои случај да

 

## Доказ
### Позитивен став
Сите N-торки од A_n  може еднозначно да се кодираат со бинарни l_n'-торки доколку

2^{ln'-1}  \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+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} се добива

 \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

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

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

познато е дека
 = \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

## Наводи

## Литература
* 

## Надворешни врски
* FTN Novi Sad, Teorija informacija i komunikacija

Категорија:Математички теореми
Категорија:Теорија на информациите
Категорија:Теорија на кодирањето
Категорија:Збивање на податоци