Spațiu de eveniment aleatoriu
În 1946, statisticianul american John Tukey a propus numele BIT
Imaginați-vă un spațiu de evenimente aleatoriicare constă în aruncarea unei monede false, pe ambele părți ale cărora este un vultur. Când cade vulturul? Este clar că întotdeauna. Știm acest lucru în avans, pentru că spațiul nostru este aranjat. Căderea unui vultur este un eveniment fiabil, adică probabilitatea lui este egală cu 1. Vom oferi multe informații dacă spunem despre vultur căzut? Nu. Cuantumul de informații din acest mesaj, vom fi considerați egali cu 0.
Acum să aruncăm moneda corectă:pe o parte sunt capete, iar pe cealaltă, cozi, așa cum ar trebui să fie. Capetele sau cozile de aterizare vor fi două evenimente diferite care alcătuiesc spațiul nostru de evenimente aleatorii. Dacă raportăm rezultatul unei aruncări, va fi într-adevăr informații noi. Dacă se scapă capete, vom raporta 0, iar dacă cozile sunt 1. Pentru a raporta această informație, avem nevoie doar de 1 bit.
Ce sa schimbat?În spațiul nostru de evenimente a apărut incertitudinea. Avem ceva de spus despre asta cuiva care nu aruncă el însuși o monedă și nu vede rezultatul aruncării. Dar pentru a înțelege corect mesajul nostru, el trebuie să știe exact ce facem și ce înseamnă 0-urile și 1-urile.Spațiile de eveniment trebuie să se potrivească, iar procesul de decodificare este unic pentru a restabili rezultatul aruncării.Dacă spațiul de evenimente al emițătorului și al receptorului nu coincide sau nu există posibilitatea decodării fără ambiguitate a mesajului, informația va rămâne doar zgomot în canalul de comunicație.
Dacă arunci două independent și simultanmonede, atunci vor exista patru rezultate diferite la fel de probabile: cap-capete, cap-cozi, cozi-capete și cozi-cozi. Pentru a transmite informații, vom avea nevoie de 2 biți, iar mesajele noastre vor fi următoarele: 00, 01, 10 și 11. Există de două ori mai multe informații. Acest lucru s-a întâmplat deoarece incertitudinea a crescut. Dacă încercăm să ghicim rezultatul unei astfel de aruncări în pereche, avem de două ori șanse să greșim.
Cu cât este mai mare incertitudinea spațiului evenimentului, cu atât mai multe informații conține mesajul despre starea acestuia.
Să ne complicăm puțin spațiul de evenimente.Până acum, toate evenimentele care s-au petrecut au fost la fel de probabile. Dar în spațiile reale, nu toate evenimentele au probabilitate egală. Să presupunem că probabilitatea ca cioara pe care o vedem să fie neagră este aproape de 1. Probabilitatea ca primul trecător pe care îl întâlnim pe stradă să fie bărbat este de aproximativ 0,5. Dar întâlnirea cu un crocodil pe străzile Moscovei este aproape imposibilă. În mod intuitiv, înțelegem că un raport despre o întâlnire cu un crocodil are o valoare informativă mult mai mare decât despre o cioară neagră.Cu cât probabilitatea unui eveniment este mai mică, cu atât mai multe informații din mesajul despre un astfel de eveniment.
Lăsați spațiul de eveniment să nu fie atât de exotic. Stăm doar la fereastră și uităm la mașinile care trec. Sunt trecute mașini de patru culori, pe care trebuie să le raportăm. Pentru a face acest lucru, vom codifica culorile: negru - 00, alb - 01, roșu - 10, albastru - 11. Pentru a raporta exact ce mașină a condus, trebuie doar să transferăm 2 biți de informații.
Dar, de multă vreme, uitându-te la mașini,observăm că culoarea mașinilor este distribuită inegal: negru - 50% (în fiecare secundă), alb - 25% (fiecare al patrulea), roșu și albastru - 12,5% (la fiecare opt). Apoi puteți optimiza informațiile transmise.
Majoritatea mașinilor sunt negre, decisă notăm negru - 0 - cel mai scurt cod și lăsăm codul tuturor celorlalți să înceapă la 1. Din jumătatea rămasă, alb - 10, iar culorile rămase încep de la 11. În cele din urmă, să notăm roșu - 110 și albastru - 111.
Acum, trecând informații despre culoarea mașinii, o putem codifica mai îndeaproape.
Shannon Entropia
Fie ca spațiul nostru de evenimente să fie format din ndiferite evenimente. Când aruncați o monedă cu două capete există exact un astfel de eveniment, când aruncați o monedă corectă există exact 2, când aruncați două monede sau vizionați mașini există exact 4. Fiecare eveniment are o probabilitate de apariție. Când aruncați o monedă cu două capete, există un eveniment (căderea capetelor) și probabilitatea acestuia este p1 = 1. Când aruncați o monedă corectă, există două evenimente, sunt la fel de probabile și probabilitatea fiecăruia este de 0,5: p1 = 0,5, p2 = 0,5. Când aruncați două monede corecte, există patru evenimente, toate sunt la fel de probabile și probabilitatea fiecăreia este de 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. La observarea mașinilor, există patru evenimente și au probabilități diferite: negru - 0,5, alb - 0,25, roșu - 0,125, albastru - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Aceasta nu este o coincidență.Shannon a ales entropia (o măsură a incertitudinii în spațiul evenimentului), astfel încât au fost îndeplinite trei condiții:
- 1 Entropia unui eveniment de încredere, a cărui probabilitate este 1, este egală cu 0.
- Entropia a două evenimente independente este egală cu suma entropiilor acestor evenimente.
- Entropia este maximă dacă toate evenimentele sunt la fel de probabile.
Toate aceste cerințe sunt pe deplin în concordanță cu noastreidei despre incertitudinea spațiului evenimentului. Dacă există un singur eveniment (primul exemplu), nu există nicio incertitudine. Dacă evenimentele sunt independente - incertitudinea sumei este egală cu suma incertitudinilor - pur și simplu se adună (exemplul aruncării a două monede). Și în sfârșit, dacă toate evenimentele sunt la fel de probabile, atunci gradul de incertitudine al sistemului este maxim. Ca și în cazul aruncării a două monede, toate cele patru evenimente sunt la fel de probabile și entropia este 2, este mai mare decât în cazul mașinilor, când sunt și patru evenimente, dar au probabilități diferite - în acest caz entropia este 1,75.
Mărimea H joacă un rol central în teoria informației ca măsură a informațiilor, alegerii și incertitudinii.
Claude Shannon
Claude Elwood Shannon- inginer american, criptoanalist șimatematician. Considerat „părintele erei informației”. Fondator al teoriei informației, care și-a găsit aplicație în sistemele moderne de comunicații high-tech. A furnizat concepte fundamentale, idei și formulările lor matematice care formează în prezent baza pentru tehnologiile moderne de comunicare.
În 1948, sa propus utilizarea cuvântului "bit"pentru a indica cea mai mică unitate de informații. El a demonstrat de asemenea că entropia introdusă de el este echivalentă cu incertitudinea informațiilor din mesajul transmis. Articolele lui Shannon "Teoria matematică a comunicării" și "Teoria comunicării în sistemele secrete" sunt considerate fundamentale pentru teoria informațiilor și criptografia.
În timpul celui de-al Doilea Război Mondial, Shannon a lucrat la Laboratoarele Bell pentru a dezvolta sisteme criptografice, care mai târziu l-au ajutat să descopere metode de codare de corectare a erorilor.
Shannon a adus o contribuție esențială la teoria sistemelor probabiliste, teoria jocurilor, teoria automatelor și teoria sistemelor de control - domenii ale științei care fac parte din conceptul de cibernetică.
de codificare
Și aruncate monede, iar mașinile care trec nu suntsunt similare cu numerele 0 și 1. Pentru a raporta evenimentele care apar în spații, trebuie să vă gândiți la o modalitate de a descrie aceste evenimente. Această descriere se numește codificare.
Mesajele pot fi codificate într-un număr infinit de moduri diferite. Dar Shannon a arătat că cel mai scurt cod nu poate fi mai mic în biți decât entropia.
De aceea, entropia unui mesaj este o măsurăinformațiile din mesaj. Deoarece în toate cazurile luate în considerare numărul de biți în timpul codificării este egal cu entropia, aceasta înseamnă că codificarea a fost optimă. Pe scurt, nu mai este posibilă codificarea mesajelor despre evenimentele din spațiile noastre.
Cu o codificare optimă, nu puteți pierde saudistorsionează un singur bit transmis în mesaj. Dacă chiar și un bit este pierdut, informațiile vor fi distorsionate. Dar toate canalele reale de comunicare nu oferă 100% încredere că toate părțile mesajului vor ajunge la destinatar nedistorsionate.
Pentru a remedia această problemă trebuie să facețicodul nu este optim, ci redundant. De exemplu, transmiteți împreună cu mesajul suma de control a acestuia - o valoare special calculată, obținută la conversia codului mesajului și care poate fi verificată prin recalcularea la primirea mesajului. Dacă suma de control transmisă se potrivește cu cea calculată, probabilitatea ca transmisia să fie fără erori va fi destul de mare. Și dacă suma de control nu se potrivește, atunci trebuie solicitată o retransmisie. Cam așa funcționează astăzi majoritatea canalelor de comunicare, de exemplu, atunci când se transmit pachete de informații prin Internet.
Mesaje de limbă naturală
Luați în considerare spațiul de eveniment care constăde la posturi în limbaj natural. Acesta este un caz special, dar unul dintre cele mai importante. Evenimentele vor fi caracterele transmise (literele unui alfabet fix). Aceste caractere se găsesc în limba cu probabilități diferite.
Simbolul celei mai frecvente (adică unul carese găsește cel mai adesea în toate textele scrise în limba rusă) este un spațiu: de o mie de caractere, un spațiu mediu este găsit de 175 de ori. Al doilea în frecvență este simbolul "o" - 90, urmat de alte vocale: "e" (sau "e" - nu le vom distinge) - 72, "a" - 62 și i - primul consonant "t" - 53. Și cel mai rar "f" - acest simbol se găsește doar de două ori pe mia de caractere.
Vom folosi alfabetul de 31 de litere din limba rusălimba (nu diferă "e" și "e", precum și "ъ" și "ь"). Dacă toate literele s-au întâlnit în limba cu aceeași probabilitate, atunci entropia pe simbol ar fi H = 5 biți, dar dacă luăm în considerare frecvențele reale ale simbolurilor, entropia va fi mai mică: H = 4,35 biți. (Acest lucru este aproape de două ori mai mic decât în cazul codării tradiționale, atunci când un caracter este transmis ca un octet - 8 biți).
Dar entropia personajului în limbă este chiar mai mică. Probabilitatea apariției următorului personaj nu este complet predeterminată de frecvența medie a personajului în toate textele. Caracterul care va urma va depinde de caracterele deja transferate. De exemplu, în limba rusă modernă, după simbolul "ъ" nu se poate urma sunetul simbolului consoanat. După două vocale consecutive "e", a treia vocală "e" urmează extrem de rar, cu excepția cazului în cuvântul "cu gât lung". Adică, următorul personaj este într-o oarecare măsură predeterminat. Dacă luăm în considerare o astfel de valoare predeterminată a simbolului următor, incertitudinea (adică informația) a simbolului următor va fi chiar mai mică de 4,35. Conform unor estimări, următorul simbol în limba rusă este predeterminat de structura limbii cu mai mult de 50%, adică cu codare optimă, toate informațiile pot fi transmise prin ștergerea a jumătate din literele din mesaj.
Un alt lucru este că nu toate literele pot fi șterse în siguranță. Înaltă frecvență "o" (și în general vocale), de exemplu, este ușor de traversat, dar rare "f" sau "e" este destul de problematică.
Limbajul natural în care comunicăm unii cu alții este extrem de redundant și, prin urmare, de încredere; dacă am auzit greșit ceva, este în regulă, informațiile vor fi în continuare transmise.
Dar până când Shannon a introdus măsura de informații, nu am putut înțelege că limba este redundantă și în ce măsură putem comprima mesajele (și de ce fișierele text sunt atât de bine comprimate de arhivator).
Limbă de redundanță naturală
În articolul "Despre cum vom vorpsimanie tektkt"(numele sună exact așa!) un fragment al romanului lui Noble Nest al lui Ivan Turgenev a fost luat și supus unei transformări: 34% din litere, dar nu aleatoare, au fost șterse din fragment. Prima și ultima literă în cuvinte au fost lăsate, doar vocalele au fost șterse, și nu toate. Scopul nu a fost doar de a avea ocazia de a recupera toate informațiile de pe textul convertit, dar și de a se asigura că persoana care citește acest text nu a întâmpinat dificultăți deosebite din cauza lipsei de scrisori.
De ce este relativ ușor să citiți acest lucru corupttext? Conține de fapt informațiile necesare pentru a reconstrui cuvinte întregi. Un vorbitor nativ de rusă are un anumit set de evenimente (cuvinte și propoziții întregi) pe care le folosește ca recunoaștere. În plus, vorbitorul are la dispoziție și structuri de limbaj standard care îl ajută să recupereze informații. De exemplu,"Ea este blee blee"- cu o mare probabilitate poate fi citit ca"Era mai sensibilă.". Dar luate separat"E mai bla", mai degrabă, va fi restaurat ca"Ea era mai albă". Din moment ce în comunicarea de zi cu zi avem de-a facecu canale în care există zgomot și interferență, ne descurcăm destul de bine la restabilirea informațiilor, dar numai a celor pe care le știm deja dinainte. De exemplu, fraza"Caracteristicile ei nu sunt în cel mai puțin plăcut, htya nmngo rspkhli și splash"citește bine cu excepția ultimului cuvânt"Splash" - "rallied". Acest cuvânt nu se află în lexicul modern. Când citești rapid un cuvânt"Splls"se citește mai degrabă ca „lipiți împreună”; când este lent, pur și simplu derutează.
Digitalizarea semnalului
Sunetul sau oscilațiile acustice sunt sinusoide. Acest lucru poate fi văzut, de exemplu, în ecranul editorului de sunet. Pentru a transmite cu exactitate sunetul, veți avea nevoie de un număr infinit de valori - întregul val sinusoidal. Acest lucru este posibil cu o conexiune analogică. El cântă - ascultați, contactul nu este întrerupt în timp ce cântecul durează.
În comunicarea digitală pe un canal, putem transmite doar un număr finit de valori. Înseamnă asta că sunetul nu poate fi reprodus cu acuratețe? Se dovedește că nu.
Sunetele diferite sunt o undă sinusoidală diferită.Transmitem numai valori discrete (frecvențe și amplitudini), iar valul sinusurilor în sine nu trebuie transmis - dispozitivul receptor poate genera.Ea generează o sinusoidă și este suprapusă peste aceastamodulație creată din valori transmise printr-un canal de comunicare. Există principii exacte ale căror valori discrete trebuie transmise, astfel încât sunetul de la intrarea în canalul de comunicație să coincidă cu sunetul de la ieșire, unde aceste valori sunt suprapuse pe o sinusoidă standard (aceasta este teorema lui Kotelnikov). despre).
Teorema Kotelnikov (în literatura de limbă engleză - teorema Nyquist - Shannon, teorema de citire)- o afirmație fundamentală în domeniul digitaluluiprocesarea semnalului, conectând semnale continue și discrete și afirmând că „orice funcție F(t), constând din frecvențe de la 0 la f1, poate fi transmisă continuu cu orice precizie folosind numere care se succed în interval de 1/(2*f1) secunde
Codificare anti-interferență. Codurile Hamming
Dacă pe un canal nesigură de transmisTextul codat al lui Ivan Turgenev, cu unele erori, va avea ca rezultat un text destul de semnificativ. Dar dacă avem nevoie să transferăm totul puțin, sarcina va fi nerezolvată: nu știm ce biți sunt greșite, deoarece eroarea este aleatorie. Chiar și suma de control nu este întotdeauna salvată.
De aceea astăzi când transmitem date desprerețelele nu au tendința de codificare optimă, în care cantitatea maximă de informații poate fi împinsă în canal, ci mai degrabă o astfel de codificare (evident redundantă) în care erorile pot fi recuperate - la fel ca atunci când citim cuvintele din fragmentul lui Ivan Turgenev.
Există coduri speciale de corectare a erorilor care vă permit să recuperați informațiile după o eroare. Unul dintre ele este codul Hamming.Să presupunem că întreaga noastră limbă este formată din trei cuvinte:111000, 001110, 100011. Atât sursa mesajului, cât și receptorul cunosc aceste cuvinte. Și știm că erorile apar într-un canal de comunicare, dar la transmiterea unui cuvânt, nu este distorsionat mai mult de un bit de informație.
Să presupunem că vom trece mai întâi cuvântul 111000. Ca urmare, nu mai mult de o eroare (am identificat eroarea) se poate transforma într-una dintre următoarele cuvinte:
1) 111000,011.000, 101000, 110000, 111100, 111010, 111001.
Când transmiteți cuvântul 001110, oricare dintre cuvinte poate fi obținut:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
În cele din urmă, pentru 100011 putem ajunge la recepție:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010.
Rețineți că toate cele trei liste nu sunt în perechi.se intersectează. Cu alte cuvinte, dacă la celălalt capăt al canalului de comunicare apare orice cuvânt din lista 1, destinatarul știe sigur că cuvântul 111000 i-a fost transmis și dacă apare vreun cuvânt din lista 2, cuvântul 001110 și din lista 3, apare cuvântul 100011. Ei spun că codul nostru a fixat o eroare.
Corecția s-a produs din cauza a doi factori.În primul rând, destinatarul cunoaște întregul "dicționar", adică spațiul de eveniment al destinatarului mesajului coincide cu spațiul celui care a transmis mesajul. Când codul a fost transmis cu o singură eroare, a ieșit un cuvânt, care nu era în dicționar.
În al doilea rând, cuvintele din dicționar au fost alese într-un mod special.Chiar dacă a apărut o eroare, destinatarul nu a pututconfunda un cuvânt cu altul. De exemplu, dacă dicționarul constă din cuvintele „fiică”, „punct”, „bump”, iar în timpul transmiterii rezultatul a fost „vochka”, atunci destinatarul, știind că un astfel de cuvânt nu există, nu ar putea corectați eroarea - oricare dintre cele trei cuvinte se poate dovedi a fi corect. Dacă dicționarul include „punct”, „daw”, „ramură” și știm că nu este permisă mai mult de o greșeală, atunci „vochka” este cu siguranță un „punct” și nu un „daw”. În codurile de corectare a erorilor, cuvintele sunt alese exact astfel încât să fie „recognoscibile” chiar și după o eroare. Singura diferență este că codul „alfabet” are doar două litere - zero și una.
Redundanța unei astfel de codificări este foarte mare, iar numărul de cuvinte pe care le putem transmite astfel este relativ mic.Trebuie să excludem orice cuvânt din dicționar,care, în caz de eroare, poate coincide cu întreaga listă corespunzătoare cuvintelor transmise (de exemplu, cuvintele „fiică” și „punct” nu pot fi în dicționar). Dar transmiterea corectă a mesajelor este atât de importantă încât se depune eforturi mari pentru cercetarea codurilor rezistente la erori.
senzație
Concepte de entropie (sau incertitudine șiimprevizibilitatea) mesajului și a redundanței (sau predeterminării și predictibilității) corespund foarte firesc ideilor noastre intuitive cu privire la măsurarea informațiilor. Cu cât mesajul este mai imprevizibil (cu cât entropia este mai mare, pentru că există o probabilitate mai mică), cu atât mai multe informații sunt transmise. O senzație (de exemplu, o întâlnire cu un crocodil pe Tverskaya) este un eveniment rar, predictibilitatea sa este foarte scăzută și, prin urmare, valoarea informațiilor este ridicată. Adesea, informațiile se numesc știri - rapoarte despre evenimente care au avut loc, despre care încă nu știm nimic. Dar dacă ne vor spune despre a doua și a treia oară cu privire la aceleași cuvinte, redundanța mesajului va fi mare, imprevizibilitatea lui va scădea la zero și pur și simplu nu vom asculta, vom îndepărta de vorbitor cu cuvintele "Știu, știu". Prin urmare, mass-media încearcă atât de greu să fie primul. Această corespondență cu sentimentul intuitiv al noutății, care dă naștere unei știri cu adevărat neașteptate, a jucat un rol major în faptul că articolul lui Shannon, care nu era destinat cititorului general, a devenit o senzație pe care presa o luase ca o cheie universală a cunoașterii naturii. - de la lingviști și critici literari la biologi.
DarConceptul de informații Shannon - teoria matematică riguroasăiar aplicarea sa în afara teoriei comunicării este foarte nesigură. Dar în teoria comunicării în sine, ea joacă un rol central.
Informații semantice
Shannon, introducând conceptul de entropie ca măsurăinformația, a avut ocazia să lucreze cu informații - în primul rând, să o măsoare și să evalueze caracteristici precum capacitatea canalului sau codificarea optimă. Dar principala ipoteză care i-a permis lui Shannon să opereze cu succes cu informații a fost ipoteza că generarea de informații este un proces aleatoriu care poate fi descris cu succes în termeni de teoria probabilității.Dacă procesul nu este aleator, adică respectă legile (mai mult, nu este întotdeauna clar, așa cum se întâmplă în limba naturală), atunci raționamentul lui Shannon nu este aplicabil.Nimic din ceea ce spune Shannon nu are vreo legătură cu informațiile semnificative.
În timp ce vorbim despre personaje (sau litere ale alfabetului),putem argumenta în termeni de evenimente aleatorii, dar de îndată ce ajungem la cuvintele limbii, situația se va schimba dramatic. Discursul este un proces special organizat, iar aici structura mesajului nu este mai puțin importantă decât caracterele prin care acesta este transmis.
Recent, se părea că nu putem face nimic.făcut pentru a ajunge măcar într-un fel mai aproape de măsurarea sensului textului, dar în ultimii ani situația a început să se schimbe. Și acest lucru se datorează în primul rând aplicării rețelelor neuronale artificiale la sarcinile de traducere automată, rezumarea automată a textelor, extragerea de informații din texte și generarea de rapoarte în limbaj natural. Toate aceste sarcini implică transformarea, codificarea și decodarea informațiilor semnificative conținute în limbajul natural. Și treptat se formează o idee despre pierderile de informații în timpul unor astfel de transformări și, prin urmare, despre amploarea informațiilor semnificative. Dar astăzi, claritatea și acuratețea pe care le are teoria lui Shannon nu sunt încă disponibile în aceste probleme dificile.