„Teoria informațiilor și a codificării. Teorema directă a lui Shannon pentru o sursă de formă generală

Pentru utilizare eficientă canal (creșterea factorului de încărcare λ→1), este necesară coordonarea acestuia cu sursa de informații la intrare. O astfel de potrivire este posibilă pentru ambele canale fără interferență și cu interferență, pe baza teoremelor de codificare a canalelor propuse de Shannon.

Teorema de codificare pentru un canal fără interferențe.

Dacă sursa mesajului are o capacitate [bit/sec], iar canalul de comunicație are o capacitate [bit/sec], atunci puteți codifica mesajul în așa fel încât să transmiteți informații prin canalul de comunicație la o viteză medie, în mod arbitrar aproape de valoare, dar nu o depășește.

Shannon a propus, de asemenea, o metodă pentru o astfel de codare, care a fost numită codare optimă. Ideea unei astfel de codări a fost dezvoltată ulterior în lucrările lui Fano și Huffman. În prezent, astfel de coduri sunt utilizate pe scară largă în practică (codare eficientă și optimă).

Teorema de codare directă a lui Shannon pentru un canal zgomotos.

Pentru orice performanță a sursei de mesaj [bit/sec] mai mică decât debitul [bit/sec], există o metodă de codare care permite transmiterea tuturor informațiilor create de sursa de mesaj cu o probabilitate de eroare ε arbitrar mică.

Teorema de codificare inversă pentru un canal zgomotos.

Nu există o metodă de codare care să permită transmiterea informațiilor cu orice probabilitate de eroare dacă performanța sursei mesajului este mai mare lățime de bandă canal.

Dovada teoremei de codificare pentru un canal cu zgomot este destul de lungă din punct de vedere matematic, așa că ne vom limita la o discuție generală a aspectelor fizice ale acestuia. aplicare practică:

1. Teorema stabilește limita teoretica posibilă eficiență a sistemului cu transmitere fiabilă a informațiilor. Din teoremă rezultă că interferența în canal nu impune restricții privind acuratețea transmisiei. Restricțiile sunt impuse numai asupra vitezei de transmisie la care poate fi atinsă fiabilitatea transmisiei arbitrar ridicată.

În același timp, fiabilitatea canal discret este de obicei estimată prin valoarea probabilității de recepție eronată a unui simbol. Cu cât probabilitatea de eroare este mai mică, cu atât este mai mare fiabilitatea canalului. Fiabilitatea, la rândul său, caracterizează imunitatea la zgomot sistem informatic.

Viteza transferului de informații caracterizează eficiența sistemului.

2. Teorema nu abordează problema modalităților de construire a codurilor care asigură transmisia ideală specificată. După ce a fundamentat posibilitatea fundamentală a unei astfel de codări, ea a mobilizat eforturile oamenilor de știință pentru a dezvolta coduri specifice.

3. La orice viteză finită de transmitere a informațiilor, până la debit, o probabilitate de eroare arbitrar mică este atinsă numai cu o creștere nelimitată a duratei secvențelor codificate de caractere. Astfel, transmisia fără erori în prezența interferenței este posibilă doar teoretic. Asigurarea transmiterii de informații cu o probabilitate de eroare foarte mică și cu o eficiență destul de mare este posibilă atunci când se codifică secvențe extrem de lungi de caractere.

Teorema directă a lui Shannon pentru sursă vedere generală A nu se confunda cu alte teoreme Shannon.

Teoremele lui Shannon pentru o sursă generală descrieți posibilitățile de codificare a unei surse generale folosind coduri separabile. Cu alte cuvinte, sunt descrise capabilitățile maxime de codare fără pierderi realizabile.

Teorema directă

Când este aplicată codificării literă cu literă, teorema directă poate fi formulată după cum urmează:

Pentru a demonstra teorema, sunt examinate caracteristicile codului Shannon-Fano. Acest codîndeplinește condițiile teoremei și are proprietățile indicate.

Teorema inversă

