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

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

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

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

[уреди | уреди извор]

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

Кодирање

[уреди | уреди извор]

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

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

[уреди | уреди извор]

За DMS со алфабет А и ентропија Н(А)=Н за секое N од множеството природни броеви пости еднозначно декодабилен код кој се состои од бинарни секвенци со должина , a е вектор од (n-торка од A) Σ

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

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

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

[уреди | уреди извор]

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

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

[уреди | уреди извор]

Сите N-торки од може еднозначно да се кодираат со бинарни -торки доколку

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

Нека се подели на подмножества и

Како во лемата АЕР секој елемент од може да се кодира со

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

за сигурно да се добие префиксен код на секој елемент од му се доделува 0, а на елемент од 1.

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

па се добива

и за е= се добива

па

o(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

Литература

[уреди | уреди извор]
  • 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)

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

[уреди | уреди извор]