Direcționați teorema lui Shannon pentru o sursă generală. Teoremele lui Shannon de codificare pentru un canal de transmitere a informațiilor

Pentru utilizare eficientă canal (creșterea factorului de sarcină λ → 1), acesta trebuie să fie corelat cu sursa de informații de la intrare. O astfel de potrivire este posibilă atât pentru canalele zgomotoase, cât și pentru cele zgomotoase, pe baza teoremelor de codificare a canalelor propuse de Shannon.

Teorema de codare pentru un canal zgomotos.

Dacă sursa mesajelor are o performanță [bit / sec], iar canalul de comunicație are un debit [bit / sec], atunci puteți codifica mesajul astfel î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 sugerat, de asemenea, o metodă de astfel de codare, care se numește codare optimă. Mai târziu, ideea unei astfel de codări a fost dezvoltată î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 mesajului [bit / sec] mai puțin de debitului[bit/sec], există o astfel de metodă de codare care permite transmiterea tuturor informațiilor generate de sursa mesajului 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 de informații cu o probabilitate de eroare arbitrar scăzută dacă performanța sursei de mesaj este mai mare decât lățimea de bandă a canalului.

Dovada teoremei de codificare pentru un canal zgomotos este destul de voluminoasă din punct de vedere matematic, prin urmare, ne limităm la o discuție generală a aspectelor fizice ale acestuia. aplicație practică:

1. Teorema stabilește limita teoretică a eficienței posibile a sistemului cu transmitere fiabilă a informațiilor. Din teoremă rezultă că interferența canalului nu impune restricții asupra preciziei transmisiei. Limitările sunt impuse numai asupra ratei de transmisie la care poate fi atinsă o fiabilitate arbitrar de mare a transmisiei.

În acest caz, fiabilitatea canalului 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ă indicată. 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. Pentru orice rată finită de transfer de informații, până la debit, o probabilitate de eroare arbitrar mică este atinsă numai cu o creștere infinită a duratei secvențelor de caractere codificate. Astfel, transmisia fără erori în prezența interferenței este posibilă doar teoretic. Asigurarea transmiterii de informații cu o probabilitate foarte mică de eroare și cu o eficiență suficient de mare este posibilă atunci când se codifică secvențe de caractere extrem de lungi.

Lucrarea a fost adăugată pe site-ul: 30-03-2016

; culoare: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5. Codificarea informațiilor

; culoare: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.1. Concepte de bază

Teoremele de codificare a mesajelor lui Shannon au fost menționate mai sus. Este intuitiv clar că codarea este o operațiune de conversie a informațiilor într-o formă necesară procesării ulterioare (transmitere pe un canal de comunicare, stocare în memorie sistem de calcul, utilizare pentru luarea deciziilor etc.). De asemenea, este clar că atunci când se construiește orice sistem informațional, este imposibil să se facă fără codificare: orice reprezentare a informațiilor implică utilizarea unor coduri. Prin urmare, vom analiza în detaliu baza teoretica informații de codificare.

Fie A - alfabetul arbitrar. Elemente ale alfabetului A sunt numite litere (sau simboluri), iar secvențele finite compuse din litere sunt numite cuvinte în A ... În acest caz, se consideră că în orice alfabet există un cuvânt gol care nu conține litere.

Cuvântul α 1 numit începutul (prefixul) unui cuvântα dacă există un cuvânt a 2 astfel încât a = a 1 a 2; în plus, cuvântul α 1 numit propriul început al cuvântuluiα 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). Înregistrareα 1 α 2 denotă legătura (concatenarea) cuvintelorα 1 și α 2. Cuvântul α 2 numită terminația (sufixul) unui cuvântα dacă există un cuvânt a 1, astfel încât a = a 1 a 2; în plus, cuvântul α 2 numit propriul lor final al cuvântuluiα 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șare set arbitrar C într-o varietate de cuvinte din alfabet B sunați pe D -prin codificarea setului C (pentru D = 2 codificarea va fi binară). Maparea inversă se numește decodare. Iată câteva exemple de codificări.

1. Codificarea unui set de numere naturale, în care numărul n = 0 se potrivește cu cuvântul e (0) = 0, iar numărul n ≥ 1 cuvânt binar

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

lungimea cea mai scurtă care satisface condiția

Evident, b 1 = 1, 2 l (n) - 1 ≤ n< 2 l (n ) prin urmare

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

unde [x] și] x [indică, 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ântul e (n ) se numește notația binară a numărului n , iar codificarea dată este reprezentarea numerelor în sistem binar socoteala. Această codificare este unu-la-unu, deoarece pentru n 1 ≠ n 2 cuvinte e (n 1) și e (n 2 ) sunt diferite. Tabelul 5.1 arată reprezentarea primelor 16 numere naturale din sistemul numeric binar.

"xml: lang =" ru-RU "lang =" ru-RU "> Tabelul 5.1

"xml: lang =" ru-RU "lang =" ru-RU "> Codificare"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" ru-RU "lang =" ru-RU "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" ru-RU "lang =" ru-RU ">)