Teorema inversă limitează raportul de compresie maxim care poate fi realizat cu codificare fără pierderi. Când se aplică codării literă cu literă, descrie limitarea lungimii medii cuvânt cod pentru orice cod separabil.

Pentru orice cod separabil cu lungimi w 1 ,w 2 ,...,w K lungimea medie a mesajului este mai mare sau egală cu entropia sursei U, normalizat la logaritmul binar al numărului de litere Dîn alfabetul codificatorului:

Literatură

• Gabidulin, E. M., Pilipchuk, N. I.§3.4 Teoremele lui Shannon pentru sursă // Prelegeri de teoria informației. - M.: MIPT, 2007. - p. 49-52. - 214 p. - ISBN 5-7417-0197-3

Fundația Wikimedia.

2010.

Vedeți ce este „teorema directă a lui Shannon pentru o sursă de formă generală” în alte dicționare:

A nu se confunda cu alte teoreme Shannon. Teoremele lui Shannon pentru o sursă generală descriu posibilitățile de codificare a unei surse generale folosind coduri separabile. Cu alte cuvinte, sunt descrise posibilitățile maxime realizabile... ... Wikipedia

Claude Elwood Shannon (n. 30 aprilie 1916, Petoskey, Michigan, Michigan, SUA, 24 februarie 2001, Medford, Massachusetts, SUA) matematician și inginer electrician american, unul dintre creatorii teoriei matematice... ... Wikipedia

Claude Elwood Shannon (n. 30 aprilie 1916, Petoskey, Michigan, Michigan, SUA, 24 februarie 2001, Medford, Massachusetts, SUA) matematician și inginer electrician american, unul dintre creatorii teoriei matematice... ... Wikipedia

- (engleză Claude Elwood Shannon; născut la 30 aprilie 1916, Petoskey, Michigan, Michigan, SUA, decedat la 24 februarie 2001, Medford, Massachusetts, SUA) Matematician și inginer electrician american, unul dintre creatorii teoriei informației matematice, în . .. ... Wikipedia

Claude Elwood Shannon (n. 30 aprilie 1916, Petoskey, Michigan, Michigan, SUA, 24 februarie 2001, Medford, Massachusetts, SUA) matematician și inginer electrician american, unul dintre creatorii teoriei matematice... ... Wikipedia

Claude Elwood Shannon (n. 30 aprilie 1916, Petoskey, Michigan, Michigan, SUA, 24 februarie 2001, Medford, Massachusetts, SUA) matematician și inginer electrician american, unul dintre creatorii teoriei matematice... ... Wikipedia

Claude Elwood Shannon (n. 30 aprilie 1916, Petoskey, Michigan, Michigan, SUA, 24 februarie 2001, Medford, Massachusetts, SUA) matematician și inginer electrician american, unul dintre creatorii teoriei matematice... ... Wikipedia

Programul cursului

„Teoria informației și codării”

Prelegerile sunt susținute în anul 4, semestrul VII,

51 de ore, lector conf. univ

Conceptul de informație, entropie. Sisteme de comunicații. Surse discrete. Descrierea sursei folosind proces aleatoriu. Independenta statistica. surse Markov. Ergodicitatea. Ergodicitatea sursei Bernoulli.

Derivarea formulei entropiei (după Fadeev). Informații reciproce și proprietățile sale. Proprietățile entropiei. Teorema despre valoarea maxima entropie. Entropia pe unitatea de timp a sursei mesajului.

Problema codificării unei surse discrete cu coduri lungime egală. Viteza de codare. Seturi de mare probabilitate. Teoreme directe și inverse pentru codificarea unei surse discrete cu coduri de lungime egală.

