Prima teoremă a lui Shannon. Teorema fundamentală a lui Shannon privind codificarea unui canal fără interferențe. Codificarea informațiilor de vorbire
Curs 6. Enunțarea problemei de codificare. Prima teoremă a lui Shannon.
Teoria codificării informației este una dintre ramurile informaticii teoretice. La principalele sarcini rezolvate în aceasta sectiune informatică, este necesar să se includă următoarele:
dezvoltarea principiilor cel mai economic codificarea informațiilor;
coordonarea parametrilor informatiile transmise cu caracteristicile canalului de comunicare;
dezvoltarea tehnicilor de asigurare fiabilitate transferul de informații prin canale de comunicatie, adică fără pierderi de informații.
După cum s-a menționat atunci când luăm în considerare conceptele inițiale ale informaticii, un anumit alfabet este folosit pentru a reprezenta mesaje discrete. Cu toate acestea, adesea nu există o corespondență unu-la-unu între informațiile conținute într-un mesaj și alfabetul (mesajului) acestuia.
Într-o serie de aplicații practice, este nevoie de a traduce un mesaj dintr-un alfabet în altul, iar o astfel de conversie nu ar trebui să ducă la pierderea de informații.
Să introducem o serie de definiții.
Vom presupune că sursa informației reprezintă informații sub forma unui mesaj discret, folosind în acest scop alfabetul, pe care vom fi de acord să-l numim alfabetul primar . Apoi, acest mesaj intră într-un dispozitiv care convertește și prezintă mesajul într-un alt alfabet - vom numi acest alfabet alfabetul secundar .
Cod - aceasta este o regulă care descrie corespondența caracterelor sau combinațiilor de caractere ale alfabetului primar cu caracterele sau combinațiile de caractere ale alfabetului secundar.
Cu toate acestea, există o altă definiție:
Cod este un set de caractere sau combinații de caractere ale alfabetului secundar, utilizate pentru a reprezenta caractere sau combinații de caractere ale alfabetului primar.
Codificare este traducerea informațiilor reprezentate de un mesaj în alfabetul primar într-o succesiune de coduri.
Decodare – aceasta este operația inversă a codificării, adică restaurarea informațiilor din alfabetul primar conform secvenței de coduri primite.
Codificator este un dispozitiv care efectuează operația de codificare.
Decodor este un dispozitiv care efectuează decodare.
Operațiile de codificare și decodare sunt numite reversibil , dacă utilizarea lor consecventă asigură revenirea la informațiile originale fără nicio pierdere.
Exemplu reversibil codificarea este reprezentarea caracterelor într-un cod telegrafic și restaurarea lor (de către destinatar) după transmitere.
Exemplu ireversibil codificarea poate servi ca traducere dintr-o limbă naturală în alta. În acest caz, traducerea inversă, în general, nu se restabilește text sursă. Aici este important de înțeles că informația originală este restaurată cu pierderi atât din punct de vedere semantic, cât și în sensul distorsiunii sub formă de prezentare (secvența de caractere din alfabetul primar obținut după traducerea inversă este aproape întotdeauna diferită față de text sursă).
Desigur, pentru problemele practice legate de reprezentarea simbolică a informației, capacitatea de a restabili informațiile din codul acesteia este o condiție necesară pentru aplicabilitatea codului, așa că pe viitor ne vom limita la a lua în considerare doar codificarea reversibilă.
Codificarea informațiilor precede transmiterea și stocarea informațiilor. În acest caz, stocarea informațiilor este asociată cu fixarea unei anumite stări a purtătorului de informații, iar transmiterea informațiilor este asociată cu procesul de schimbare a stării purtătorului de informații (mediu), adică cu semnale. Vom numi aceste stări sau semnale semnale elementare .Setul de semnale elementare constituie alfabetul secundar.
Acum nu vom discuta despre aspectele tehnice ale transmiterii și stocării unui mesaj, adică nu vom discuta despre modul în care sunt implementate din punct de vedere tehnic transmisia și recepția unei secvențe de semnale sau înregistrarea stărilor unui purtător de informații (înregistrarea informațiilor).
Să încercăm să facem matematic formularea problemei codificării informaţiei.
Să fie format din alfabetul primar 
, și alfabetul secundar 
cuprinde 
semne cu informații medii pe semn 
. Să conțină și mesajul original, reprezentat în alfabetul primar 
caractere, iar mesajul codificat (reprezentat într-un alfabet secundar) conține 
semne. Deci mesajul original conține 
informații, iar mesajul codificat conține 
informație.
Operația de codare reversibilă poate crește cantitatea de informații dintr-un mesaj, dar nu o poate reduce.:
.
Această inegalitate poate fi rescrisă ca 
sau
.
Atitudine 
caracterizează numărul mediu de caractere din alfabetul secundar care trebuie utilizat pentru a codifica un caracter al alfabetului primar.
mărimea 
o vom numi lungimea codului sau lungimea lanțului de coduri:
.
Din inegalitatea anterioară 
urmează că 
, De aceea:
. (7.1)
De obicei, în practică, procedura de codificare este implementată în așa fel încât condiția să fie îndeplinită
,
De aceea 
, adică un caracter al alfabetului primar este reprezentat de mai multe caractere ale alfabetului secundar.
Metode de construire a codurilor cu alfabete fixe 
Și 
există multe. Prin urmare, se pune problema alegerii (sau construirii) celei mai bune versiuni a codului - o vom numi cod optim
.
Rentabilitatea utilizării unui cod optim la transmiterea și stocarea informațiilor este un factor economic, deoarece un cod mai eficient poate permite mai puțină energie și timp pentru transmiterea mesajelor. Daca se foloseste codul optim la transmiterea informatiilor, linia de comunicatie poate fi ocupata mai putin timp. Utilizarea unui cod optim la stocarea informațiilor poate permite utilizarea unei suprafețe (volum) mai reduse a purtătorului de informații.
În același timp, ar trebui să știți că profitabilitatea codului nu intotdeauna este identică cu eficiența în timp a întregului proces de „codare-transmisie-decodare”. Este posibil să fiți nevoit să plătiți pentru utilizarea unui cod eficient la transmiterea informațiilor prin faptul că operațiunile de codificare și decodare vor necesita mai mult timp și/sau alte resurse (memoria unui dispozitiv tehnic, dacă aceste operațiuni sunt efectuate cu ajutorul acestuia) .
După cum rezultă din condiția (7.1), lungimea medie minimă posibilă a codului este egal cu:
. (7.2)
Această expresie ar trebui luată ca un raport evaluativ caracter care stabilește o limită inferioară a lungimii codului. Cu toate acestea, din (7.2) nu este clar în ce măsură circuite reale codificare este posibil să se aproximeze valoarea 
a valorifica 
.
Din acest motiv, teoremele dovedite de Shannon sunt importante pentru teoria codificării și teoria comunicării. Prima teoremă a lui Shannon se referă la situația de codificare în absența interferenței care distorsionează mesajul. A doua teoremă a lui Shannon se aplică liniilor de comunicație reale cu zgomot și va fi discutată mai târziu.
Prima teoremă a lui Shannon , sau teoremă fundamentală despre codificare în absența interferenței , se formulează după cum urmează:
În absența interferenței, este întotdeauna posibilă o opțiune de codare în care numărul mediu de caractere de cod per caracter al alfabetului primar va fi în mod arbitrar apropiat de raportul dintre informațiile medii per caracter al alfabetului primar și secundar.
Această teoremă stabilește posibilitatea fundamentală de codificare optimă, adică construirea unui cod cu lungime medie având valoarea 
.
Cu toate acestea, este necesar să ne dăm seama că din această teoremă în sine nu se urmărește în niciun fel cum se implementează o astfel de codificare în practică. Pentru a dezvolta o implementare practică a codificării optime, trebuie să fie implicate considerații suplimentare, despre care vom discuta în continuare.
Din (7.2) este clar că există două moduri de reducere a valorii 
:
K. Shannon a examinat în detaliu următoarea situație particulară. În această situație, la codificarea unui mesaj, se ia în considerare probabilitatea diferită de apariție a caracterelor în alfabetul primar, adică cantitatea de informații per caracter al alfabetului primar este calculată ca o primă aproximare: 
. Cu toate acestea, corelațiile semnelor alfabetului primar nu sunt luate în considerare. Surse de mesaje similare se numesc surse fără memorie
(despre corelarea semnelor alfabetului primar – propriu). Dacă în același timp este asigurată o probabilitate egală de apariție a semnelor alfabetului secundar, atunci, după cum urmează din (7.2), pentru lungimea medie minimă a codului 
următoarea relație se dovedește a fi adevărată:
. (7.3)
Ca măsură a excesului 
de mai sus 
poti intra redundanță relativă a codului
:
Ținând cont de (7.2), ultima formulă poate fi rescrisă ca
și 
.
Magnitudinea 
arată cât de mult a crescut operația de codificare lungimea mesajului original. Este evident că 
la .
Astfel, soluția la problema de optimizare a codării este de a găsi scheme de codare care să asigure că lungimea medie a codului se apropie de valoarea 
, și redundanța relativă 
cod - la zero. Cu cât valoarea este mai mică 
, cu atât apar informațiile mai puțin redundante, adică informațiile asociate cu codificarea; codul devine mai profitabil și operația de codificare devine mai eficientă.
Folosind conceptul de redundanță de cod, se poate construi o formulare diferită a primei teoreme a lui Shannon :
În absența interferenței, este întotdeauna posibilă codificarea unui mesaj în așa fel încât redundanța codului să fie în mod arbitrar aproape de zero.
Cea mai importantă situație pentru practică este atunci când se află în alfabetul secundar 
, adică atunci când doar două tipuri de semnale sunt folosite pentru a reprezenta coduri pe o linie de comunicație. Această codificare este numită codificare binară
. Din punct de vedere tehnic, aceasta este opțiunea cel mai ușor de implementat. De exemplu, existența tensiunii în fir (puls) sau absența acesteia (pauză); prezența sau absența unei găuri pe cardul perforat; prezența sau absența unei zone magnetizate pe o dischetă și așa mai departe
Caracterele alfabetului binar sunt de obicei notate „0” și „1”; aceste caractere ar trebui să fie percepute ca litere. Comoditatea codurilor binare constă și în faptul că, cu durate și probabilități egale, fiecare semnal elementar (0 sau 1) poartă exact 1 bit de informație ().
În cazul unui alfabet secundar binar (notăm 
) din formula (7.3) se obține:
,
iar primul Teorema lui Shannon primește o altă (a treia) formulare :
În absența interferenței, lungimea medie cod binar poate fi în mod arbitrar aproape de informația medie pe semn al alfabetului primar.
Astfel, la codificarea mesajelor sursă fără memorie cu semne binare de probabilitate egală folosind formula (7.4), găsim:
. (7.5)
La decodificarea mesajelor binare, apare problema izolării semnalelor (secvențe de impulsuri și pauze) din flux. cuvinte de cod (grupuri de semnale elementare) corespunzătoare caracterelor individuale ale alfabetului primar. În acest caz, dispozitivul receptor înregistrează intensitate Și durată semnale și, de asemenea, poate corela secvența semnalelor de intrare cu secvențe de referință (cu tabelul de coduri ).
Notă următoarele caracteristici binar alfabetul secundar folosit în codificare:
Combinațiile dintre caracteristicile enumerate ale alfabetului secundar determină baza unei anumite metode de codificare a mesajelor. Cu toate acestea, chiar și cu aceeași bază, sunt posibile opțiuni diferite pentru construirea de coduri, care vor diferi în ceea ce privește eficacitatea.
Principala semnificație a rezultatelor lui Shannon în acest domeniu este că acestea oferă un criteriu universal care permite comparații tehnice diverse dispozitiveși sisteme în ceea ce privește capacitățile lor de transfer de informații. Din punct de vedere tehnic, sursele de mesaje și canalele de comunicare pot fi semnificative diferite dispozitive privind semnalele utilizate, metodele de codificare a mesajelor, formatele de date, caracteristicile vitezei. În aceste condiții, măsurarea informației lui Shannon și teoremele de codificare ideală fac posibilă evaluarea în ce măsură sisteme diferite din punct de vedere tehnic corespund între ele pentru a rezolva problema transmiterii mesajelor. Acest lucru necesită, pe baza indicatorilor tehnici ai sursei și canalului, să se evalueze indicatorii lor informaționali: productivitatea informațională și debitul de informații. Raportul indicatorilor de informații este măsura ideală prin care se poate aprecia gradul de conformitate a sistemelor reale.
Meritul special al lui Shannon este că a fost primul care a realizat imaginea reală a influenței interferențelor aleatorii asupra procesului de transmitere a mesajelor. Efectul fundamental al interferenței este exprimat în măsura în care acestea afectează performanța informațională a sistemului. Prin urmare, canalele cu aceeași capacitate sunt echivalente cu posibilitatea transmiterii fără erori a mesajelor, indiferent dacă au interferențe sau nu.
Pentru a explica clar rolul teoremei lui Shannon, vom recurge la următoarea comparație. Să existe o conductă pentru livrarea unui produs lichid dintr-o sursă. Capabilitati tehnice conductele sunt determinate de cantitatea de lichid care poate fi transmisă prin ele pe unitatea de timp. Definim productivitatea sursei prin cantitatea de produs pur care provine din aceasta pe unitatea de timp și debitul conductei - ca rata maximă posibilă de transfer a produsului pur, corespunzătoare condiției din care provine un produs pur fără impurități. sursa. Un analog al unui canal cu interferență poate fi o conductă cu o scurgere. Debitul său va fi mai mic. Decât într-o conductă fără scurgeri, prin cantitatea de scurgere de produs pe unitatea de timp. Ne putem imagina acum ce efect ar fi cauzat de afirmația că există o astfel de modalitate de a introduce o impuritate („redundanță”) într-un produs în care, prin introducerea unei cantități de impurități egale cu scurgerea în conductă, este posibil pentru a livra produsul prin acesta fără pierderi la o viteză corespunzătoare debitului conductei cu o scurgere. Acesta este tocmai sensul teoremei lui Shannon în raport cu problema transmiterii informației. Continuând analogia cu acest exemplu, putem spune că această metodă de introducere a unei impurități necesită prezența unui fel de „decantator” în care impuritatea se va depune pentru un anumit timp înainte de a fi alimentată în conductă (ideal, un timp infinit) . După o astfel de „decontare”, atunci când lichidul se deplasează prin conductă, numai impuritățile se vor scurge.
Interpretarea rezultatelor lui Shannon pentru problemele de stocare și regăsire a informațiilor. Rezultatele teoremelor lui Shannon, formulate în mod tradițional pentru problema transmiterii mesajelor, sunt ușor de extins la problemele de stocare și regăsire a informațiilor.
Să luăm în considerare problema stocării datelor în următoarea formă generalizată. Lasă datele sub forma unei secvențe de înregistrări să fie plasate în celulele unui dispozitiv de stocare (memorie); Fiecare intrare este plasată într-o celulă separată. Înregistrările destinate stocării se caracterizează printr-o anumită colecție caracteristici tehnice: dimensiuni, metode de codificare a datelor, formate de cod etc. Celulele de stocare în care sunt stocate înregistrările se caracterizează și printr-un anumit set de caracteristici tehnice ale acestora: reprezentarea internă a datelor, modalitatea de acces, sistemul de etichetare etc. limitări tehnice asupra procesului de plasare a datelor. În plus, informațiile plasate în celulele de memorie pot fi supuse interferențelor, ceea ce provoacă apariția erorilor în înregistrări.
Se pune întrebarea în ce condiții este posibilă stocarea fiabilă a informațiilor, adică preluarea datelor din memorie în forma în care acestea au fost plasate acolo.
Pentru a răspunde la această întrebare în conformitate cu abordarea Shannon, este necesar să trecem de la caracteristici tehnice la informativ:
Pentru datele stocate, determinați entropia medie a înregistrării;
Pentru un dispozitiv de stocare, determinați cantitatea maximă de informații care poate fi plasată într-o celulă, ținând cont de limitările tehnice ale acesteia și de interferența prezentă în aceasta, adică de a determina capacitatea de informare a celulei.
Atunci pentru utilizatorii de informații va fi valabilă următoarea formulare teorema lui Shannon pentru problema stocării informațiilor: pentru un dispozitiv de stocare (cu și fără interferență) există o modalitate de a codifica și decoda datele stocate cu orice fiabilitate, dacă doar entropia medie a înregistrării este mai mică decât capacitatea de informare a celulei.
Dacă luăm în considerare aplicarea codării ideale la problema stocării informațiilor, devine clar că aceasta va necesita o memorie cu potențial număr infinit celule pentru a găzdui secvențe tipice de înregistrări de orice lungime. Acest lucru demonstrează imposibilitatea tehnică a codării ideale în raport cu problema stocării informațiilor.
Vă puteți apropia de rezultatul ideal prin mărirea înregistrărilor stocate. În practică, așa-numita blocare a înregistrărilor este utilizată pe scară largă în dispozitivele de stocare a datelor computerizate (de exemplu, bandă magnetică și unități de disc). În acest caz, grupurile de înregistrări sunt combinate în blocuri, care sunt plasate în memorie ca niște înregistrări unice mărite. Se realizează astfel o utilizare mai economică a capacităţii informaţionale a celulelor.
Implementare practică Stocarea informațiilor rezistente la zgomot se bazează pe metode de codare rezistente la zgomot. Înainte de plasarea înregistrărilor în memorie, redundanța acestora este mărită artificial prin introducerea unor caractere de control suplimentare. După citirea înregistrărilor din memorie, erorile sunt detectate și corectate.
Să luăm acum în considerare problema de căutare în următoarea formă generalizată. Să existe un fișier ale cărui înregistrări sunt identificate prin chei. Interogările multiple de înregistrare formează o secvență de argumente de căutare. Cunoașterea cheilor și argumentelor de căutare poate fi distorsionată din cauza interferențelor aleatorii în timpul generării fișierului și pregătirii interogărilor.
Se pune întrebarea în ce condiții este posibilă o căutare fiabilă a informațiilor, adică. primind pentru fiecare cerere exact acele inregistrari care sunt necesare.
În conformitate cu abordarea Shannon, să trecem la caracteristicile informatiei:
Pentru secvențele de argumente de căutare, determinăm entropia medie a argumentelor. Dacă argumentele sunt afectate de erori, atunci este necesar să se țină cont de creșterea entropiei medii din cauza erorilor;
Pentru un set de înregistrări de fișier, determinăm capacitatea de informare a cheii - cantitatea maximă de informații care poate fi conținută în cheia de fișier. Dacă cheile fișierului pot conține erori aleatorii, atunci este necesar să se țină cont de reducerea capacității informaționale a cheii din cauza erorilor.
Atunci formularea următoare va fi valabilă pentru indicatorii informaționali teorema lui Shannon pentru sarcina de căutare a informațiilor:
Pentru a căuta un fișier (cu sau fără interferență) există o metodă pentru o căutare arbitrar de încredere înregistrările necesare, dacă doar entropia medie a argumentului este mai mică decât capacitatea de informare a cheii.
Aplicarea algoritmului de codificare ideal în această problemă va necesita o mărire potențial infinită a fișierului pentru a căuta secvențe tipice de argumente sursă ca argumente. Acest lucru demonstrează imposibilitatea tehnică a codării ideale în raport cu problema regăsirii informațiilor.
După cum sa menționat în al doilea capitol, dezvoltarea unor metode fezabile din punct de vedere tehnic pentru căutarea imună la zgomot este în prezent la început. Rezultatele disponibile aici sunt semnificativ mai modeste decât, de exemplu, în codarea imună la zgomot, unde a fost creată o teorie de codificare matematică extinsă și profundă. Ce se întâmplă aici? De ce să nu folosiți rezultatele teoriei codificării pentru a rezolva o problemă legată de regăsire.
Ideea principală a codificării de corectare a erorilor este introducere artificială redundanță în mesaje prin introducerea lor într-un canal zgomotos. În majoritatea sarcinilor de căutare, avem de-a face cu redundanța naturală a mesajelor pe care nu o putem influența în mod activ. Primim un argument de căutare deja distorsionat, de exemplu, numele de familie al clientului a bolborosit la telefon și ne putem baza doar pe redundanța naturală a limbii (redundanța naturală a limbii ruse, ca majoritatea limbilor europene, este de aproximativ 60% ).
Cu toate acestea, ținând cont de solubilitatea fundamentală a acestei probleme în lumina rezultatelor lui Shannon, precum și a publicațiilor recente despre problemele căutării imune la zgomot, se poate spera că această problemă va fi rezolvată tehnic.
Comprimarea datelor.
Mesajele codificate sunt transmise prin canale de comunicație, stocate în dispozitive de stocare și procesate de procesor. Volumele de date care circulă în sistemul de control automatizat sunt mari și, prin urmare, în multe cazuri, este important să se asigure o codificare a datelor care se caracterizează printr-o lungime minimă a mesajelor rezultate. Aceasta este o problemă de compresie a datelor. Rezolvarea acestuia asigură o creștere a vitezei de transfer a informațiilor și o scădere a memoriei necesare a dispozitivelor de stocare. În cele din urmă, acest lucru duce la creșterea eficienței sistemului de procesare a datelor.
Există două abordări (sau două etape) de comprimare a datelor:
Comprimare bazată pe analiza structurii specifice și a conținutului semantic al datelor;
Compresie bazată pe analiză proprietăți statistice mesaje codificate. Spre deosebire de prima, a doua abordare este universală și poate fi folosită în toate situațiile în care există motive să credem că mesajele se supun legilor probabilistice. Ne vom uita la ambele abordări în continuare.
4.1. Comprimare bazată pe conținutul semantic al datelor
Aceste metode sunt euristice și unice în natură, dar ideea principală poate fi explicată după cum urmează. Lăsați setul să conțină elemente. Apoi, pentru a codifica elementele multimii cu un cod uniform, sunt necesare caractere binare. În acest caz, vor fi utilizate toate combinațiile de cod binar. Dacă nu sunt folosite toate combinațiile, codul va fi redundant. Astfel, pentru a reduce redundanța, ar trebui să se încerce să se delimiteze setul de valori posibile ale elementelor de date și să se codifice în consecință. ÎN conditii reale acest lucru nu este întotdeauna ușor, unele tipuri de date sunt foarte mai multă putere set de valori posibile. Să vedem ce fac în cazuri specifice.
Trecerea de la notațiile naturale la cele mai compacte. Valorile multor date specifice sunt codificate într-o formă care poate fi citită de om. Cu toate acestea, de obicei conțin mai multe caractere decât este necesar. De exemplu, data este scrisă ca „26 ianuarie 1982” sau în cea mai scurtă formă: „26/01/82”. cu toate acestea, multe combinații de coduri, cum ar fi „33.18.53” sau „95.00.11”, nu sunt niciodată folosite. Pentru a comprima astfel de date, ziua poate fi codificată cu cinci cifre, luna cu patru, anul cu șapte, i.e. întreaga dată nu va dura mai mult de doi octeți. O altă modalitate de înregistrare a datelor, propusă încă din Evul Mediu, este înregistrarea numărului total de zile care au trecut până în prezent de la un punct de referință. În acest caz, ele sunt adesea limitate la ultimele patru cifre ale acestei reprezentări. De exemplu, 24 mai 1967 este scrisă ca 0000, iar numărarea zilelor de la acea dată necesită evident doi octeți în format zecimal.
CODIFICAREA INFORMAȚIILOR.
ALFABET ABSTRACT
Informațiile sunt transmise sub formă de mesaje. Informații discrete este scris folosind un anumit set finit de semne, pe care le vom numi litere, fără a pune sensul limitat obișnuit acestui cuvânt (cum ar fi „litere rusești” sau „ scrisori"). O scrisoare în acest sens extins este oricare dintre semnele care sunt stabilite printr-un acord pentru comunicare. De exemplu, în transmiterea obișnuită a mesajelor în limba rusă, astfel de semne vor fi litere rusești - majuscule și minuscule, semne de punctuație, spațiu; dacă textul conține numere, atunci există numere. În general, vom numi o literă un element al unui set finit (mult) de semne care sunt diferite unele de altele. Vom numi setul de caractere în care este determinată ordinea lor alfabet (ordinea caracterelor din alfabetul rus este binecunoscută: A, B,..., Z).
Să ne uităm la câteva exemple de alfabete.
1, Alfabetul majusculelor rusești:
A B C D E F G H I J K L M N O P R S T U V
2. Alfabetul Morse:
3. Alfabetul simboluri de la tastatură IBM PC (tastatură rusificată):
4. Alfabetul semnelor unui zar obișnuit cu șase fețe:
5. Alfabetul cu cifre arabe:
6. Alfabetul cifrelor hexazecimale:
0123456789ABCDEF
Acest exemplu, în special, arată că semnele unui alfabet pot fi formate din semne ale altor alfabete.
7. Alfabetul cifrelor binare:
Alfabetul 7 este un exemplu de așa-numitele alfabete „binare”, adică. alfabete formate din două caractere. Alte exemple sunt alfabetele binare 8 și 9:
8. Alfabet binar „punct, „liniuță”:. _
9. Alfabetul binar „plus”, „minus”: + -
10. Alfabetul literelor latine majuscule:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
11. Alfabetul sistemului numeric roman:
I V X L C D M
12. Alfabetul limbajului diagramelor de flux care descriu algoritmi:
13. Alfabetul limbajului de programare Pascal (vezi Capitolul 3).
^
CODARE SI DECODARE
Într-un canal de comunicare, un mesaj compus din simboluri (litere) ale unui alfabet poate fi transformat într-un mesaj format din simboluri (litere) unui alt alfabet. Regula care descrie corespondența unu-la-unu a literelor alfabetului în timpul unei astfel de transformări se numește cod. Procedura de conversie a mesajelor în sine se numește recodare. O astfel de transformare a mesajului poate fi efectuată în momentul în care mesajul sosește de la sursă în canalul de comunicare (codificare) și în momentul în care mesajul este primit de către destinatar (decodare). Dispozitivele care oferă codare și decodare vor fi numite codificator și, respectiv, decodor. În fig. 1.5 prezintă o diagramă care ilustrează procesul de transmitere a mesajului în cazul recodării, precum și influența interferenței (vezi paragraful următor).
Orez. 1.5. Procesul de transmitere a unui mesaj de la o sursă la un receptor
Să ne uităm la câteva exemple de cod.
1. Cod Morse în versiunea rusă (un alfabet compilat din alfabetul rus litere mari iar alfabetul cifrelor arabe este pus în corespondență cu alfabetul Morse):
2. Cod trisime (caracterele alfabetului latin sunt atribuite combinațiilor de trei caractere: 1,2,3):
| A | 111 | D | 121 | G | 131 | J211 | M221 | P231 | S311 | V321 | Y331 |
| ÎN | 112 | E | 122 | H | 132 | K212 | N222 | Q232 | T312 | W322 | Z332 |
| CU | 113 | F | 123 | eu | 133 | L213 | O223 | R233 | U313 | X323 | .333 |
Codul Trisime este un exemplu de așa-numit cod uniform (unul în care toate combinațiile de coduri conțin același număr de caractere - în în acest caz, Trei). Un exemplu de cod neuniform este codul Morse.
3. Codificarea numerelor cu semne diverse sisteme pentru notare vezi §3.
CONCEPTUL DE TEOREME LUI SHANNON
S-a remarcat anterior că atunci când se transmit mesaje prin canale de comunicație, pot apărea interferențe care pot duce la distorsiunea caracterelor primite. Deci, de exemplu, dacă încercați să transmiteți un mesaj vocal pe vreme vântoasă unei persoane aflate la o distanță considerabilă de dvs., acesta poate fi foarte distorsionat de interferențe precum vântul. În general, transmiterea mesajelor în prezența interferenței este o teoretică serioasă și sarcină practică. Importanţa sa creşte datorită implementare pe scară largă telecomunicații computerizate, unde interferențele sunt inevitabile. Când se lucrează cu informații codificate distorsionate prin interferență, pot fi identificate următoarele probleme principale: stabilirea faptului însuși că a avut loc distorsiunea informației; aflarea exactă unde s-a întâmplat acest lucru în textul transmis; corectarea erorii, cel puțin cu un anumit grad de certitudine.
Interferența în transmiterea informațiilor este destul de comună în toate domeniile activitate profesionalăși în viața de zi cu zi. Unul dintre exemple a fost dat mai sus, alte exemple sunt vorbirea la telefon, al cărui receptor „troșnește”, conducerea unei mașini în ceață etc. Cel mai adesea, o persoană se descurcă complet cu fiecare dintre sarcinile de mai sus, deși nu este întotdeauna conștientă de modul în care o face (adică nu algoritmic, ci pe baza unor conexiuni asociative). Se știe că limbajul natural are o mare redundanţă(în limbile europene - până la 7%), ceea ce explică imunitatea mai mare la zgomot a mesajelor compuse din caractere din alfabetele unor astfel de limbi. Un exemplu care ilustrează rezistența limbii ruse la interferență este propoziția „în slovacă vso glosnoo zomonono bokvoy o”. Aici 26% dintre personaje sunt „afectate”, dar acest lucru nu duce la o pierdere a sensului. Astfel, redundanța este o proprietate utilă în acest caz.
Redundanța poate fi folosită și la transmiterea mesajelor codificate în sisteme tehnice. De exemplu, fiecare fragment de text („propoziție”) este transmis de trei ori, iar perechea de fragmente care coincid complet este considerată corectă. Cu toate acestea, redundanța ridicată duce la cantități mari de timp petrecut pentru transmiterea informațiilor și necesită o cantitate mare de memorie pentru stocarea acesteia. Primul studiu teoretic al codificării eficiente a fost întreprins de K. Shannon.
^ Prima teoremă Shannon declară posibilitatea creării unui sistem de codificare eficientă a mesajelor discrete, în care numărul mediu de simboluri binare per simbol de mesaj tinde asimptotic către entropia sursei mesajului (în absența interferenței).
Problema codificării eficiente este descrisă de triada:
X = (X 4i) - codificator - ÎN.
Aici X, B - respectiv, alfabetul de intrare și de ieșire. Sub mulţime x i Puteți înțelege orice semne (litere, cuvinte, propoziții). IN - un set, al cărui număr de elemente, în cazul codificării caracterelor cu numere, este determinat de baza sistemului numeric (de exemplu, T= 2). Codificatorul se potrivește cu fiecare mesaj x i din X combinație de cod alcătuită din n i set de caractere ÎN. Limitarea acestei sarcini este absența interferenței. Este necesar să se estimeze lungimea medie minimă a combinației de coduri.
Pentru a rezolva această problemă, probabilitatea trebuie cunoscută P i apare mesajul x i, care corespunde unui anumit număr de caractere n i alfabet ÎN. Apoi așteptarea matematică a numărului de caractere din ÎN se va determina astfel:
n cf = p i P i(valoarea medie).
Acest număr mediu de caractere din alfabet ÎN corespunde entropiei maxime Ntax = n jurnal mediu T. Pentru a asigura transmiterea informațiilor conținute în mesaje X combinatii de coduri din ÎN, trebuie îndeplinită condiția H4max ≥ H(x), sau p sr Buturuga T≥- P i Buturuga R i.În acest caz, mesajul codificat are redundanță p sr≥H(x) / Buturuga t, n min = H(x) / Buturuga T.
Factorul de redundanță
LA u = ( H max – H(X)) / H max = ( n cp – n min) / n cp
Să scriem aceste valori sub forma unui tabel. 1.8. Avem:
N min = H(X)/Buturuga 2 = 2,85, K u = (2,92 - 2,85) / 2,92 = 0,024,
Acestea. codul nu are practic nicio redundanță. Se poate observa că numărul mediu de simboluri binare tinde spre entropia sursei mesajului.
^ Tabelul 1.8 Exemplu pentru prima teoremă a lui Shannon
| N | Рх i | x i | Cod | n i | n i - ∙ P i | Рх i∙log Рх i |
| 1 | 0,19 | X 1 | 10 | 2 | 0,38 | -4,5522 |
| 2 | 0,16 | X 2 | 001 | 3 | 0,48 | -4,2301 |
| 3 | 0.16 | X 3 | 011 | 3 | 0,48 | -4,2301 |
| 4 | 0,15 | X 4 | 101 | 3 | 0,45 | -4,1054 |
| 5 | 0,12 | X 5 | 111 | 3 | 0,36 | -3,6706 |
| 6 | 0,11 | X 6 | 111 | 3 | 0,33 | - 3,5028 |
| 7 | 0,09 | X 7 | 1011 | 4 | 0,36 | -3,1265 |
| 8 | 0,02 | X 8 | 1001 | 4 | 0,08 | -3,1288 |
| Σ=1 | Σ=2,92 | Σ=2,85 |
^ A doua teoremă a lui Shannon afirmă că în prezența interferențelor în canal, este întotdeauna posibil să se găsească un sistem de codare în care mesajele să fie transmise cu o anumită fiabilitate. Dacă există o restricție debitului canalul trebuie să depășească capacitatea sursei mesajului. Astfel, a doua teoremă a lui Shannon stabilește principiile codificării corectoare de erori. Pentru un canal discret cu zgomot, teorema afirmă că dacă rata de generare a mesajelor este mai mică sau egală cu capacitatea canalului, atunci există un cod care asigură transmisia cu o rată de eroare arbitrară.
Demonstrarea teoremei se bazează pe următorul raționament. Inițial secvența X = (xi) codificat cu caractere din ÎN astfel încât să fie atins debitul maxim (canalul nu are interferențe). Apoi într-o secvență de ÎN lungime P introdus r caractere și este transmisă pe canal noua secventa din n + r personaje. Numărul de secvențe posibile de lungime și + T mai mare decât numărul de secvențe de lungime posibile P. Mulțimea tuturor secvențelor de lungime P + r poate fi descompus în P submulțimi, fiecare dintre acestea fiind asociată cu una dintre secvențele de lungime P. Dacă există interferență pe o secvență de P + rîl îndepărtează din submulțimea corespunzătoare cu probabilitate arbitrar mică.
Acest lucru face posibilă determinarea, pe partea de recepție a canalului, căreia îi aparține secvența recepționată de lungime, distorsionată de interferență. n + r,și astfel restabiliți secvența originală de lungime P.
Această teoremă nu oferă o metodă specifică de construire a unui cod, dar indică limitele a ceea ce se poate realiza în crearea codurilor rezistente la erori și stimulează căutarea unor noi modalități de rezolvare a acestei probleme.
Teoria codificării informației este una dintre ramurile informaticii teoretice. Principalele sarcini abordate în această secțiune includ următoarele:
dezvoltarea principiilor cel mai economic codificarea informațiilor;
coordonarea parametrilor informațiilor transmise cu caracteristicile canalului de comunicație;
dezvoltarea tehnicilor de asigurare fiabilitate transmiterea de informații prin canale de comunicare, de ex. fara pierderi de informatii.
Ultimele două sarcini sunt legate de procesele de transfer de informații – ele vor fi discutate în Capitolul. 5. Prima sarcină - codificarea informațiilor - se referă nu numai la transmiterea, ci și la prelucrarea și stocarea informațiilor, adică. acoperă o gamă largă de probleme; Soluția lor privată va fi reprezentarea informațiilor pe un computer. Să începem să stăpânim teoria codificării discutând aceste probleme.
3.1. Enunțul problemei de codificare. Prima teoremă a lui Shannon
După cum s-a menționat atunci când luăm în considerare conceptele inițiale ale informaticii, un anumit alfabet este folosit pentru a reprezenta mesaje discrete. Cu toate acestea, nu există o corespondență clară între informațiile conținute în mesaj și alfabetul acestuia.
Într-o serie de aplicații practice, este nevoie de a traduce un mesaj de mutare dintr-un alfabet în altul, iar o astfel de transformare nu ar trebui să ducă la pierderea de informații.
Să introducem o serie de definiții.
Vom presupune că sursa reprezintă informație sub forma unui mesaj discret, folosind în acest scop alfabetul, pe care vom fi de acord să-l numim în continuare. primar. Apoi, acest mesaj intră într-un dispozitiv care îl convertește și îl reprezintă într-un alt alfabet - vom numi acest alfabet secundar.
Cod - (1) o regulă care descrie corespondența semnelor sau combinațiile acestora din alfabetul primar cu semnele sau combinațiile lor din alfabetul secundar;.
(2) un set de caractere din alfabetul secundar, folosit pentru a reprezenta caractere sau combinațiile lor din alfabetul primar.
Codificare - traducerea informațiilor reprezentate de un mesaj în alfabetul primar într-o succesiune de coduri.
Decodare - operațiune inversă codării, i.e. restaurarea informațiilor din alfabetul primar conform secvenței de coduri primite.
Codificator - un dispozitiv care efectuează operația de codificare.
Decodor - dispozitiv care efectuează decodare.
Operațiile de codificare și decodare sunt numitereversibil, dacă aplicarea lor consecventă asigură revenirea la informațiile originale fără nicio pierdere.
Un exemplu de codificare reversibilă este reprezentarea caracterelor într-un cod telegrafic și recuperarea lor după transmitere. Un exemplu de codificare ireversibilă este traducerea dintr-o limbă naturală în alta - traducerea inversă, în general, nu restabilește textul original. Desigur, pentru problemele practice legate de reprezentarea simbolică a informației, capacitatea de a restaura informația folosind codul acesteia este o conditie necesara aplicarea codului, prin urmare, în prezentarea ulterioară ne vom limita să luăm în considerare doar codarea reversibilă.
Codificarea precede transmiterea și stocarea informațiilor. În acest caz, așa cum sa indicat mai devreme, stocarea este asociată cu fixarea unei anumite stări a purtătorului de informații, iar transmisia este asociată cu o schimbare a stării în timp (adică, un proces). Vom numi aceste stări sau semnale semnale elementare - totalitatea lor constituie alfabetul secundar.
Fără a discuta aspectele tehnice ale transmiterii și stocării mesajelor (adică modul în care sunt implementate efectiv transmisia și recepția secvențelor de semnal sau fixarea stărilor), vom încerca să oferim o formulare matematică a problemei de codificare.
Lasă alfabetul primar A este format din N caractere cu informații medii pe caracter eu(A), și alfabetul secundar ÎN- din M semne cu informații medii pe semn eu(ÎN). Să conțină și mesajul original, reprezentat în alfabetul primar P caractere, iar mesajul codificat este T semne. Dacă mesajul original conține euSf(A) informația, iar cea codificată este I fin (B), apoi condiția reversibilității codificării, i.e. nedispariție informațiile din timpul codificării pot fi scrise, evident, după cum urmează:
al cărui sens este că O operație de codare reversibilă poate crește cantitatea de informații dintr-un mesaj, dar nu o poate reduce. Cu toate acestea, fiecare dintre cantitățile din această inegalitate poate fi înlocuită cu produsul dintre numărul de semne și conținutul mediu de informații al semnului, adică:
Atitudine t/n, caracterizează evident numărul mediu de caractere din alfabetul secundar care trebuie utilizat pentru a codifica un caracter al alfabetului primar -îl vom chema lungimea codului sau lungimea lanțului de coduri si denota K(A,B). Prin urmare
De obicei N>M și I(A) > I(B), de unde K(A,B) > 1, adică. un caracter al alfabetului primar este reprezentat de mai multe caractere ale alfabetului secundar. Deoarece metodele de construire a codurilor cu alfabete fixe Ași B există o mulțime, se pune problema alegerii (sau construirii) celei mai bune opțiuni - o vom numi cod optim. Rentabilitatea codului la transmiterea și stocarea informațiilor este un factor economic, deoarece un cod mai eficient vă permite să cheltuiți mai puțină energie și timp pentru transmiterea mesajelor și, în consecință, să ocupați mai puțin din linia de comunicație; În timpul stocării, este utilizată o suprafață (volum) mai mică a suportului. În același timp, trebuie să știm că rentabilitatea codului nu este identică cu rentabilitatea în timp a întregului lanț de codare-transmisie-decodare; este posibilă o situație când utilizarea unui cod eficient în timpul transmisiei va trebui să plătească pentru faptul că operațiunile de codificare și decodare vor necesita mai mult timp și alte resurse (de exemplu, spațiu în memoria unui dispozitiv tehnic, dacă aceste operațiuni sunt efectuate cu ajutorul acestuia). Ajutor).
După cum urmează din β.1), valoarea minimă posibilă a lungimii medii a codului va fi:
Această expresie ar trebui percepută ca o relație de evaluare care stabilește o limită inferioară a lungimii codului; cu toate acestea, nu este clar din ea în ce măsură este posibilă aproximarea în schemele de codare reale. K(A,B) La Kmin(A,B). Din acest motiv, două teoreme demonstrate de Shannon sunt de cea mai mare importanță pentru teoria codificării și teoria comunicării. Primul, pe care îl vom analiza acum, se referă la situația de codificare în absența interferențelor care denaturează mesajul. A doua teoremă se aplică liniilor de comunicație reale cu zgomot și va fi discutată în Cap. 5.
Prima teoremă a lui Shannon, care se numește teorema principală despre codificare în absența interferenței, este formulat astfel:
În absența interferenței, este întotdeauna posibilă codificarea unui mesaj în așa fel încât numărul mediu de caractere de cod per caracter al alfabetului primar să fie în mod arbitrar apropiat de raportul dintre informațiile medii per caracter al alfabetului primar și secundar. .
Afirmația de mai sus este o teoremă și, prin urmare, trebuie demonstrată. O vom omite, trimițându-i pe cei interesați în mod specific de latura probatorie la cartea lui A. M. Yaglom și I. M. Yaglom. Este important pentru noi ca teorema să deschidă posibilitatea fundamentală de codificare optimă, adică. codul constructiei cu lungime medie LAmin(A,B). Cu toate acestea, este necesar să ne dăm seama că din teorema în sine nu decurge în niciun fel cum să implementăm o astfel de codificare în practică - pentru aceasta trebuie implicate câteva considerații suplimentare, care vor face obiectul discuției noastre ulterioare.
Din (3.2) este clar că există două moduri de a reduce K min (A,B):
reducerea numărătorului este posibilă dacă, la codificare, ținem cont de diferența de frecvențe de apariție a diferitelor caractere în mesaj, corelații cu două litere, trei litere etc. (în paragraful 2.3. s-a arătat că I 0 >I 1 >I 2 >…>I ∞);
creșterea numitorului - pentru aceasta este necesară utilizarea unei metode de codare în care apariția caracterelor alfabetului secundar ar fi la fel de probabilă, adică. I (B) = log 2 M.
ÎN situație particulară, considerată în detaliu de K. Shannon, la codificarea unui mesaj în alfabetul primar se iau în considerare diferitele probabilități de apariție a semnelor (ceea ce am numit „prima aproximare” în paragraful 2.3), totuși, corelațiile acestora nu sunt urmărite - sursele unor astfel de mesaje sunt apelate surse fără memorie. Dacă în același timp se asigură o probabilitate egală de apariție a caracterelor alfabetului secundar, atunci, după cum urmează din β.2), pentru lungimea medie minimă a codului, următoarea relație se dovedește a fi valabilă:
Ca măsură a excesului K(A,B) peste K min (A, B) se poate intra redundanță relativă a codului (Q(A,B):
Această valoare arată cât de mult a crescut operația de codificare lungimea mesajului original. Evident, Q(A,B)→ 0 la K(A,B)→LAmin(A,B).În consecință, soluția problemei de optimizare a codului este găsirea unor scheme de codare care să asigure că lungimea medie a codului se apropie de valoarea K min (AB), egală cu raportul informației medii pe semn al alfabetului primar și secundar. Este ușor să arăți că cu atât mai puțin Q(A,B), cu atât I fin (B) este mai aproape de Ist(A)), adică. Există mai puține informații asociate cu codificarea, codul este mai profitabil și operația de codificare este mai eficientă.
Folosind conceptul de redundanță de cod, putem construi o formulare diferită a teoremei lui Shannon:
În absența interferenței, este întotdeauna posibilă codificarea unui mesaj în așa fel încât redundanța codului să fie în mod arbitrar aproape de zero.
Cea mai importantă situație pentru practică este când M = 2, acestea. Pentru a reprezenta coduri într-o linie de comunicație, sunt utilizate doar două tipuri de semnale - din punct de vedere tehnic, aceasta este opțiunea cel mai ușor de implementat (de exemplu, existența tensiunii în fir (vom numi aceasta). impuls) sau lipsa acestuia ( pauză); prezența sau absența unei găuri pe o cartelă perforată sau a unei zone magnetizate pe o dischetă); se numeste acest tip de codare binar. Caracterele alfabetului binar sunt de obicei notate ca „O” și „1”, dar trebuie să vă gândiți la ele ca litere, nu numere. Comoditatea codurilor binare este că, cu durate și probabilități egale, fiecare semnal elementar (0 sau 1) poartă 1 bit de informație (log 2 M = 1); apoi de la β.3)
iar prima teoremă a lui Shannon primește următoarea interpretare:
În absența interferenței, lungimea medie a unui cod binar poate fi în mod arbitrar apropiată de informația medie pe caracter al alfabetului primar.
Aplicarea formulei (3.4) pentru mesajele surse binare fără memorie atunci când sunt codificate cu semne de probabilitate egală dă:
La decodificarea mesajelor binare se pune problema izolării din fluxul de semnale (secvențe de impulsuri și pauze) cuvinte de cod (grupuri de semnale elementare) corespunzătoare caracterelor individuale ale alfabetului primar. În acest caz, dispozitivul receptor înregistrează intensitateȘi durată semnale și, de asemenea, poate corela o anumită secvență de semnale cu una de referință ( tabelul de coduri).
Sunt posibile următoarele caracteristici ale alfabetului secundar utilizat în codificare:
semnalele elementare (0 și 1) pot avea aceeași durată (τ 0 =τ 1) sau diferite (τ 0 ≠τ 1);
lungimea codului poate fi aceeași pentru toate caracterele alfabetului primar (în acest caz, codul este numit uniformă) sau codurile diferitelor caractere ale alfabetului primar pot avea lungimi diferite ( neuniformă cod);
codurile pot fi construite pentru un caracter separat al alfabetului primar ( codificare alfabetică) sau pentru combinații ale acestora ( blocuri de codare, cuvinte).
Combinațiile dintre caracteristicile enumerate determină baza unei anumite metode de codare; cu toate acestea, chiar și cu aceeași bază, sunt posibile diferite opțiuni pentru construirea de coduri care diferă în eficacitatea lor. Următoarea noastră sarcină va fi să ne uităm la diferite scheme de codare pentru unele elemente de bază.
1.2. Prima teoremă a lui Shannon
S-a remarcat anterior că atunci când se transmit mesaje prin canale de comunicație, pot apărea interferențe care pot duce la distorsiunea caracterelor primite. Deci, de exemplu, dacă încercați să transmiteți un mesaj vocal pe vreme vântoasă unei persoane situate la o distanță considerabilă de dvs., atunci acesta poate fi foarte distorsionat de interferențe precum vântul. În general, transmiterea mesajelor în prezența interferenței este o problemă serioasă teoretică și practică. Importanța sa este în creștere datorită introducerii pe scară largă a telecomunicațiilor computerizate, în care interferențele sunt inevitabile.
Când se lucrează cu informații codificate distorsionate prin interferență, pot fi identificate următoarele probleme principale: stabilirea faptului însuși că a avut loc distorsiunea informației; aflarea exactă unde s-a întâmplat acest lucru în textul transmis; corectarea erorilor - cel puțin cu un anumit grad de certitudine.
Interferența în transmiterea informațiilor nu este în niciun caz o proprietate doar a sistemelor tehnice. Acesta este un lucru destul de comun în viața de zi cu zi. Exemplul era mai sus; alte exemple sunt vorbirea la telefon cu un trosnet, conducerea unei mașini în ceață etc. Cel mai adesea, o persoană se descurcă destul de bine cu fiecare dintre sarcinile de mai sus, deși nu este întotdeauna conștientă de modul în care o face (adică non-algoritmic, dar pe baza unor conexiuni asociative). Se știe că limbajul natural are o mare redundanță (în limbile europene - până la 70%), ceea ce explică imunitatea ridicată la zgomot a mesajelor compuse din caractere din alfabetele unor astfel de limbi. Un exemplu care ilustrează rezistența limbii ruse la interferență este propoziția „în slovacă vso glosnoo zomonono bokvoy o”. Aici 26% dintre personaje sunt „afectate”, dar acest lucru nu duce la o pierdere a sensului. Astfel, redundanța este o proprietate utilă în acest caz.
De exemplu, fiecare fragment de text („propoziție”) este transmis de trei ori, iar perechea de fragmente care coincid complet este considerată corectă. Cu toate acestea, redundanța ridicată duce la cantități mari de timp petrecut pentru transmiterea informațiilor și necesită o cantitate mare de memorie pentru stocarea acesteia. Acest lucru duce la sarcina de a elimina redundanța sau codificarea eficientă. K. Shannon a fost primul care a întreprins un studiu teoretic al acestui gen de problemă.
Prima teoremă a lui Shannon despre transmiterea informațiilor, numită și teorema fundamentală a codării în absența interferenței, este formulată după cum urmează:
În absența interferențelor de transmisie, este întotdeauna posibilă codificarea unui mesaj în așa fel încât numărul mediu de caractere de cod per caracter al alfabetului codificat să fie în mod arbitrar apropiat de raportul dintre informațiile medii pe caracterul primar și secundar. alfabete.
Folosind conceptul de redundanță de cod, putem da o formulare mai scurtă a teoremei:
În absența interferenței de transmisie, este întotdeauna posibilă codificarea unui mesaj în așa fel încât redundanța codului să fie în mod arbitrar aproape de zero.
Aceste afirmații sunt teoreme și, prin urmare, trebuie demonstrate, dar vom omite demonstrațiile. Este important pentru noi ca teorema să deschidă posibilitatea fundamentală de codificare optimă. Cu toate acestea, este necesar să ne dăm seama că din teoremă în sine nu decurge în niciun fel modul de implementare a unei astfel de codări în practică - pentru aceasta trebuie implicate câteva considerații suplimentare, care vor face obiectul unei discuții ulterioare.
Astfel, codarea optimă este în principiu posibilă.
Cea mai importantă situație pentru practică este atunci când M = 2, adică informația este codificată cu doar două semnale 0 și 1.
Shannon a luat în considerare situația în care, la codificarea unui mesaj în alfabetul primar, sunt luate în considerare diferite probabilități de apariție a caracterelor, precum și o probabilitate egală de apariție a caracterelor din alfabetul secundar. Apoi:
K min (A, B)= I (A) / log 2 M= I (A),
aici I (A) este informația medie per semn al alfabetului primar.
Să ne limităm la situația când M = 2, adică. Pentru a reprezenta coduri într-o linie de comunicație, sunt utilizate doar două tipuri de semnale - opțiunea cea mai ușor de implementat. Acest tip de codificare se numește binară. Semnele alfabetului binar sunt de obicei notate „0” și „1. Comoditatea codurilor binare constă în faptul că fiecare semnal elementar (0 sau 1) transportă 1 bit de informație (log 2 M = 1), apoi de la ( 1), teorema lui Shannon:
I 1 (A) ≤ K (2)
iar prima teoremă a lui Shannon primește următoarea interpretare:
În absența interferenței de transmisie, lungimea medie a unui cod binar poate fi în mod arbitrar apropiată de informația medie pe caracter al alfabetului primar.
Determinarea cantității de informații transmise în timpul codificării binare se reduce la simpla numărare a numărului de impulsuri (unu) și pauze (zero). În acest caz, apare problema izolării codurilor individuale de fluxul de semnal (secvență de impulsuri și pauze). Dispozitivul receptor înregistrează intensitatea și durata semnalelor. Semnalele elementare (0 și 1) pot avea durate identice sau diferite. Numărul lor din cod (lungimea lanțului de coduri), care este atribuit unui semn al alfabetului primar, poate fi, de asemenea, același (în acest caz, codul se numește uniform) sau diferit (cod inegal). În final, se pot construi coduri pentru fiecare caracter al alfabetului sursă (codificare alfabetică) sau pentru combinațiile acestora (codificare de blocuri, cuvinte). Ca urmare, la codificare (alfabetică și verbală), sunt posibile următoarele combinații:
Tabelul 1. Opțiuni de combinare
|
Durata cipului |
Codificarea caracterelor primare (cuvinte) |
Situatie |
|
aceeași |
uniformă |
|
|
aceeași |
neuniformă |
|
|
uniformă |
||
|
neuniformă |
În cazul utilizării codării inegale sau a semnalelor de durată diferită (situațiile (2), (3) și (4)), pentru a separa codul unui caracter de altul între ele, este necesar să se transmită un semnal special - un timp separator (semnul de sfârșit al caracterului) sau folosiți astfel de coduri care se dovedesc a fi unice, de ex. incompatibil cu părți ale altor coduri. Cu codificare uniformă cu semnale de durată egală (situația (1)), nu este necesară transmiterea unui separator special, deoarece separarea unui cod de altul se realizează în funcție de durata totală, care se dovedește a fi aceeași pentru toate codurile (sau acelasi numar bit când este stocat).
Durata unui impuls binar elementar arată cât timp este nevoie pentru a transmite 1 bit de informație. Evident, este nevoie de timp pentru a transmite informații, în medie pe semn al alfabetului primar. Astfel, problema optimizării codării poate fi formulată în alți termeni: construiți un sistem de codare astfel încât durata totală a codurilor în timpul transmisiei (sau numărul total de coduri în timpul stocării) unui mesaj dat să fie minimă.
Dacă există o sursă de informație cu entropie H(x) și un canal de comunicare cu capacitate C, atunci dacă C > H(X), atunci este întotdeauna posibil să se codifice suficient mesaj lungîn aşa fel încât să fie transmisă fără întârziere. Dacă, dimpotrivă, C
Prima teoremă a lui Shannon declară posibilitatea creării unui sistem de codificare eficientă a mesajelor discrete, în care numărul mediu de simboluri binare per simbol de mesaj tinde asimptotic către entropia sursei mesajului (în absența interferenței).
Prima teoremă a lui Shannon (reformulare).
În absența interferenței, lungimea medie a unui cod binar poate fi în mod arbitrar apropiată de informația medie pe caracter al alfabetului primar.
Care pot fi caracteristicile alfabetului secundar la codificare:
Codurile elementare 0 și 1 pot avea aceeași durată (t0=t1) sau diferită (≠).
Lungimea codului poate fi aceeași pentru toate caracterele alfabetului primar (cod uniform) sau diferită (cod neuniform)
Codurile pot fi construite pentru un singur caracter al alfabetului primar (codificare alfabetică) sau pentru combinațiile acestora (codificare de blocuri, cuvinte).
1.3 A doua teoremă a lui Shannon
Raportul dintre capacitatea canalului de comunicație și viteza de transmitere nedistorsionată a simbolurilor alfabetice ale mesajului transmis trebuie să fie mai mare sau egal cu entropia de transmitere a unui simbol.
A doua teoremă a lui Shannon afirmă că, în prezența interferenței în canal, este întotdeauna posibil să se găsească un sistem de codare în care mesajele să fie transmise cu o anumită fiabilitate. Dacă există o constrângere, capacitatea canalului trebuie să depășească capacitatea sursei mesajului. A doua teoremă a lui Shannon stabilește principiile codificării corectoare de erori. Pentru un canal discret cu zgomot, teorema afirmă că dacă rata de creare a mesajelor este mai mică sau egală cu capacitatea canalului, atunci există un cod care asigură transmisia cu o rată de eroare arbitrar scăzută.
Demonstrarea teoremei se bazează pe următorul raționament. Inițial, secvența X=(x i ) este codificată cu simboluri din B astfel încât să fie atins debitul maxim (canalul nu are interferență). Apoi r simboluri sunt introduse într-o secvență de B de lungime n și o nouă secvență de n + r simboluri este transmisă pe canal. Numărul de secvențe posibile de lungime n + r este mai mare decât numărul de secvențe posibile de lungime n. Mulțimea tuturor secvențelor de lungime n + r poate fi împărțită în n submulțimi, fiecare dintre ele fiind asociată cu una dintre secvențele de lungime n. Dacă există interferență pe o secvență de n + r, aceasta o elimină din submulțimea corespunzătoare cu o probabilitate arbitrar mică.Codificarea informațiilor (4) Rezumat >> Informatică
Cuprins I. Istorie codificare informații……………………………..3 II. Codificare informații……………………………………………………4 III. Codificare informații text…………………………….4 IV. ... și umanitatea în ansamblu. Dar depinde de tine să decizi sarcină codificare omenirea a început informarea cu mult înainte...
Codificareși criptarea informațiilor
Rezumat >> InformaticăPrieteni. Atunci a apărut sarcină protecția acestei corespondențe împotriva excesive... încercat să o folosească pentru a rezolva acest lucru sarcini o varietate de metode și... software pe sistem universal codificare. Codificare date grafice Dacă luați în considerare cu...
Codificare numere, simboluri și informații grafice, unități de date
Test >> Informatică... Nr. 2………………………………………………..8 SARCINA PRACTICĂ Nr. 3…………………………………………………………………. .9 REFERINȚE…………………………………………………..unsprezece CODARE NUMERE, SIMBOLULE ȘI INFORMAȚII GRAFICE, UNITĂȚI... calculul funcției: Y = Algoritm pentru rezolvarea acesteia sarcini va arăta astfel: Pe baza datelor primite...
Codificare informații despre vorbire
Rezumat >> Informatică... sarcină, căruia metoda de selecție a frecvenței nu le poate face față. Descrierea metodei codificare... Introducere 2 Sistem codificare discurs 4 Motivul alegerii unei metode codificare 4 Descrierea metodei codificare 5 Generator pseudo-aleatoriu...
Să fie o sursă de informație X și un receptor Y, conectat prin canal K. Este cunoscută productivitatea sursei de informaţie H 1 (X), adică. cantitate medie unități binare informație provenind de la o sursă pe unitatea de timp (numeric este egală cu entropia medie a mesajului produs de sursă pe unitatea de timp). Capacitatea canalului C1 este cunoscută, adică. cantitatea maximă de informații pe care un canal este capabil să o transmită în aceeași unitate de timp. Se pune întrebarea: care ar trebui să fie capacitatea canalului pentru ca acesta să-și facă față sarcinii sale, de ex. astfel încât informațiile de la sursă la receptor să ajungă fără întârziere?
Chiar dacă răspunsul este deja evident, este dat în prima teoremă a lui Shannon.
Prima teoremă a lui Shannon:
Dacă capacitatea canalului de comunicaţie C 1 este mai mare decât entropia sursei de informaţie pe unitatea de timp
C1 > H1 (X),
atunci este întotdeauna posibilă codificarea unui mesaj suficient de lung astfel încât să fie transmis fără întârziere printr-un canal de comunicație.
Dacă, dimpotrivă,
C 1< Н 1 (Х),
atunci transferul de informații fără întârziere este imposibil.
Transmiterea de informații cu distorsiuni.
Capacitatea canalului cu interferențe.
Atât teorema 1 a lui Shannon, cât și ambele metode de codare pe care le-am considerat se referă la transmiterea de informații fără erori. În realitate, acest proces este însoțit inevitabil de erori (distorsiuni). Un canal de transmisie în care este posibilă distorsiunea se numește canal de interferență (sau zgomot).
Este destul de evident că prezența interferențelor duce la pierderea de informații. Pentru a primi cantitatea necesară de informații la receptor în prezența interferențelor, este necesar să se ia măsuri speciale. Una dintre aceste măsuri este introducerea așa-numitei „redundanțe”. Se știe că toate limbile vii au o oarecare redundanță, ajungând până la 50% (adică nu am putut pronunța deloc 50% din litere sau să le amestecăm :-)).
Iată un exemplu: Conform rzelulattam ilsseovadniy odongo anligysokgo unviertiseta, nu ieemt zanchneya, în kokam pryakde rsapozholeny bkuvy v solva. Galvone, astfel încât să pre-avya și psloendya bkvuy blyi pe mseta. Osatlyne bkvuy mgout seldovt în ploonm bsepordyak, totul este rupt tkest chtaitsey fără rătăcire.
Sper că înțelegi ce scrie aici))))
Cu toate acestea, pentru o transmisie fără erori, redundanța naturală a limbajului poate fi fie excesivă, fie insuficientă: totul depinde de cât de mare este pericolul distorsiunii. Folosind metodele teoriei informației, este posibil să se găsească gradul necesar de redundanță al sursei de informații pentru fiecare nivel de interferență.
Luați în considerare, de exemplu, următoarea problemă. Canalul de comunicație K transmite de la sursa de informații X către receptorul Y simbolurile elementare 0 și 1 în cantitate de k simboluri pe unitatea de timp. În timpul procesului de transmitere, fiecare simbol, indiferent de celelalte, cu probabilitate μ poate fi distorsionat (adică înlocuit cu cel opus). Trebuie să găsim capacitatea canalului.
Să definim mai întâi informatii maxime pe caracter pe care îl poate transmite canalul. Fie ca sursa să producă simbolurile 0 și 1 cu probabilitățile p și 1-p.
Atunci entropia sursei va fi
H(X)=-p log p - (1-p) log (1-p).
Dacă transmiterea mesajelor nu ar fi însoțită de erori, atunci cantitatea de informații pe simbol ar fi egală cu entropia sistemului X. Dacă există erori, aceasta va fi mai mică:
I = H(Y) - H(Y/X).
Pentru a găsi entropia condiționată totală Н(У/Х), găsim mai întâi entropiile condiționate parțiale: Н(У/х 1) și Н(У/х 2).
Să calculăm H(Y/x 1); Pentru a face acest lucru, presupunem că este transmis simbolul 0. Să găsim probabilitățile condiționate ca în acest caz sistemul Y să fie în starea y 1 = 0 și în starea y 2 = 1. Prima dintre ele este egală cu probabilitatea ca semnalul să nu fie confuz:
P(y1/x1)=1-p;
a doua este probabilitatea ca semnalul să fie amestecat:
P(y2/x1)=p.
Entropia condiționată H(U/x 1) va fi:
H(Y/x1)=-Σ P(yi/x1) log P(yi/x1) = -(1-u) log (1-u) - ulog u.
Să găsim acum entropia condiționată a sistemului Y, cu condiția ca semnalul 1 să fie transmis:
P(y1/x2)=p; P(y2/x2)=1-µ,
Н(У/х 2)= - µ log µ - (1-µ) log (1-µ).
Prin urmare
N(U/x 1) = N(U/x 2).
Entropia condiționată totală H(Y/X) se obține dacă facem media entropiilor condiționate ținând cont de probabilitățile p și 1-p. Întrucât entropiile condiționate parțiale sunt egale, atunci
H(U/X)= - ulog u - (1-u) log (1-u).
Concluzie: entropia condiționată Н(У/Х) nu depinde deloc de probabilitățile cu care apar simbolurile 0 și 1 mesaj transmis, dar depinde numai de probabilitatea de eroare µ.
Acum calculați informațiile transmise de un caracter:
I = H(Y) - H(Y/X) = - r log r - (1-r) log (1-r) - - µ log µ - (1-µ) log (1-µ) =
= [η(r) + η(1-r)] - [η(µ) + η(1-µ)],
Unde r este probabilitatea ca simbolul 0 să apară în ieșire.
Știm că entropia și cantitatea de informații sunt maxime pentru semnale la fel de probabile, adică. (în cazul nostru) la p=1/2. Prin urmare, cantitatea maximă de informații transmise printr-un simbol
I max = 1 - [η(µ) + η(1-µ)],
Iar capacitatea canalului de comunicare va fi egală cu
С= k(1 - [η(µ) + η(1-µ)]).
Rețineți că η(µ) + η(1-µ) este entropia unui sistem având 2 stări posibile cu probabilități µ și 1-µ. Caracterizează pierderea de informații pe simbol asociată cu prezența interferenței.
Exemplul 1. Determinați capacitatea unui canal de comunicație capabil să transmită 100 de simboluri 0 sau 1 pe unitatea de timp, fiecare simbol fiind distorsionat (înlocuit cu opusul) cu probabilitatea µ=0,001.
η(µ) = η(0,001) = 0,0664
η(1-u) = 0,0144
η(µ) + η(1-µ) = 0,0808
Se pierd 0,0808 biți de informații per caracter. Capacitatea canalului este
C = 100(1-0808) = 91,92 ≈ 92 biți pe unitate de timp.
Cunoscând capacitatea canalului, este posibil să se determine limita superioară a vitezei de transmitere a informațiilor pe un canal zgomotos. A doua teoremă a lui Shannon se aplică în acest caz.
A doua teoremă a lui Shannon:
Să existe o sursă de informație X, a cărei entropie pe unitatea de timp este egală cu H 2 (X) și un canal cu capacitate C 2 . Atunci dacă
H2 (X) > C2,
Apoi, cu orice codificare, transmiterea mesajelor fără întârzieri și distorsiuni este imposibilă. Dacă
N 2 (X)< С 2 ,
Atunci este întotdeauna posibil să se codifice un mesaj suficient de lung, astfel încât să fie transmis fără întârzieri și distorsiuni cu o probabilitate arbitrar apropiată de unu.
Exemplul 2. Există o sursă de informație cu entropie pe unitatea de timp H(X) = 100 biți și 2 canale de comunicare; fiecare dintre ele poate transmite 70 de caractere binare (0 sau 1) pe unitatea de timp; fiecare semn binar este înlocuit cu cel opus cu probabilitatea µ=0,1. Este necesar să aflăm: este suficientă capacitatea acestor canale pentru a transmite informația furnizată de sursă?
Soluție: Determinați pierderea de informații per caracter:
η(µ) + η(1-µ) = 0,332+0,137=0,469 biți
Suma maximă informații transmise pe un canal pe unitatea de timp:
C = 70(1-0,469) = 37,2 biți.
Cantitatea maximă de informații care poate fi transmisă pe două canale pe unitatea de timp:
37,2*2 = 74,7 biți,
ceea ce nu este suficient pentru a asigura transmiterea informaţiei din sursă.
| 2 |