"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)
"xml: lang =" en-US "lang =" en-US "> 0	"xml: lang =" en-US "lang =" en-US "> 0	"xml: lang =" en-US "lang =" en-US "> 4	"xml: lang =" en-US "lang =" en-US "> 100	"xml: lang =" en-US "lang =" en-US "> 8	"xml: lang =" en-US "lang =" en-US "> 1000	"xml: lang =" en-US "lang =" en-US "> 12	"xml: lang =" en-US "lang =" en-US "> 1100
"xml: lang =" en-US "lang =" en-US "> 1	"xml: lang =" en-US "lang =" en-US "> 1	"xml: lang =" en-US "lang =" en-US "> 5	"xml: lang =" en-US "lang =" en-US "> 101	"xml: lang =" en-US "lang =" en-US "> 9	"xml: lang =" en-US "lang =" en-US "> 1001	"xml: lang =" en-US "lang =" en-US "> 13	"xml: lang =" en-US "lang =" en-US "> 1101
"xml: lang =" en-US "lang =" en-US "> 2	"xml: lang =" en-US "lang =" en-US "> 10	"xml: lang =" en-US "lang =" en-US "> 6	"xml: lang =" en-US "lang =" en-US "> 110	"xml: lang =" en-US "lang =" en-US "> 10	"xml: lang =" en-US "lang =" en-US "> 1010	"xml: lang =" en-US "lang =" en-US "> 14	"xml: lang =" en-US "lang =" en-US "> 1110
"xml: lang =" en-US "lang =" en-US "> 3	"xml: lang =" en-US "lang =" en-US "> 11	"xml: lang =" en-US "lang =" en-US "> 7	"xml: lang =" en-US "lang =" en-US "> 111	"xml: lang =" en-US "lang =" en-US "> 11	"xml: lang =" en-US "lang =" en-US "> 1011	"xml: lang =" en-US "lang =" en-US "> 15	"xml: lang =" en-US "lang =" en-US "> 1111

2. Codificarea primelor 2 k numere naturale, pentru care fiecare număr n (0 ≤ n< 2 k ) cuvantul

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

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

"xml: lang =" ru-RU "lang =" ru-RU "> Tabelul 5."xml: lang =" en-US "lang =" en-US "> 2

"xml: lang =" ru-RU "lang =" ru-RU "> Codificare"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" ru-RU "lang =" ru-RU "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" ru-RU "lang =" ru-RU ">)

"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)	"xml: lang =" en-US "lang =" en-US "> n	"xml: lang =" en-US "lang =" en-US "> e; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> k"xml: lang =" en-US "lang =" en-US "> ("xml: lang =" en-US "lang =" en-US "> n"xml: lang =" en-US "lang =" en-US ">)
"xml: lang =" en-US "lang =" en-US "> 0	"xml: lang =" en-US "lang =" en-US "> 0000	"xml: lang =" en-US "lang =" en-US "> 4	"xml: lang =" en-US "lang =" en-US "> 0100	"xml: lang =" en-US "lang =" en-US "> 8	"xml: lang =" en-US "lang =" en-US "> 1000	"xml: lang =" en-US "lang =" en-US "> 12	"xml: lang =" en-US "lang =" en-US "> 1100
"xml: lang =" en-US "lang =" en-US "> 1	"xml: lang =" en-US "lang =" en-US "> 0001	"xml: lang =" en-US "lang =" en-US "> 5	"xml: lang =" en-US "lang =" en-US "> 0101	"xml: lang =" en-US "lang =" en-US "> 9	"xml: lang =" en-US "lang =" en-US "> 1001	"xml: lang =" en-US "lang =" en-US "> 13	"xml: lang =" en-US "lang =" en-US "> 1101
"xml: lang =" en-US "lang =" en-US "> 2	"xml: lang =" en-US "lang =" en-US "> 0010	"xml: lang =" en-US "lang =" en-US "> 6	"xml: lang =" en-US "lang =" en-US "> 0110	"xml: lang =" en-US "lang =" en-US "> 10	"xml: lang =" en-US "lang =" en-US "> 1010	"xml: lang =" en-US "lang =" en-US "> 14	"xml: lang =" en-US "lang =" en-US "> 1110
"xml: lang =" en-US "lang =" en-US "> 3	"xml: lang =" en-US "lang =" en-US "> 0011	"xml: lang =" en-US "lang =" en-US "> 7	"xml: lang =" en-US "lang =" en-US "> 0111	"xml: lang =" en-US "lang =" en-US "> 11	"xml: lang =" en-US "lang =" en-US "> 1011	"xml: lang =" en-US "lang =" en-US "> 15	"xml: lang =" en-US "lang =" en-US "> 1111

Fie A = (a i, i = 1, 2, ...) - un alfabet finit sau numărabil, ale cărui litere sunt numerotate numere naturale... În acest caz, codificarea literelor alfabetului A poate fi setat în ordine Cuvintele D -are 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 (alfabet A ). Dacă este dat codul V al alfabetului A , apoi codificarea cuvintelor în care fiecare cuvânt a i 1 a i 2 ... a ik se potrivește cu cuvântul v i 1 v i 2 ... v ik se numește codificare literă cu literă.

