Prostor slučajnog događaja
Godine 1946. američki statističar John Tukey predložio je naziv BIT
Zamislite prostor slučajnih događajakoji se sastoji od bacanja jednog lažnog novčića, s obje strane orao. Kada padne orao? Jasno je da uvijek. To znamo unaprijed, jer je naš prostor tako uređen. Pad orla je pouzdani događaj, tj. Njegova je vjerojatnost jednaka 1. Hoćemo li dati mnogo informacija ako kažemo o ispuštenom orlu? Ne. Količina informacija u takvoj poruci smatrat ćemo se jednakom 0.
Sada bacimo pošteni novčić:s jedne strane su glave, a s druge repovi, kako i dolikuje. Slijetanje glave ili repa bit će dva različita događaja koji čine naš prostor slučajnih događaja. Ako izvijestimo o ishodu jednog bacanja, to će doista biti nova informacija. Ako su glave pale, prijavit ćemo 0, a ako su repovi 1. Da bismo prijavili ovu informaciju, potreban nam je samo 1 bit.
Što se promijenilo?Neizvjesnost se pojavila u našem događanju. O tome imamo što reći nekome tko sam ne baca novčić i ne vidi ishod bacanja. Ali da bi pravilno razumio našu poruku, on mora točno znati što radimo i što znače 0 i 1.Naši prostori događaja moraju se podudarati, a proces dekodiranja jedinstveno služi za vraćanje rezultata bacanja.Ako se događajni prostor odašiljača i prijamnika ne poklapa ili ne postoji mogućnost jednoznačnog dekodiranja poruke, informacija će ostati samo šum u komunikacijskom kanalu.
Ako bacite dva neovisno i istovremenonovčića, onda će postojati četiri različita jednako vjerojatna rezultata: heads-heads, heads-tails, tails-heads i tails-tails. Za prijenos informacija trebat će nam 2 bita, a naše poruke će biti sljedeće: 00, 01, 10 i 11. Informacija je dvostruko više. To se dogodilo jer je neizvjesnost porasla. Ako pokušamo pogoditi ishod takvog bacanja parova, imamo dvostruko veće šanse da pogriješimo.
Što je neizvjesnost prostora događaja veća, poruka o svom stanju sadrži više informacija.
Idemo malo zakomplicirati naš event prostor.Do sada su svi događaji koji su se dogodili bili jednako vjerojatni. Ali u stvarnim prostorima nemaju svi događaji jednaku vjerojatnost. Recimo da je vjerojatnost da će vrana koju vidimo biti crna blizu 1. Vjerojatnost da će prvi prolaznik kojeg sretnemo na ulici biti muškarac je otprilike 0,5. Ali sresti krokodila na ulicama Moskve gotovo je nemoguće. Intuitivno shvaćamo da izvještaj o susretu s krokodilom ima mnogo veću informacijsku vrijednost nego o crnoj vrani.Što je manja vjerojatnost događaja, više informacija u poruci o takvom događaju.
Neka prostor događaja ne bude tako egzotičan. Samo stojimo na prozoru i gledamo prolazne automobile. Automobili četiriju boja prolaze, što moramo prijaviti. Da bismo to učinili, kodirat ćemo boje: crna - 00, bijela - 01, crvena - 10, plava - 11. Da bismo točno izvijestili koji je automobil vozio, samo trebamo prenijeti 2 bita informacija.
Ali dugo vremena gledajući automobile,napominjemo da je boja automobila neravnomjerno raspoređena: crna - 50% (svaka sekunda), bijela - 25% (svaka četvrta), crvena i plava - 12,5% (svaka osma). Tada možete optimizirati prenesene informacije.
Većina auta je crna, dakleoznačimo crno - 0 - najkraći kod, a kod svih ostalih neka počinje s 1. Od preostale polovice, bijele - 10, a ostale boje počinju s 11. Na kraju, označimo crvenu - 110, a plavu - 111.
Sada, prenoseći informacije o boji automobila, možemo ga bolje kodirati.
Shannon Entropy
Neka se naš prostor događaja sastoji od nrazličite događaje. Kod bacanja novčića s dvije glave postoji točno jedan takav događaj, kod bacanja jednog poštenog novčića točno 2, pri bacanju dva novčića ili promatranja automobila točno 4. Svaki događaj ima vjerojatnost da će se dogoditi. Kod bacanja novčića s dvije glave postoji jedan događaj (ispadanje glava) i njegova je vjerojatnost p1 = 1. Kod bacanja poštenog novčića postoje dva događaja, jednako su vjerojatni i vjerojatnost svakog je 0,5: p1 = 0,5, p2 = 0,5. Kod bacanja dva poštena novčića postoje četiri događaja, svi su jednako vjerojatni i vjerojatnost svakog je 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Kod promatranja automobila postoje četiri događaja, a imaju različite vjerojatnosti: crni - 0,5, bijeli - 0,25, crveni - 0,125, plavi - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Ovo nije slučajnost.Shannon je odabrala entropiju (mjeru nesigurnosti u prostoru događaja) tako da su ispunjena tri uvjeta:
- 1 Entropija pouzdanog događaja čija je vjerojatnost 1 jednaka je 0.
- Entropija dvaju neovisnih događaja jednaka je zbroju entropija tih događaja.
- Entropija je maksimalna ako su svi događaji jednako vjerojatni.
Svi ovi zahtjevi u potpunosti su u skladu s našimideje o neizvjesnosti prostora događanja. Ako postoji samo jedan događaj (prvi primjer), nema neizvjesnosti. Ako su događaji neovisni - nesigurnost zbroja jednaka je zbroju neizvjesnosti - jednostavno se zbrajaju (primjer bacanja dva novčića). I konačno, ako su svi događaji jednako vjerojatni, tada je stupanj nesigurnosti sustava maksimalan. Kako su u slučaju bacanja dva novčića sva četiri događaja jednako vjerojatna i entropija je 2, veća je nego u slučaju automobila, kada također postoje četiri događaja, ali imaju različite vjerojatnosti - u ovom slučaju entropija je 1.75.
Veličina H igra središnju ulogu u informacijskoj teoriji kao mjera informacije, izbora i neizvjesnosti.
Claude Shannon
Claude Elwood Shannon- američki inženjer, kriptoanalitičar imatematičar. Smatra se "ocem informacijskog doba". Utemeljitelj je informacijske teorije koja je našla primjenu u suvremenim visokotehnološkim komunikacijskim sustavima. Pruža temeljne koncepte, ideje i njihove matematičke formulacije koje trenutno čine osnovu za moderne komunikacijske tehnologije.
Godine 1948. predložio je korištenje riječi "bit"za označavanje najmanje jedinice podataka. Također je pokazao da je entropija koju je unio jednak nesigurnosti informacija u prenesenoj poruci. Shannonovi članci "Matematička teorija komunikacije" i "Teorija komunikacije u tajnim sustavima" smatraju se temeljnim za teoriju informacija i kriptografiju.
Tijekom Drugog svjetskog rata, Shannon je radio u Bell Laboratories na razvoju kriptografskih sustava, koji su mu kasnije pomogli otkriti metode kodiranja s ispravljanjem pogrešaka.
Shannon je dao ključni doprinos teoriji probabilističkih shema, teoriji igara, teoriji automata i teoriji upravljačkih sustava - područjima znanosti koja su dio koncepta kibernetike.
šifriranje
I bačene kovanice, a prolazni automobili nisuslični su brojevima 0 i 1. Da biste prijavili događaje koji se događaju u prostorima, trebate smisliti način opisivanja tih događaja. Ovaj se opis naziva kodiranje.
Poruke se mogu kodirati na beskonačan broj različitih načina. Ali Shannon je pokazao da najkraći kod ne može biti manji u bitovima od entropije.
Zato je entropija poruke mjerainformacije u poruci. Budući da je u svim razmatranim slučajevima broj bitova tijekom kodiranja jednak entropiji, to znači da je kodiranje bilo optimalno. Ukratko, više nije moguće kodirati poruke o događanjima u našim prostorima.
S optimalnim kodiranjem ne možete izgubiti iliiskriviti jedan preneseni bit u poruci. Ako se čak i jedan bit izgubi, informacija će biti iskrivljena. Ali svi stvarni komunikacijski kanali ne pružaju 100 postotno povjerenje da će svi dijelovi poruke stići do primatelja neiskrivljeni.
Da biste riješili ovaj problem morate učinitikod nije optimalan, nego suvišan. Na primjer, zajedno s porukom prenesite njen kontrolni zbroj - posebno izračunatu vrijednost dobivenu prilikom pretvorbe koda poruke, a koja se može provjeriti ponovnim izračunavanjem po primitku poruke. Ako se preneseni kontrolni zbroj podudara s izračunatim, vjerojatnost da je prijenos bio bez grešaka bit će prilično velika. A ako kontrolni zbroj ne odgovara, mora se zatražiti ponovni prijenos. Otprilike tako danas funkcionira većina komunikacijskih kanala, primjerice, prilikom prijenosa paketa informacija putem interneta.
Poruke prirodnog jezika
Razmotrite prostor događaja koji se sastojiiz postova na prirodnom jeziku. Ovo je poseban slučaj, ali jedan od najvažnijih. Događaji će biti preneseni znakovi (slova fiksne abecede). Ovi znakovi nalaze se u jeziku s različitim vjerojatnostima.
Simbol najviše frekvencije (tj. Jedan od njihnajčešće se nalazi u svim tekstovima pisanim na ruskom) je prostor: od tisuću znakova, prosječan prostor se nalazi 175 puta. Drugi po učestalosti je simbol "o" - 90, iza kojeg slijede drugi samoglasnici: "e" (ili "e" - nećemo ih razlikovati) - 72, "a" - 62, i i - 62, i samo dalje prvi suglasnik "t" - 53. A najrjeđi "f" - ovaj simbol se nalazi samo dvaput na tisuću znakova.
Koristit ćemo 31 slovo ruske abecedejezik (ne razlikuje se "e" i "e", kao i "ʺ" i "ü"). Ako se sva slova nađu u jeziku s istom vjerojatnošću, entropija po simbolu bi bila H = 5 bitova, ali ako uzmemo u obzir stvarne frekvencije simbola, entropija će biti manja: H = 4,35 bita. (To je gotovo dva puta manje nego kod tradicionalnog kodiranja, kada se znak prenosi kao bajt - 8 bita).
Ali entropija lika u jeziku još je niža. Vjerojatnost pojavljivanja sljedećeg znaka nije u potpunosti predodređena prosječnom frekvencijom znaka u svim tekstovima. Koji će znak slijediti ovisi o već prenesenim znakovima. Na primjer, u suvremenom ruskom, nakon što simbol "ʺ" ne može slijediti zvuk simbola suglasnika. Nakon dva uzastopna samoglasnika "e", treći samoglasnik "e" slijedi iznimno rijetko, osim u riječi "dugi vrat". To jest, sljedeći znak je donekle predodređen. Ako uzmemo u obzir takvu predodređenost sljedećeg simbola, nesigurnost (tj. Informacija) sljedećeg simbola bit će čak i manja od 4,35. Prema nekim procjenama, sljedeći simbol na ruskom jeziku je unaprijed određen strukturom jezika za više od 50%, to jest, uz optimalno kodiranje, sve se informacije mogu prenijeti brisanjem polovice slova iz poruke.
Druga stvar je da se svako slovo ne može sigurno izbrisati. Visoke frekvencije "o" (i općenito vokali), na primjer, lako se prekriže, ali rijetko "f" ili "e" je prilično problematično.
Prirodni jezik kojim međusobno komuniciramo vrlo je redundantan, a samim time i pouzdan; ako smo nešto pogrešno čuli, u redu je, informacija će se ipak prenijeti.
Ali sve dok Shannon nije predstavio mjeru informacija, nismo mogli shvatiti da je jezik suvišan, iu kojoj mjeri možemo komprimirati poruke (i zašto tekstualne datoteke tako dobro komprimiraju arhivatori).
Redundantnost prirodnog jezika
U članku "O tome kako vorpsimanie tektkt"(ime zvuči točno ovako!) snimljen je fragment romana Ivana Turgenjeva Noble Nest i podvrgnut je nekoj transformaciji: iz fragmenta je izbrisano 34% slova, ali ne slučajnih. Ostala su prva i posljednja slova u riječima, izbrisani su samo samoglasnici, a ne svi. Cilj nije bio samo dobiti priliku da se oporave sve informacije o prevedenom tekstu, već i da se osigura da osoba koja čita ovaj tekst nije iskusila nikakve posebne poteškoće zbog nedostajućih slova.
Zašto je relativno lako čitati ovo iskvarenotekst? Zapravo sadrži potrebne informacije za rekonstrukciju cijelih riječi. Izvorni govornik ruskog jezika ima određeni skup događaja (riječi i cijele rečenice) koje koristi za prepoznavanje. Osim toga, govornik ima na raspolaganju i standardne jezične strukture koje mu pomažu u obnavljanju informacija. Na primjer,"Ona je blae blee- s velikom vjerojatnošću može se čitati kao"Bila je osjetljivija.". Ali odvojeno"Ona je više bla", radije, bit će obnovljen kao"Bila je bjelja". Budući da se u svakodnevnoj komunikaciji bavimos kanalima u kojima ima šuma i smetnji, vrlo smo dobri u vraćanju informacija, ali samo onih koje već unaprijed znamo. Na primjer, izraz"Njezine značajke nisu nimalo ugodne, htya nmngo rspkhli i splash"dobro se čita osim zadnje riječi"Splash" - "okupljeni". Ova riječ nije u modernom leksikonu. Pri brzom čitanju riječi"Splls"čita se više kao "zalijepljeni zajedno"; kada je spor, jednostavno zbunjuje.
Digitalizacija signala
Zvuk, ili akustične oscilacije, je sinusoid. To se može vidjeti, primjerice, na zaslonu uređivača zvuka. Da biste točno prenijeli zvuk, trebat će vam beskonačan broj vrijednosti - cijeli sinusni val. To je moguće uz analognu vezu. On pjeva - slušajte, kontakt se ne prekida dok pjesma traje.
U digitalnoj komunikaciji putem kanala možemo prenijeti samo konačan broj vrijednosti. Znači li to da se zvuk ne može točno reproducirati? Ispostavilo se da nije.
Različiti zvukovi su različito modulirani sinusni val.Mi prenosimo samo diskretne vrijednosti (frekvencije i amplitude), a sam sinusni val ne treba prenositi - uređaj koji ga prima može ga generirati.Generira sinusoidu i superponira se na njumodulacija stvorena od vrijednosti prenesenih putem komunikacijskog kanala. Postoje točni principi koje se diskretne vrijednosti moraju prenijeti tako da se zvuk na ulazu u komunikacijski kanal podudara sa zvukom na izlazu, gdje se te vrijednosti superponiraju na neku standardnu sinusoidu (to je Kotelnikovljev teorem oko).
Kotelnikov teorem (u literaturi na engleskom jeziku - Nyquist-Shannonov teorem, teorem o čitanju)- temeljna izjava u području digitalnogobrada signala, povezujući kontinuirane i diskretne signale i navodeći da se „bilo koja funkcija F(t), koja se sastoji od frekvencija od 0 do f1, može kontinuirano prenositi s bilo kojom točnošću koristeći brojeve koji slijede jedan za drugim kroz 1/(2*f1) sekunde
Kodiranje protiv smetnji. Hammingovi kodovi
Ako je na nepouzdanom kanalu za prijenosŠifrirani tekst Ivana Turgenjeva, iako s nekim pogreškama, rezultirat će vrlo smislenim tekstom. Ali, ako moramo sve prenijeti na malo, zadatak će biti neriješen: ne znamo koji su bitovi pogrešni, jer je pogreška slučajna. Čak ni kontrolni zbroj ne štedi uvijek.
To je razlog zašto danas kod prijenosa podatakamreže nisu toliko usmjerene na optimalno kodiranje, u kojem se maksimalna količina informacija može gurnuti u kanal, nego na takvo kodiranje (očigledno suvišno) u kojem se pogreške mogu oporaviti - baš kao kad čitamo riječi u fragmentu Ivana Turgenjeva.
Postoje posebni kodovi za ispravljanje pogrešaka koji omogućuju vraćanje informacija nakon kvara. Jedan od njih je Hammingov kod.Recimo da se cijeli naš jezik sastoji od tri riječi:111000, 001110, 100011. I izvor poruke i primatelj znaju ove riječi. I znamo da se pogreške događaju u komunikacijskom kanalu, ali pri prijenosu jedne riječi ne iskrivljuje se više od jednog bita informacije.
Pretpostavimo da prvo prođemo riječ 111000. Kao rezultat toga, ne više od jedne pogreške (identificirali smo pogrešku) ona se može pretvoriti u jednu od riječi:
1) 111000,011,000, 101000, 110000, 111100, 111010, 111001,
Pri prijenosu riječi 001110 može se dobiti bilo koja od riječi:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111,
Konačno, za 100011 možemo doći na recepciju:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010,
Imajte na umu da sva tri popisa nisu parna.sijeku. Drugim riječima, ako se na drugom kraju komunikacijskog kanala pojavi bilo koja riječ s popisa 1, primatelj sigurno zna da mu je prenesena riječ 111000, a ako se pojavi bilo koja riječ s popisa 2, pojavljuje se riječ 001110 i s popisa 3, riječ 100011. Kažu da je naš kod popravio jednu pogrešku.
Do korekcije je došlo zbog dva faktora.Prvo, primatelj zna cijeli "rječnik"prostor događaja događaja primatelja poruke podudara se s prostorom osobe koja je poslala poruku. Kada je kôd prenio samo s jednom pogreškom, izašla je riječ koja nije bila u rječniku.
Drugo, riječi u rječniku odabrane su na poseban način.Čak i ako je došlo do pogreške, primatelj nije mogaobrkati jednu riječ s drugom. Na primjer, ako se rječnik sastoji od riječi "kći", "točka", "kvrga", a tijekom prijenosa je rezultat bio "vočka", tada primatelj, znajući da takva riječ ne postoji, ne bi mogao ispravi pogrešku - bilo koja od tri riječi može se pokazati točnom. Ako u rječniku ima “točka”, “čarka”, “grana” i znamo da nije dopuštena više od jedne pogreške, onda je “vočka” definitivno “točka”, a ne “čarka”. U kodovima za ispravljanje pogrešaka, riječi su odabrane upravo tako da budu "prepoznatljive" čak i nakon pogreške. Jedina razlika je u tome što šifra "abeceda" ima samo dva slova - nula i jedan.
Redundantnost takvog kodiranja je vrlo velika, a broj riječi koje možemo prenijeti relativno je mali.Moramo isključiti bilo koju riječ iz rječnika,koji se u slučaju pogreške može podudarati s cijelim popisom koji odgovara prenesenim riječima (na primjer, riječi "kći" i "točka" ne mogu biti u rječniku). Ali točan prijenos poruka toliko je važan da se veliki napor ulaže u istraživanje kodova otpornih na pogreške.
senzacija
Pojmovi entropije (ili nesigurnosti i. \ Tnepredvidivost) poruke i redundancije (ili predodređenosti i predvidljivosti) vrlo prirodno odgovaraju našim intuitivnim idejama o mjeri informacija. Što je poruka nepredvidljivija (što je veća entropija, jer postoji manja vjerojatnost), to više informacija nosi. Osjećaj (na primjer, susret s krokodilom na Tverskoj) je rijedak događaj, njegova predvidljivost je vrlo niska i stoga je informacijska vrijednost visoka. Često se informacije nazivaju vijestima - izvještaji o događajima koji su se upravo dogodili, o kojima još uvijek ništa ne znamo. Ali ako nam kažu o drugom i trećem puta o istim riječima, suvišnost poruke će biti velika, njezina nepredvidljivost će pasti na nulu, i mi jednostavno nećemo slušati, mašući se od govornika riječima: "Znam, znam". Stoga se mediji toliko trude biti prvi. Ta podudarnost s intuitivnim osjećajem za novost, koja dovodi do zaista neočekivanih vijesti, odigrala je važnu ulogu u činjenici da je Shannonin članak, koji nije bio namijenjen općem čitatelju, postao senzacija, koju je novina pokupila kao univerzalni ključ znanja o prirodi. - od lingvista i književnih kritičara do biologa.
AliShannonov informacijski koncept - stroga matematička teorijai njegova primjena izvan teorije komunikacije vrlo je nepouzdana. Ali u samoj teoriji komunikacije ona igra središnju ulogu.
Semantičke informacije
Shannon, uvodeći koncept entropije kao mjereinformacije, dobili priliku raditi s informacijama - prije svega, mjeriti ih i evaluirati karakteristike poput kapaciteta kanala ili optimalnog kodiranja. Ali glavna pretpostavka koja je omogućila Shannonu da uspješno operira s informacijama bila je pretpostavka da je generiranje informacija slučajan proces koji se može uspješno opisati u terminima teorije vjerojatnosti.Ako je proces ne-slučajan, to jest, poštuje zakone (štoviše, nije uvijek jasno, kao što se događa u prirodnom jeziku), tada Shannonovo razmišljanje nije primjenjivo na njega.Ništa što Shannon kaže nema nikakve veze s time da je informacija smislena.
Dok govorimo o znakovima (ili slovima abecede),možemo raspravljati u smislu slučajnih događaja, ali čim stignemo do riječi jezika, situacija će se dramatično promijeniti. Govor je proces koji je posebno organiziran, a ovdje struktura poruke nije ništa manje važna od znakova kojima se prenosi.
Nedavno se činilo da ne možemo ništa učiniti.učinjeno kako bi se barem nekako približilo mjerenju smislenosti teksta, no posljednjih godina situacija se počela mijenjati. I to prije svega zbog primjene umjetnih neuronskih mreža na zadatke strojnog prevođenja, automatskog sažimanja tekstova, izvlačenja informacija iz tekstova i generiranja izvješća na prirodnom jeziku. Svi ovi zadaci uključuju transformaciju, kodiranje i dekodiranje smislenih informacija sadržanih u prirodnom jeziku. Postupno se stvara ideja o gubicima informacija tijekom takvih transformacija, a time i o opsegu smislenih informacija. Ali danas, jasnoća i točnost koju ima Shannonova teorija informacija još nije dostupna u ovim teškim problemima.