Problema codificării unei surse cu coduri de lungime inegală. Costul de codare. Coduri fără ambiguitate descifrabile. Coduri de prefix. Codare literă cu literă. O condiție necesară și suficientă pentru descifrabilitatea unică a unui cod. Codurile complete. Teoremă pentru codificarea unei surse discrete cu coduri de lungime inegală. Algoritmi pentru construirea codurilor optime (Fano, Shannon, Huffman). Construirea unui cod binar optim cu o distribuție de probabilitate egală a probabilităților de intrare. Aplicarea teoriei informațiilor are ca rezultat demonstrarea limitelor inferioare și superioare pentru complexitatea implementării Funcții booleeneîn unele clase de sisteme de control. O metodă pentru construirea unui cod optim cu condiția ca distribuția de probabilitate a literelor sursă să fie necunoscută. Teorema lui Markov privind descifrabilitatea unică a unui cod. Algoritmi adaptativi pentru compresia informatiilor.

Canal discret fără memorie. Binar canal simetric. Viteza de transmitere a informațiilor pe canal. Capacitatea canalului. Canal extins și capacitatea acestuia. Modele decisive și grupări de observații. Posibilitatea transmiterii eronate de informații. inegalitatea lui Feinstein. Teoremă directă pentru codificarea canalelor fără memorie. inegalitatea lui Fano. Teorema procesării informației. Inversarea teoremei de codificare.

Teoria codării rezistente la zgomot. Criteriul de maximă probabilitate. Distanța codului. Codurile de paritate. generativ și verificarea matricelor. Sindromul. Algoritm de decodare pentru codurile de verificare a parității. Codurile liniareși algoritmul lor de decodare. Hamming legat. Cod Hamming. Codurile ciclice. Codificarea și decodificarea codurilor ciclice.

LITERATURĂ

1. Gallagher R. Teoria informaţiei şi conexiune de încredere., M., Sov. Radio, 1979.

2. Krichevsky E. Prelegeri despre teorie și informație, Novosibirsk, NSU, 1966.

3. Kolesnik V., Poltyrev G. Curs de teoria informaţiei, Nauka, 1982.

4. Fainstein A. Fundamentals of Information Theory, M., IL, 1960.

5. Peterson V., Weldon F. Codurile de corectare a erorilor, M., Mir, 1976.

6. Teoria codificării algebrice Berlekamp, ​​M., Mir, 1971.

Capacitatea informațională a canalelor discrete (4.4) și capacitatea canalelor continue (4.7) caracterizează capacitățile maxime ale acestora ca mijloace de transmitere a informațiilor. Ele sunt relevate în teoremele fundamentale ale teoriei informației, care sunt cunoscute ca teoremele fundamentale ale codificării Shannon. În legătură cu un canal discret, scrie:

Teorema 4.4.1. (Teorema de codare directă pentru DKBP.) Pentru un canal discret fără memorie la rate de cod R, mai mică decât capacitatea de informare, există întotdeauna un cod pentru care probabilitatea medie de eroare tinde spre zero pe măsură ce lungimea cuvântului cod crește.

În cazul unui canal continuu se formulează ca

Teorema 4.4.2. (Teorema de codare directă pentru canalul AWGN). Pe un canal AWGN cu lățime de bandă nelimitată, informațiile pot fi transmise cu o probabilitate de eroare arbitrar scăzută dacă viteza de transmisie este mai mică decât lățimea de bandă.

Teorema inversă spune:

Teorema 4.4.3. La baud rate
, capacitate mai mare a canalului de comunicare C, niciun cod nu va oferi o probabilitate arbitrar de mică de eroare de decodificare, adică transmiterea mesajului absolut fiabilă.

Trebuie remarcat faptul că, dacă teorema inversă este dovedită pentru un model arbitrar al unui canal de comunicare, atunci cea directă este dovedită numai pentru anumite tipuri de canale.

Rezultatele teoremelor de codare pentru un canal zgomotos sunt oarecum neașteptate. Într-adevăr, la prima vedere, se pare că reducerea probabilității erorilor în transmiterea mesajelor necesită o reducere corespunzătoare a ratei de transmisie și că aceasta din urmă ar trebui să tindă la zero împreună cu probabilitatea erorilor. Această concluzie, în special, rezultă din luarea în considerare a retransmisiei multiple de simboluri pe un canal ca o modalitate de a reduce probabilitatea erorilor în transmiterea mesajelor. În acest caz, în prezența interferenței în canalul de comunicație, este posibil să se asigure că probabilitatea de eroare în transmiterea mesajului tinde spre zero numai dacă viteza de transmisie tinde spre zero.

