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

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

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

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

Дискретен извор без меморија (англиски: discrete memoryless source - DMS) чиј изл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}}]$$\leq$$NH+o(N)$

каде сумата оди по $A_{n}$

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

Негативен став

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

$<l_{n}><NH$

Доказ

Позитивен став

Сите N-торки од $A_{n}$ може еднозначно да се кодираат со бинарни $l_{n}'$-торки доколку

$2^{ln'-1}<r^{N}$ $\leq$ $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}>=(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)}}]$

па се добива

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

и за е=$N^{1/3}$ се добива

$<l_{n}>\leq 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}}]\leq 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}}])$

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

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

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

$NH\leq <l_{n}>$

Литература

• Cover, Thomas M. (2006). „Chapter 5: Data Compression“. Elements of Information Theory. John Wiley & Sons. ISBN 978-0-471-24195-9.CS1-одржување: ref=harv (link)

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

• FTN Novi Sad, Teorija informacija i komunikacija