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

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

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

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

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

Кодирање

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

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

За DMS со алфабет А и ентропија Н(А)=Н за секое N од множеството природни броеви пости еднозначно декодабилен код кој се состои од бинарни секвенци со должина ${\displaystyle l_{n}[{\overrightarrow {a}}]}$, a е вектор од ${\displaystyle A_{n}}$(n-торка од A) ${\displaystyle <l_{n}>=}$ Σ${\displaystyle P_{n}[{\overrightarrow {a}}]l_{n}[{\overrightarrow {a}}]}$${\displaystyle \leq }$${\displaystyle NH+o(N)}$

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

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

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

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

${\displaystyle <l_{n}><NH}$

Доказ

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

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

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

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

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

Нека ${\displaystyle A_{n}}$ се подели на подмножества ${\displaystyle S(N,e)}$ и ${\displaystyle {\overline {S(N,e)}}}$

Како во лемата АЕР секој елемент од ${\displaystyle S(N,e)}$ може да се кодира со ${\displaystyle l_{n}}$

каде според АЕP тоа изнесува

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

за сигурно да се добие префиксен код на секој елемент од ${\displaystyle S(N,e)}$ му се доделува 0, а на елемент од ${\displaystyle {\overline {S(N,e)}}}$ 1.

Просечната должина на вака добиен код е:

${\displaystyle <l_{n}>=(l_{n}+1)P[{\overrightarrow {a}}\in S(N,e)]+(l_{n}'+1)P[{\overrightarrow {a}}\in {\overline {S(N,e)}}]}$

${\displaystyle =1+(l_{n})P[1-{\overrightarrow {a}}\in {\overline {S(N,e)}}]+(l_{n}')P[{\overrightarrow {a}}\in {\overline {S(N,e)}}]}$

${\displaystyle \leq 1+(l_{n})+(l_{n}')P[{\overrightarrow {a}}\in {\overline {S(N,e)}}]}$

па се добива

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

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

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

па

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

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

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

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

Се дефинира распределба

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

и следи

${\displaystyle NH(A)=\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]*ld(1/P_{n}[{\overrightarrow {a}}])}$

${\displaystyle \leq \sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]*ld(1/Q_{n}[{\overrightarrow {a}}])}$

${\displaystyle =\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]*ld\sum _{A}^{}2^{-l_{n}[{\overrightarrow {a'}}]}/2^{-l_{n}[{\overrightarrow {a}}]}}$

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

познато е дека ${\displaystyle <l_{n}>=\sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]l_{n}[{\overrightarrow {a}}]}$

${\displaystyle \sum _{A_{n}}^{}P_{n}[{\overrightarrow {a}}]ld\sum _{A}^{}2^{-l_{n}[{\overrightarrow {a'}}]}\leq 1}$

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

${\displaystyle NH\leq <l_{n}>}$

Наводи

1. C.E. Shannon, "A Mathematical Theory of Communication Архивирано на 16 февруари 2009 г.", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
2. David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge. Предлошка:Page1.
3. Cover 2006 harvnb error: no target: CITEREFCover2006 (help)

Литература

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

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

• FTN Novi Sad, Teorija informacija i komunikacija