Cu toate acestea, teorema de codare arată că, în principiu, este posibil să se transmită cu o viteză arbitrar apropiată de C, obținând în același timp o probabilitate de eroare arbitrar mică. Din păcate, teoremele, deși indică existența fundamentală a unui cod rezistent la erori, nu oferă o rețetă pentru a-l găsi. Putem doar să remarcăm că pentru aceasta este necesar să folosiți coduri lungi. Mai mult, pe măsură ce viteza de transmisie se apropie de debitul și probabilitatea erorilor scade, codul devine mai complex datorită creșterii lungimii blocurilor, ceea ce duce la o complicație accentuată a dispozitivelor de codificare și decodare, precum și la o întârziere în ieșirea de informații în timpul decodării. Metodele de codare utilizate în prezent, care vor fi discutate mai târziu, nu realizează capabilitățile potențiale ale sistemului de comunicații. Singura excepție sunt codurile turbo deschise recent.

1Acest rezultat este valabil pentru orice canale simetrice.

Codificarea informațiilor

Concepte de bază

Teoremele lui Shannon privind codificarea mesajelor au fost menționate mai sus. Este intuitiv clar că codificarea este operația de conversie a informațiilor în forma necesară procesării ulterioare (transmitere pe un canal de comunicare, stocare în memorie sistem de calcul, utilizarea pentru luarea deciziilor etc.). De asemenea, este clar că la construirea oricărui sistem informațional este imposibil să se facă fără codificare: orice prezentare a informațiilor implică utilizarea unui fel de coduri. Prin urmare, vom analiza în continuare în detaliu fundamente teoretice codificarea informațiilor.

Lasă O– alfabet arbitrar. Elemente alfabetice O sunt numite litere (sau simboluri), iar secvențele finite formate din litere sunt numite cuvinte în O. Se crede că în orice alfabet există un cuvânt gol care nu conține litere.

Cuvânt α 1 se numește începutul (prefixul) unui cuvânt α , dacă cuvântul există α 2, astfel încât α = α 1 α 2; în acelaşi timp cuvântul α 1 se numește începutul propriu al unui cuvânt α , Dacă α 2 nu este un cuvânt gol. Lungimea cuvântului este numărul de litere din cuvânt (un cuvânt gol are lungimea 0). Înregistra α 1 α 2 denotă legătura (concatenarea) cuvintelor α 1 și α 2. Cuvânt α 2 se numește terminația (sufixul) unui cuvânt α , dacă cuvântul există α 1, astfel încât α = α 1 α 2; în acelaşi timp cuvântul α 2 se numește finalul propriu al unui cuvânt α , Dacă α 1 nu este un cuvânt gol. Un cuvânt gol este, prin definiție, considerat începutul și sfârșitul oricărui cuvânt α .

Luați în considerare alfabetul B = {0, 1, …, D– 1), unde D≥ 2 și o mulțime arbitrară C. Afișarea arbitrară a unui set Cîn multe cuvinte din alfabet B numit D-ar set codificare C(la D= 2 codificarea va fi binară). Maparea inversă se numește decodare. Să dăm exemple de codificări.

1. Codificarea mulţimii numerelor naturale, în care numărul n= 0 se potrivește cu cuvântul e(0) = 0 și numărul n ≥ 1 cuvânt binar

e(n) = b 1 b 2 … b l (n)

cea mai scurtă lungime care satisface condiția

Este evident că b 1 = 1, 2l (n) – 1 ≤ n < 2l (n) și prin urmare