În trecerea de la codarea unu-la-unu a literelor alfabetului la codificarea literă cu literă a cuvintelor din alfabet, este posibil ca proprietatea unu-la-unu să nu fie păstrată. De exemplu, codificarea e (n ) nu conservă această proprietateși codificarea e k (n ) îl salvează. Codurile separabile păstrează proprietatea unu-la-unu. Codul 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… v jl

rezultă că l = k și v i 1 = v j 1, v i 2 = v j 2,…, v ik = v jl ... Codurile separabile sunt denumite și coduri decodificate unic.

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

Pentru cod arbitrar V constând din cuvinte diferite, puteți construi un arbore de cod. Este un grafic direcționat care nu conține cicluri, în care vârfulβ 1 conectat la vârfβ 2 margine îndreptată dinβ 1 până 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 terminale (vârfurile din care nu emană muchii) arborele de coduri.

5.2. Teoreme de codare de bază

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

Teorema 5.1. Inegalitatea lui Craft.Pentru existența unui cod decodat (separabil) unic care conține N cuvinte de cod din set (0, 1, D - 1) cu lungimile n 1, n 2, ..., n N , este necesar și suficient pentru inegalitate

Dovada. Imaginați-vă că aveți un arbore de cod pentru un cod de prefix. Rădăcina arborelui de cod este nivelul 0, nodurile asociate cu rădăcina sunt nivelul 1 și așa mai departe. Numărul posibil de vârfuri per k -al-lea nivel este notat ca D k. Fiecare vârf k -al-lea nivel generează exact D n - k vârfuri ale nivelului n -lea.

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

Evident, cuvântul de cod al lungimii k interzice exact D n - k posibile vârfuri de capăt (vârfurile ultimului nivel). Apoi toate cuvintele de cod ale codului de prefix interzic vârfurile de sfârșit. pentru că numărul total vârfurile de capăt este D n , apoi inegalitatea

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 unic decodabile cu lungimi de cuvinte de cod. n 1, n 2, ..., n N satisfacerea inegalității lui Kraft. Următoarea teoremă, numită afirmația lui McMillan, generalizează această concluzie la toate codurile decodificate unic.

Teorema 5.2. Inegalitatea McMillan.Fiecare cod decodat unic satisface inegalitatea Craft.

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

. (5.1)

Fie 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 mesaj care contine L cuvinte de cod. Dacă codul este decodat unic, atunci toate secvențele de la L cuvinte de cod de lungime totală k sunt diferite. Din moment ce există de toate D k secvențe posibile, atunci A k ≤ D k și apoi

Din moment ce 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. Prin urmare, L ≤ L max și. Și de aici rezultă că

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

Următoarele teoreme leagă entropia sursei mesajului și lungimea medie cuvânt cod.

Teorema 5.3. Teorema codării sursei eu. Pentru oricine sursă discretă fara memorie X cu alfabet finit și entropie H (X) există D -cod prefix ary în care lungimea medie a cuvântului de cod satisface inegalitatea

. (5.2)

Dovada. În primul rând, să clarificăm că o 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 aceasta, 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, pentru fiecare termen, alegem cel mai mic număr întreg n i pentru care

Deoarece inegalitatea lui Kraft este păstrată pentru această alegere, este posibil să se construiască codul de prefix corespunzător. pentru că n i Este cel mai mic număr întreg, atunci pentru n i - 1

Atunci

Deci teorema de codificare sursă eu dovedit. Determină că lungimea medie a unui cuvânt de cod nu poate fi mai mică decât entropia sursei mesajului. Rețineți că în demonstrarea teoremei am folosit aceeași notație ca și în considerarea inegalității lui Kraft.

Teorema 5.4. Teorema codării sursei II. Pentru un bloc de lungime L, există D -cod de prefix în care lungimea medie a cuvântului 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 la L personaje. Pentru a demonstra teorema, puteți folosi teorema de codificare sursă eu:

Teorema codării sursei II ne permite să afirmăm că există astfel de metode de codare pentru un mesaj suficient de lung încât lungimea medie a cuvântului de cod poate fi făcută arbitrar aproape de valoare. Într-adevăr, pentru L  ∞, H L (X)  H, unde H Este entropia sursei mesajului pentru un simbol, inegalitatea este adevărată

, (5.3)

Unde. Acest lucru poate fi interpretat și după cum urmează: pentru orice număr arbitrar micε , există o metodă de codificare a blocurilor care conțin simboluri, în care inegalitatea (5.3) este satisfăcută pentru lungimea medie a unui cuvânt de cod per simbol.

În plus, deoarece lungimea minimă a cuvântului de cod atins per simbol este valoarea, atunci pentru D = Redundanța cu 2 coduri poate fi determinată prin formulă.

; culoare: # 000000 "xml: lang =" ru-RU "lang =" ru-RU "> 5.3. Codificare optimă

Sarcina de a construi un cod optim este de a găsi numere întregi pozitive n 1, n 2, ..., n N minimizarea lungimii medii a cuvântului de cod, cu condiția ca inegalitatea lui Kraft să fie satisfăcută:

La construirea codurilor în cazul alfabetului A = (a i, i = 1, 2, ..., N ) cu o distribuție de probabilitate cunoscută P = (p i, i = 1, 2, ..., N ) fără pierderea generalității, putem presupune că literele alfabetului A sunt numerotate în ordinea descrescătoare a probabilităților lor, adică p 1 ≥ p 2 ≥… ≥ p N ... În plus, vom lua în considerare doar codurile binare.

