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

Бинарен канал за бришење

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

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

Дискретен извор без меморија (Предлошка:Lang-en) чиј излeз е случајна променлива 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}^{\prime }$-торки доколку

$2^{l{n}^{\prime }-1}<r^N$ $\le$ $2^{l{n}^{\prime }}$

од што следува дека

${l_n}^{\prime }=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}^{\prime }+1)P[\overrightarrow{a}\in \overline{S(N,e)}]$

$=1+(l_n)P[1-\overrightarrow{a}\in \overline{S(N,e)}]+({l_n}^{\prime })P[\overrightarrow{a}\in \overline{S(N,e)}]$

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

па се добива

$\le NH+Ne+2+Nldr{\sigma }^2/N{e}^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^{\prime }}]}$

и следи

$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^{\prime }}]}/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^{\prime }}]}$

познато е дека $<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^{\prime }}]}\le 1$

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

$NH\le <l_n>$

Литература

• Предлошка:Наведена книга

Надворешни врски

• FTN Novi Sad, Teorija informacija i komunikacija