l(n) = + 1 = ]log( n + 1)[,

Unde [ x] și ] x[ denotă, respectiv, cel mai mare număr întreg care nu depășește x, iar cel mai mic număr întreg mai mare decât x. Cuvânt e(n) se numește notația binară a unui număr n, iar această codificare este reprezentarea numerelor în sistem binar Socoteala. Această codificare este unu-la-unu pentru că când n 1 ≠ n 2 cuvinte e(n 1) și e(n 2) diferit. Tabelul 5.1 arată reprezentarea primelor 16 numere naturale din sistemul numeric binar.

Tabelul 5.1

Codificarea e(n)

n	e(n)	n	e(n)	n	e(n)	n	e(n)

2. Codificarea primelor 2 k numere naturale, pentru care fiecare număr n (0 ≤ n < 2k) se potrivește cu cuvântul

e k(n) = 0k – l (n) e(n),

unde intrarea 0 k – l (n) denotă un cuvânt format din k – l(n) zerouri, e(n) – reprezentarea unui număr nîn sistemul de numere binar discutat mai sus. Această codificare este pentru primele 16 numere naturale ( k= 4) este dat în tabelul 5.2.

Tabelul 5.2

Codificarea e k(n)

n	e k(n)	n	e k(n)	n	e k(n)	n	e k(n)

Lasă O = {un i, i= 1, 2, ...) – un alfabet finit sau de numărare, ale cărui litere sunt numerotate numere naturale. În acest caz, codificarea literelor alfabetului O poate fi specificată prin succesiune D-cuvinte literale V = {v i, i= 1, 2, …), unde v i există o imagine a unei scrisori un i. Astfel de secvențe de cuvinte (din set V) se numesc coduri (ale alfabetului O). Dacă este dat codul V alfabet O, apoi codificarea cuvintelor, în care fiecare cuvânt un i 1 un i 2 …un ik se potrivește cu cuvântul v i 1 v i 2 …v ik, numită codificare literă cu literă.

Când treceți de la codificarea unu-la-unu a literelor alfabetului la codificarea literă cu literă a cuvintelor din alfabet, este posibil ca proprietatea caracterului unu-la-unu să nu fie păstrată. De exemplu, codificare e(n) nu salvează această proprietate, și codificare e k(n) îl salvează. Proprietatea unu-la-unu este păstrată prin coduri separabile. Cod V = {v i, i= 1, 2, …) se numește separabil dacă din fiecare egalitate a formei

v i 1 v i 2 …v ik = v j 1 v j 2 …vjl

rezultă că l = kŞi v i 1 = v j 1 , v i 2 = v j 2 , … , v ik = vjl. Codurile separabile sunt numite și coduri unic decodabile.

Codurile de prefix aparțin clasei de coduri separabile. Cod V = {v i, i= 1, 2, …) se numește prefix dacă nu există un cuvânt vk nu este începutul (prefixul) niciunui cuvânt v l, l ≠ k. Dacă fiecare cuvânt al unui cod de prefix este înlocuit cu cel mai mic început, care nu este începutul altor cuvinte de cod, atunci codul rezultat va fi și un prefix. Această operație se numește trunchierea codului de prefix.

Pentru cod arbitrar V, format din cuvinte diferite, puteți construi un arbore de cod. Acesta este un grafic direcționat care nu conține cicluri, în care vârful β 1 conectat la partea de sus β 2 margine îndreptată din β 1 la β 2 dacă și numai dacă β 2 = β 1 b, Unde b Î B = {0, 1, …, D – 1}, D≥ 2. Pentru codurile de prefix (și numai pentru acestea), setul de cuvinte de cod coincide cu setul de vârfuri de sfârșit (vârfurile din care nu provin muchii) arborele de coduri.

Teoreme de codare de bază

Proprietățile codurilor care sunt utile pentru aplicarea lor practică sunt determinate de teoremele de codare de bază.

Teorema 5.1. Inegalitatea lui Kraft. Pentru existența unui cod unic decodabil (separabil) care conține N cuvinte de cod din set (0, 1, D– 1) cu lungimi n 1 , n 2 , …, n N, este necesar și suficient ca inegalitatea să se mențină

Dovada. Să ne imaginăm că avem un arbore de cod pentru un cod de prefix. Rădăcina arborelui de cod formează nivelul 0, vârfurile asociate cu forma rădăcină nivelul 1 etc. Numărul posibil de vârfuri per k-al-lea nivel îl notăm ca Dk. Fiecare vârf k nivelul apare exact Dn – k culmi n- al-lea nivel.

n 1 ≤ n 2 ≤…≤ n N = n.

Evident, cuvântul de cod al lungimii k interzice exact Dn – k posibile vârfuri de capăt (vârfurile ultimului nivel). Apoi toate cuvintele cod ale codului prefix interzic vârfurile de sfârșit. Deoarece numărul total vârfurile de capăt sunt egale Dn, atunci inegalitatea este adevărată

,

din care rezultă că

Astfel, inegalitatea lui Kraft este dovedită.

Ca rezultat al demonstrației teoremei 5.1, se ajunge la concluzia că există cel puțin coduri de prefix care sunt coduri decodabile în mod unic cu lungimi de cuvinte de cod. n 1 , n 2 , …, n N, satisfăcând inegalitatea lui Kraft. Următoarea teoremă, numită afirmația lui McMillan, generalizează această concluzie pentru toate codurile unic decodabile.

Teorema 5.2. inegalitatea lui McMillan. Fiecare cod decodabil unic satisface inegalitatea lui Kraft.

Dovada. Să ridicăm suma la o putere L:

. (5.1)

Lasă A k– numărul de combinaţii care conţin L cuvinte de cod cu lungime totală k. Atunci expresia (6.1) poate fi reprezentată ca

,

Unde L max – lungime maxima mesaje care conțin L cuvinte de cod. Dacă codul este unic decodabil, atunci toate secvențele de la L cuvinte cod de lungime totală k sunt diferite. Din moment ce există doar Dk secvențe posibile, atunci A k ≤ Dk si apoi

Deoarece L este numărul de cuvinte de cod independente care sunt utilizate pentru a construi toate secvențele posibile de lungime care nu depășește L max. De aceea L ≤ L max si . Și de aici rezultă că

Deoarece raționamentul de mai sus este valabil pentru fiecare cod decodabil unic și nu doar pentru codurile de prefix, afirmația lui McMillan este dovedită.

Următoarele teoreme relaționează entropia unei surse de mesaj și lungimea medie a unui cuvânt de cod.

Teorema 5.3. Teorema codării sursei I. Pentru orice sursă discretă fără memorie X cu alfabet finit și entropie H(X) există D-ichny cod prefix, în care lungimea medie a cuvântului de cod satisface inegalitatea

. (5.2)

Dovada.În primul rând, să clarificăm asta sursă discretă fără memorie, este descrisă de un model care nu ține cont de conexiunile dintre simbolurile mesajelor. Acum demonstrăm partea stângă a inegalității (6.2):

Pentru a face acest lucru, folosim definiția entropiei și a inegalității lui Kraft:

Pentru a demonstra partea dreaptă a inegalității (6.2), rescriem inegalitatea lui Kraft în următoarea formă:

.

Apoi alegem pentru fiecare termen cel mai mic număr întreg n i, la care

Deoarece inegalitatea lui Kraft rămâne aceeași cu această alegere, putem construi codul de prefix corespunzător. Deoarece n i este cel mai mic număr întreg, atunci pentru n i– 1 este corect

Astfel, teorema de codificare a sursei I este demonstrată. Determină că lungimea medie a unui cuvânt cod nu poate fi mai mică decât entropia sursei mesajului. Rețineți că demonstrația teoremei a folosit aceeași notație ca atunci când ați luat în considerare inegalitatea lui Kraft.

Teorema 5.4. Teorema Codării Sursei II. Pentru lungimea blocului L există D-cod prefix-ary în care lungimea medie a unui cuvânt de cod pe caracter satisface inegalitatea

,

Unde .

Dovada. Aici, blocuri de personaje și H(X 1 , X 2 , …, X L) este entropia sursei mesajului pe bloc de L personaje. Pentru a demonstra teorema, puteți folosi teorema de codificare sursă I:

În plus, deoarece lungimea minimă realizabilă a unui cuvânt de cod per simbol este valoarea , atunci când D= 2 redundanță de cod poate fi determinată prin formulă .

1 | |