Există două metode cunoscute (de Fano și Shannon) pentru a construi coduri care sunt aproape de optime. Metoda lui Fano este următoarea. Lista de litere, ordonată în ordinea descrescătoare a probabilităților, este împărțită în două părți consecutive, astfel încât sumele probabilităților literelor incluse în ele să difere cât mai puțin una de cealaltă. Literelor din prima parte li se atribuie caracterul 0, iar literelor din a doua parte - caracterul 1. În plus, același lucru se procedează cu fiecare dintre părțile primite, dacă conține, prin macar, două litere. Procesul continuă până când întreaga listă este împărțită în părți care conțin câte o literă fiecare. Fiecare literă este asociată cu o secvență de caractere atribuită ca rezultat al acestui proces acestei litere. Este ușor de observat că codul rezultat este prefixat.

Metoda lui Shannon este aplicabilă numai atunci când toate probabilitățile sunt pozitive. Constă în faptul că scrisoarea un i cu probabilitate p i > 0, o secvență din n i =] log (1 / p i ) [primele cifre după virgulă zecimală în extinderea numărului într-o fracție infinită (pentru a 1 presupunem că q 1 = 0). De la ora l> k (datorită faptului că p l ≤ p k) n l ≥ n k iar apoi codul obţinut în acest fel este prefixat. Pe baza codului de prefix obținut, se construiește un cod de prefix trunchiat, care este rezultatul codificării prin metoda Shannon.

De exemplu, să existe un set de litere A = (a 1, a 2, a 3, a 4, a 5, a 6, a 7 ) cu distribuția de probabilitate P = (0,2, 0,2, 0,19, 0,12, 0,11, 0,09, 0,09). Să efectuăm codificarea literelor folosind metoda Fano.

1. Împărțiți lista în două părți, astfel încât sumele probabilităților literelor incluse în ele să difere cât mai puțin una de cealaltă:

A 1 = (a 1, a 2, a 3), P 1 = (0,2, 0,2, 0,19);

A 2 = (a 4, a 5, a 6, a 7), P 2 = (0,12, 0,11, 0,09, 0,09).

2. Să atribuim simbolul 0 literelor din prima parte și simbolul 1 literelor din a doua parte:

A 1 = (a 1/0, a 2/0, a 3/0);

A 2 = (a 4/1, a 5/1, a 6/1, a 7/1).

3. Să repetăm ​​secvenţial actiuni specificate pentru fiecare parte separat. V ca rezultat obținem:

A 1 1 = (a 1/00);

A 121 = (a 2/010);

A 122 = (a 3/011);

A 211 = (a 4/100);

A 212 = (a 5/101);

A 221 = (a 6/110);

A 222 = (a 7/111).

Cuvintele de cod rezultate sunt afișate pentru fiecare literă în dreapta barei oblice. În acest caz, ordinea indicilor listelor cu o literă obținute arată succesiunea de împărțire a listei originale de grupuri în părți.

Procesul de codare Fano este formatat convenabil sub forma unui tabel. Pentru exemplul considerat, este prezentat în tabelul 5.3.

"xml: lang =" ru-RU "lang =" ru-RU "> Tabelul 5.3

"xml: lang =" ru-RU "lang =" ru-RU "> Codificare Fano

"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0,20	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 00
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 2	"xml: lang =" ru-RU "lang =" ru-RU "> 0,20		"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 010
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 3	"xml: lang =" ru-RU "lang =" ru-RU "> 0.19			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 011
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 4	"xml: lang =" ru-RU "lang =" ru-RU "> 0.12	"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 100
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 5	"xml: lang =" ru-RU "lang =" ru-RU "> 0.11			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 101
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 6	"xml: lang =" ru-RU "lang =" ru-RU "> 0,09		"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 0	"xml: lang =" ru-RU "lang =" ru-RU "> 110
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 7	"xml: lang =" ru-RU "lang =" ru-RU "> 0,09			"xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" ru-RU "lang =" ru-RU "> 111

Să determinăm lungimea medie a cuvântului de cod:

Acum hai să facem codarea Shannon. Procesul de codificare este prezentat în tabelul 5.4.

"xml: lang =" ru-RU "lang =" ru-RU "> Tabelul 5.4

"xml: lang =" ru-RU "lang =" ru-RU "> Codificare Shannon

"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" en-US "lang =" en-US "> n; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" en-US "lang =" en-US "> q; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" ru-RU "lang =" ru-RU "> Cod"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i	"xml: lang =" ru-RU "lang =" ru-RU "> Cod trunchiat"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" en-US "lang =" en-US "> i
"xml: lang =" en-US "lang =" en-US "> a; vertical-align: sub "xml: lang =" ru-RU "lang =" ru-RU "> 1	"xml: lang =" en-US "lang =" en-US ">] 2.321… [= 3	"xml: lang =" en-US "lang =" en-US "> 0	000	000
a 2	] 2.321… [= 3	0.2	001	001
a 3	] 2.395… [= 3	0.4	011	01
a 4	] 3.058… [= 4	0,59	1001	100
a 5	] 3.183… [= 4	0.71	1011	101
a 6	] 3.472… [= 4	0.82	1101	110
a 7	] 3.472… [= 4	0.91	1110	111

Ca și în cazul precedent, găsim lungimea medie a cuvântului de cod:

.

După cum puteți vedea, rezultatele codificării prin metodele Fano și Shannon în ceea ce privește minimizarea lungimii medii a codului au coincis practic. Prin urmare, aceste metode sunt adesea considerate ca una (în formularea lui Fano) și numite metoda Shannon-Fano.

În 1952, David Huffman a propus o metodă de codificare optimă a prefixelor pentru surse discrete, care, spre deosebire de metodele lui Shannon și Fano, este încă folosită în practică. D. Huffman a demonstrat că lungimea medie a unui cuvânt de cod, obținută folosind metoda sa, va fi minimă. Codarea Huffman se face în trei pași.

1. Ordonare: literele sunt aranjate în ordinea descrescătoare a probabilităţilor lor.

2. Reducere: două litere cu cea mai mică probabilitate sunt combinate într-una cu probabilitatea totală; lista de litere este reordonată conform pasului 1; procesul continuă până când toate literele sunt combinate într-una singură. În acest caz, este posibil să se realizeze egalizarea lungimilor cuvintelor cod folosind următoarea strategie: dacă mai multe litere au aceleași probabilități, atunci acele două dintre ele care au avut anterior cel mai mic număr de uniuni sunt combinate (deși acest lucru nu va afectează lungimea medie a codului).

3. Codificare: începând de la ultima unire, unei componente a literei compuse i se atribuie secvenţial simbolul 0, iar celei de-a doua - simbolul 1; procesul continuă până când toate literele originale sunt codificate.

Să executăm codarea Huffman pentru setul considerat în exemplele de aplicare a metodelor Fano și Shannon.

1. Lista de scrisori originaleA = { A1 , A2 , A3 , A4 , A5 , A6 , A7 ) este deja comandat din moment ceP = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Combină litereleA6 șiA7 într-o singură scrisoareA1 cu probabilitate0.18 șireordonalistă:

P1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, A1 = { A1 , A2 , A3 , A1 , A4 , A5 }.

3. Repetați pasul 2 până când rămâne o singură literă în listă:

P2 = {0.23, 0.2, 0.2, 0.19, 0.18}, A2 = { A2 , A1 , A2 , A3 , A1 };

P3 = {0.37, 0.23, 0.2, 0.2}, A3 = { A3 , A2 , A1 , A2 };

P4 = {0.4, 0.37, 0.23}, A4 = { A4 , A3 , A2 };

P5 = {0.6, 0.4}, A5 = { A5 , A4 };

P6 = {1}, A6 = { A6 }.

4. Să atribuimbinarcodurisimboluri:

A6 : A5 = 0, A4 = 1;

A5 : A3 = 00, A2 = 01;

A4 : A1 = 10, A2 = 11;

A3 : A3 = 000, A1 = 001;

A2 : A4 = 010, A5 = 011;

A1 : A6 = 0010, A7 = 0011.

Astfel, următoarele coduri binare sunt atribuite literelor originale:A1 = 10, A2 = 11, A3 = 000, A4 = 010, A5 = 011, A6 = 0010, A7 = 0011, care oferă o lungime medie a codului care este mai mică decât în ​​cazul codării Fano și Shannon.

Să definim redundanța codurilor primite. Pentru a face acest lucru, găsim entropia sursei mesajului:

.

Atunci codurile au următoarea redundanță:

Cod Fano:;

Cod Shannon:;

Cod Huffman:.

Astfel, redundanța codului Huffman este minimă.

Pentru a reduce redundanța, de ex. reducând lungimea medie a unui cuvânt de cod cu un simbol, puteți utiliza codarea bloc, a cărei rațiune este dată în teorema de codare sursăII... În acest caz, trebuie să obțineți tot felul de grupuri de litere lungimea dată, găsiți probabilitățile grupelor, ca și probabilitățile de apariție comună a literelor grupului în același timp și efectuați codarea, considerând grupurile ca simboluri ale noului alfabet.

PAGINA 43

Pentru orice productivitate a sursei de mesaje H, mai mică decât capacitatea canalului C, există o metodă de codare care permite transmiterea tuturor informațiilor generate de sursa de mesaje cu o probabilitate de eroare arbitrar mică.

Deși demonstrația acestei teoreme, propusă de Shannon, a fost supusă ulterior unei prezentări matematice mai profunde și mai riguroase, ideea ei a rămas neschimbată. Se dovedește doar existența metodei de codare dorite, pentru care probabilitatea medie de eroare se găsește pentru toate modalități posibile codificare și să arate că se poate face mai puțin decât o valoare arbitrar mică a lui e. Mai mult, există cel puțin o metodă de codare pentru care probabilitatea de eroare este mai mică decât media.

Demonstrarea teoremei. Lăsa H (x)și H (x | y) - entropia a priori și a posteriori per simbol (de la capătul receptor) pentru un sistem care implementează capacitatea CU canal. In virtutea proprietatii E pentru o durată suficient de lungă ( P simboluri) toate transmisiile posibile ale oricărui ansamblu se împart în grupuri foarte probabile și improbabile; în același timp, se pot face următoarele afirmații despre numărul de semnale din grupurile corespunzătoare:

a) Un grup de semnale transmise foarte probabil conține aproximativ 2 nn (x) secvente.

b) Un grup de semnale primite foarte probabil conține aproximativ 2 luni (y) secvente.

c) Fiecare semnal primit foarte probabil ar putea (cu probabilități aproximativ egale) să provină de la aproximativ 2 nn (x | y) semnale transmise ale unui grup foarte probabil.

d) Fiecare semnal trimis dintr-un grup foarte probabil (cu aproximativ aceleași probabilități) poate corespunde cu aproximativ 2 nn (y | x) a primit semnale de mare probabilitate.

In virtutea proprietatii E entropia proceselor discrete, cu creștere P toate e și d corespunzătoare vor tinde spre zero.

Acum lăsați informațiile să fie transmise pe același canal cu o viteză de intrare egală cu N< С. În acest caz, numărul de semnale trimise foarte probabil cu o lungime de P caracterele vor fi egale cu 2 lun< 2nn (x)... După cum sa menționat deja, problema alegerii un anumit cod constă în a indica care dintre cele 2 nn (x) secvențele posibile sunt alese ca 2 lun permise pentru expediere și cum sunt împărțite în 2 lun subgrupe 2 luni (y) secvențe de ieșire. Luați în considerare o clasă de tot felul de coduri care se vor dovedi dacă 2 lun a permis postarea secvențelor la întâmplare dintre 2 nn (x) semnale posibile ale unui grup foarte probabil; găsiți valoarea medie a probabilității de eroare pentru aceste coduri.

Să fie primit un semnal la K.În acest caz, probabilitatea de eroare este egală cu probabilitatea ca un anumit semnal să apară de la mai mult de unul din 2 lun semnale permise. Deoarece codul este obținut prin alegere aleatorie (echiprobabilă) 2 lun secvențe de 2 nn (x), apoi probabilitatea ca semnal prestabilit la intrarea canalului va fi printre cele permise, egale cu

Semnal primit la corespunde cu 2 nn (x | y) eventual semnale trimise. De aici probabilitatea medie ca niciuna dintre cele 2 nn (x | y) semnale (cu excepția unuia efectiv trimis) nu este permis, egal (neglijăm unitatea în comparație cu nn (x | y))

Aceasta este probabilitatea medie de recepție fără erori. Mai departe, din moment ce N< С = Н(х) – Н(х| у), atunci

H - H (x) = - H (x | y) - h , (8.23)

Unde h> 0. Înlocuind (8.23) în (8.22), obținem

Se poate arăta că

acestea. că, cu codificare aleatorie în blocuri suficient de lungi, probabilitatea medie de eroare poate fi făcută arbitrar de mică. Afirmația despre existența a cel puțin unui cod care oferă o probabilitate de eroare mai mică decât media completează demonstrația.

Rețineți că egalitatea (8.25) este valabilă pentru orice h pozitiv, arbitrar mic. Aceasta înseamnă că teorema admite condiția H £ C.

Acest lucru dă o semnificație specială conceptului de lățime de bandă: lățimea de bandă se dovedește a fi nu doar rata maximă posibilă de transfer de date, ci viteza maxima, în care transmisia este încă posibilă cu o probabilitate de eroare arbitrar mică.

A doua teoremă a lui Shannon privind codificarea în prezența zgomotului. Pentru a asigura o imunitate suficientă la zgomot, este necesar să se introducă în semnal transmis redundanță, reducând astfel viteza de transfer de informații. Este destul de firesc să ne temem că, odată cu restricțiile crescânde privind micimea probabilității de eroare, redundanța necesară va crește, reducând progresiv rata de transfer de informații, eventual la zero. Cu toate acestea, toate îndoielile sunt înlăturate de a doua teoremă de codificare Shannon pentru canalele zgomotoase, care poate fi formulată după cum urmează:

Teorema.În condiția H £ C, printre codurile care oferă (conform Primei Teoreme) o probabilitate de eroare arbitrar mică, există un cod în care rata de transfer de informații R este în mod arbitrar apropiată de rata de creare a informațiilor H.

Rata de transfer de informații (pe caracter) este definită ca

R = H - H (x | y), (8.26)

Unde H (x | y) - entropia posterioară a semnalului trimis pe simbol, sau împrăștierea informațiilorîn canal.

Dovada teoremei (vezi) începe cu afirmația că redundanța minimă necesară per simbol este H (x | y) caractere suplimentare. Se mai arată că codul poate fi ales astfel încât H (x | y) era arbitrar mic.

Discuție de teoreme.În primul rând, să remarcăm caracterul fundamental al rezultatelor obținute. Teorema stabilește limita teoretică a posibilei eficiențe a sistemului cu transmitere fiabilă a informațiilor. Ideea, care părea intuitiv corectă, că realizarea unei probabilități de eroare arbitrar de mică în cazul transmiterii informațiilor pe un canal zgomotos este posibilă numai cu introducerea unei redundanțe infinit de mari, adică este infirmată. când viteza de transmisie este redusă la zero. Din teoreme rezultă că interferența canalului nu impune restricții asupra preciziei transmisiei. Limitarea este impusă doar asupra ratei de transmisie la care poate fi atinsă o fiabilitate a transmisiei arbitrar ridicată.

Teoremele sunt neconstructive în sensul că nu ating problema modalităților de construire a codurilor care asigură transmisia ideală indicată. Cu toate acestea, după ce au fundamentat posibilitatea fundamentală a unei astfel de codări, ei au mobilizat eforturile oamenilor de știință pentru a dezvolta coduri specifice.

Trebuie remarcat faptul că pentru orice rată finită de transfer de informații până la debit, o probabilitate de eroare arbitrar mică este atinsă numai cu o creștere nelimitată a duratei secvențelor de caractere codificate. Astfel, transmisia fără erori în prezența interferenței este posibilă doar teoretic.

Oferirea de transmitere a informațiilor cu o probabilitate foarte scăzută de eroare și o eficiență suficient de mare este posibilă atunci când se codifică secvențe de caractere extrem de lungi. În practică, gradul de fiabilitate și eficiență este limitat de doi factori: mărimea și costul echipamentului de codificare și decodare și timpul de întârziere. mesaj transmis... Folosit în prezent relativ metode simple codificări care nu implementează capabilitățile indicate de teorie. Cu toate acestea, cerințele în continuă creștere pentru fiabilitatea transmisiei și progresele în tehnologie pentru a crea mari circuite integrate promovează introducerea unor echipamente din ce în ce mai sofisticate în aceste scopuri.

Cu toate acestea, trebuie avut în vedere că teoremele pentru canalele zgomotoase discrete, precum și teorema 2 pentru canalele zgomotoase, nu afirmă că codarea secvențelor lungi de mesaje este singura metoda codificare eficientă. Sensul acestor teoreme este de a afirma existența metode eficiente codificarea şi stabilirea limitelor cantitative ale ratei maxime posibile de transmisie a datelor. În acest sens, nu numai afirmațiile directe, ci și inverse ale acestor teoreme sunt importante. Din demonstrarea teoremelor rezultă doar că prin codificarea unor secvențe de mesaje suficient de lungi, se poate apropia întotdeauna rata maximă posibilă de transmitere a mesajelor (cu probabilitatea minimă de eroare pentru canalele zgomotoase) cât mai aproape posibil. Aceasta din urmă, însă, nu înseamnă că alte metode eficiente de codare nu pot exista. Dimpotrivă, se poate demonstra pe o serie de exemple particulare că astfel de metode există.

Din păcate, în prezent, nu au fost găsite metode generale pentru construirea de coduri eficiente pentru canalele zgomotoase care să satisfacă diverse cerințe practice. Treptat, însă, astfel de metode ies la iveală. O afirmație foarte interesantă și importantă a teoremei este că, într-un canal zgomotos, cu nesiguranță arbitrar scăzută a transmisiei mesajului (→ 0), rata de transfer de informații poate fi în mod arbitrar apropiată de C C ... Anterior, opinia predominantă, bazată pe considerații intuitive, că, cu aceste cerințe, rata de transfer de informații ar trebui redusă la infinit.

Semnificația fundamentală a teoremelor constă în faptul că permit, cunoașterea valorilor limită (teoretice) ale ratei de transfer de informații C C , evaluați eficacitatea metodelor de codificare utilizate.

Deci, teoremele de mai sus sunt teoreme de existență.

Din demonstrarea acestor teoreme nu rezultă cum să construiți codul și să efectuați decodarea, astfel încât probabilitatea de eroare să fie cât de mică doriți, iar rata de transmisie să fie în mod arbitrar apropiată de capacitatea liniei de comunicație. Teoremele sunt asimptotice, i.e. nu sunt constructive. Cu toate acestea, însăși cunoașterea oportunităților potențiale este de mare importanță: compararea caracteristicilor sisteme reale Cu limite teoretice vă permite să judecați nivelul atins și fezabilitatea costurilor ulterioare pentru a-l crește. Întrebările aplicate sunt luate în considerare într-o secțiune specială a teoriei informațiilor - teoria codificării, care studiază metodele de construire a codurilor specifice și proprietățile acestora, în special, exacte sau dependențe de graniță probabilitățile de erori din parametrii codului.

Teorema lui Shannon inversă pentru canalele zgomotoase. Teorema inversă indică condițiile care apar atunci când informațiile sunt transmise pe un canal zgomotos la o rată care depășește lățimea de bandă.

Teorema.Dacă rata de creare a informațiilor H este mai mare decât capacitatea canalului C, atunci niciun cod nu poate reduce probabilitatea de eroare în mod arbitrar. Difuzarea minimă a informațiilor pe simbol, atinsă pentru H> C, este egală cu H - C; niciun cod nu poate oferi mai puțină împrăștiere a informațiilor.

Dovada teoremei inverse a lui Shannon poate fi găsită în.

Teorema inversă afirmă că pentru H> C transmiterea fără erori este imposibilă; mai mult, cu cât raportul este mai mare H/C, cu atât este mai mare incertitudinea reziduală H (x | y). Acesta din urmă este legat de probabilitatea de a primi erori. Întrebarea apare în mod firesc cu privire la modul în care s-a atins probabilitatea minimă de eroare la cea mai buna codare, cu atitudine N/S. Pentru canal binar solutia este data in. La k = N/C< 1 вероятность ошибки e(La) = 0 conform primei teoreme. La La® ¥ e ( La) ® 0,5, ceea ce înseamnă că fracția informatii transmise a întregului canal care intră în intrare tinde spre zero la La® ¥; cu cât transmisia este mai rapidă, cu atât se transmit mai puține informații.

Întrebări de control

1. Oferiți o justificare pentru necesitatea introducerii redundanței la codificare pe un canal zgomotos.

2. Cum este cantitatea medie de informații (pe caracter) transmisă prin canal discret cu zgomote?

3. Cum se determină rata de transmisie și lățimea de bandă a unui canal zgomotos?

4. Formulați și explicați teoremele de codificare Shannon înainte și înapoi pentru un canal zgomotos.

5. Ce relații decurg din teorema de echiprobabilitate asimptotică pentru lanțuri tipice suficient de lungi pentru canalele zgomotoase staționare?

6. Care este motivul pentru recomandarea de a codifica secvențe lungi de caractere?

7. Ce formulă determină debitul unui canal binar simetric fără memorie, în ce condiție dispare debitul acestui canal?

Capacitatea informațională a canalelor discrete (4.4) și debitul continuu (4.7) caracterizează capacitățile lor limitatoare ca mijloace de transmitere a informațiilor. Ele sunt dezvăluite în teoremele fundamentale ale teoriei informației, care sunt cunoscute sub numele de teoreme fundamentale de codare ale lui Shannon. Pentru un canal discret, scrie:

Teorema 4.4.1. (Teorema de codificare directă pentru DCBP.) Pentru un canal discret fără memorie la rate de cod R mai puțină capacitate de informare, există întotdeauna un cod pentru care probabilitatea medie de eroare tinde spre zero odată cu creșterea lungimii cuvântului de cod.

În cazul unui canal continuu se formulează ca

Teorema 4.4.2. (Teorema de codare directă pentru canalul ABGN). Informațiile pot fi transmise pe un canal ABGS cu lățime de bandă nelimitată cu o probabilitate de eroare arbitrar mică dacă rata de transmisie este mai mică decât lățimea de bandă.

Teorema inversă spune:

Teorema 4.4.3. La baud rate
, lățime de bandă mai mare a canalului de comunicație C, niciun cod nu va oferi o probabilitate arbitrar scăzută de eroare de decodare, adică mesaje absolut de încredere.

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

Rezultatele teoremelor de codificare 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 odată cu probabilitatea erorilor. Această concluzie, în special, decurge din luarea în considerare a retransmiterii multiple a simbolurilor pe 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 unei erori în transmiterea unui mesaj tinde spre zero numai atunci când rata de transmisie tinde spre zero.

Cu toate acestea, teorema de codificare arată că, în principiu, este posibil să se transmită la o rată arbitrar apropiată de C realizând în același timp o probabilitate de eroare arbitrar mică. Din păcate, teoremele, care indică existența fundamentală a unui cod imun la zgomot, nu oferă o rețetă pentru găsirea acestuia. Se poate observa doar că acest lucru necesită utilizarea de coduri lungi. În acest caz, pe măsură ce rata de transmisie se apropie de debitul și probabilitatea de eroare scade, codul devine mai complicat din cauza creșterii lungimii blocului, 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, despre care se vor discuta mai târziu, nu realizează potenţialul sistemului de comunicaţii. Codurile turbo care au fost descoperite recent sunt singurele excepții.

1Acest rezultat este valabil pentru orice canale echilibrate.

Programul cursului

„Teoria informației și codării”

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

51 ore, lector asistent universitar

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

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

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

Problema codificării unei surse cu coduri de lungime inegală. Costul de codare. Coduri decriptate fără ambiguitate. Coduri de prefix... Codare literă cu literă. O condiție necesară și suficientă pentru decriptarea fără ambiguitate a codului. Codurile complete... O 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 echiprobabilă 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 decriptarea fără ambiguitate a unui cod. Algoritmi adaptativi pentru compresia informatiilor.

Canal discret fără memorie. Binar canal echilibrat... Rata de transfer de informații în canal. Lățime de bandă de canal. Canal extins și lățimea de bandă a acestuia. Scheme decisive și grupări de observații. Probabilitatea transmiterii eronate a informațiilor. inegalitatea lui Feinstein. Teorema directă de codificare a unui canal fără memorie. Inegalitatea lui Fano. Teorema procesării informației. Inversarea teoremei de codare.

Teoria codificării corectoare de erori. Criteriul de maximă probabilitate. Distanța codului. Codurile de paritate. generativ și verificarea matricelor... sindrom. Algoritm de decodare pentru codurile de verificare a parității. Codurile liniareși algoritmul lor de decodare. Chenar Hamming. Cod Hamming. Codurile ciclice. Codificare și decodare ciclică.

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, Știință, 1982.

4. Feinstein A. Foundations of information theory, M., IL, 1960.

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

6. Bärlekamp, ​​​​Teoria codificării algebrice, M., Mir, 1971.