Náhodný priestor udalostí
V roku 1946 americký štatistik John Tukey navrhol názov BIT
Predstavte si priestor náhodných udalostíktorá pozostáva z hádzania jednej falošnej mince, z ktorej je na oboch stranách orol. Kedy orol padne? Je jasné, že vždy. Vieme to vopred, pretože náš priestor je zariadený. Pád orla je spoľahlivá udalosť, to znamená, že jeho pravdepodobnosť je rovná 1. Dáme veľa informácií, ak povieme o vyradenom orli? Nie. Množstvo informácií v takejto správe sa bude považovať za rovné 0.
Teraz si hodíme spravodlivú mincu:na jednej strane sú to hlavy a na druhej chvosty, ako sa patrí. Pristávacie hlavy alebo chvosty budú dve rôzne udalosti, ktoré tvoria náš priestor náhodných udalostí. Ak oznámime výsledok jedného hodu, bude to skutočne nová informácia. Ak padnú hlavy, hlásime 0 a ak sú chvosty 1. Aby sme mohli nahlásiť túto informáciu, potrebujeme iba 1 bit.
čo sa zmenilo?V našom priestore podujatí sa objavila neistota. Máme o tom čo povedať niekomu, kto sám nehádže mincou a nevidí výsledok hádzania. Aby však správne pochopil našu správu, musí presne vedieť, čo robíme a čo znamenajú nuly a jedničky.Naše priestory udalostí sa musia zhodovať a proces dekódovania jedinečne obnoví výsledok hodu.Ak sa priestor udalostí vysielača a prijímača nezhoduje alebo neexistuje možnosť jednoznačného dekódovania správy, informácia zostane iba šumom v komunikačnom kanáli.
Ak hodíte dve nezávisle a súčasnemincí, potom budú štyri rôzne rovnako pravdepodobné výsledky: hlavy – hlavy, hlavy – chvosty, chvosty – hlavy a chvosty – chvosty. Na prenos informácií budeme potrebovať 2 bity a naše správy budú nasledovné: 00, 01, 10 a 11. Informácií je dvakrát toľko. Stalo sa tak preto, že neistota vzrástla. Ak sa pokúsime uhádnuť výsledok takéhoto párového hádzania, máme dvojnásobnú šancu, že sa mýlime.
Čím väčšia je neistota priestoru udalostí, tým viac informácií správa o jeho stave obsahuje.
Poďme si trochu skomplikovať náš eventový priestor.Všetky udalosti, ktoré sa stali, boli zatiaľ rovnako pravdepodobné. Ale v reálnych priestoroch nie všetky udalosti majú rovnakú pravdepodobnosť. Povedzme, že pravdepodobnosť, že vrana, ktorú vidíme, bude čierna, sa blíži k 1. Pravdepodobnosť, že prvý okoloidúci, ktorého stretneme na ulici, bude muž, je približne 0,5. Ale stretnúť krokodíla v uliciach Moskvy je takmer nemožné. Intuitívne chápeme, že správa o stretnutí s krokodílom má oveľa väčšiu informačnú hodnotu ako o čiernej vrane.Čím nižšia je pravdepodobnosť udalosti, tým viac informácií v správe o takejto udalosti.
Nechajte priestor udalostí tak exotický. Len stojíme pri okne a pozrieme sa na prechádzajúce autá. Prejdú autá štyroch farieb, ktoré musíme nahlásiť. Aby sme to mohli urobiť, zakódujeme farby: čierna - 00, biela - 01, červená - 10, modrá - 11. Aby sme presne oznámili, ktoré auto išlo, stačí preniesť 2 kúsky informácií.
Ale po dlhú dobu sledujúc autá,Všimli sme si, že farba áut je nerovnomerne rozložená: čierna - 50% (každú sekundu), biela - 25% (každá štvrtá), červená a modrá - 12,5% (každých osem). Potom môžete optimalizovať prenášané informácie.
Väčšina áut je teda čiernaoznačme čiernu - 0 - najkratší kód a kód všetkých ostatných nech začína na 1. Zo zvyšnej polovice biela - 10 a zvyšné farby začínajú na 11. Nakoniec označme červenú - 110 a modrú - 111.
Teraz, keď odovzdávame informácie o farbe auta, môžeme ho viac zakódovať.
Shannon Entropia
Nech náš eventový priestor pozostáva z nrôzne udalosti. Pri hode mincou s dvoma hlavami je taká udalosť práve jedna, pri hode jednej poctivej mince presne 2, pri hode dvoma mincami alebo sledovaní áut presne 4. Každá udalosť má pravdepodobnosť, že nastane. Pri hode mincou s dvoma hlavami nastane jedna udalosť (vypadnutie hláv) a jej pravdepodobnosť je p1 = 1. Pri hode poctivou mincou nastanú dve udalosti, sú rovnako pravdepodobné a pravdepodobnosť každej z nich je 0,5: p1 = 0,5, p2 = 0,5. Pri hode dvoch spravodlivých mincí nastanú štyri udalosti, všetky sú rovnako pravdepodobné a pravdepodobnosť každej z nich je 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Pri pozorovaní áut sú štyri udalosti a majú rôzne pravdepodobnosti: čierna - 0,5, biela - 0,25, červená - 0,125, modrá - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
To nie je náhoda.Shannon si vybral entropiu (mieru neistoty v priestore udalostí) tak, aby boli splnené tri podmienky:
- 1Entropia spoľahlivej udalosti, ktorej pravdepodobnosť je 1, sa rovná 0.
- Entropia dvoch nezávislých udalostí sa rovná súčtu entropií týchto udalostí.
- Entropia je maximálna, ak sú všetky udalosti rovnako pravdepodobné.
Všetky tieto požiadavky sú plne v súlade s našimipredstavy o neistote priestoru udalostí. Ak existuje iba jedna udalosť (prvý príklad), neexistuje žiadna neistota. Ak sú udalosti nezávislé – neistota súčtu sa rovná súčtu neistôt – jednoducho sa sčítajú (príklad hodu dvoch mincí). A nakoniec, ak sú všetky udalosti rovnako pravdepodobné, potom je stupeň neistoty systému maximálny. Rovnako ako v prípade hodu dvoch mincí sú všetky štyri udalosti rovnako pravdepodobné a entropia je 2, je väčšia ako v prípade áut, kedy sú udalosti tiež štyri, ale majú rozdielnu pravdepodobnosť - v tomto prípade je entropia 1,75.
Množstvo H hrá ústrednú úlohu v teórii informácie ako miera informácie, výberu a neistoty.
Claude Shannon
Claude Elwood Shannon- americký inžinier, kryptoanalytik amatematik. Považovaný za „otca informačného veku“. Zakladateľ teórie informácie, ktorá našla uplatnenie v moderných high-tech komunikačných systémoch. Poskytol základné pojmy, myšlienky a ich matematické formulácie, ktoré v súčasnosti tvoria základ pre moderné komunikačné technológie.
V roku 1948 navrhol použiť slovo "bit"označiť najmenšiu jednotku informácií. Taktiež preukázal, že entropia, ktorú zadal, zodpovedá neistote informácií v odovzdanej správe. Shannonove články "Matematická teória komunikácie" a "Teória komunikácie v tajných systémoch" sa považujú za základ informačnej teórie a kryptografie.
Počas druhej svetovej vojny Shannon pracoval v Bellových laboratóriách na vývoji kryptografických systémov, ktoré mu neskôr pomohli objaviť metódy kódovania na opravu chýb.
Shannon významne prispel k teórii pravdepodobnostných schém, teórie hier, teórie automatov a teórie riadiacich systémov - oblastí vedy, ktoré sú súčasťou koncepcie kybernetiky.
kódovanie
A hádzať mince, a prechádzajúce autá nie súsú podobné číslam 0 a 1. Ak chcete nahlásiť udalosti vyskytujúce sa v priestoroch, musíte si predstaviť spôsob, ako tieto udalosti opísať. Tento opis sa nazýva kódovanie.
Správy môžu byť kódované nekonečným množstvom rôznych spôsobov. Ale Shannon ukázal, že najkratší kód nemôže byť v bitoch menší ako entropia.
Preto je entropia správy mierouinformácie v správe. Keďže vo všetkých uvažovaných prípadoch je počet bitov pri kódovaní rovný entropii, znamená to, že kódovanie bolo optimálne. Správy o dianí v našich priestoroch už skrátka nie je možné kódovať.
Pri optimálnom kódovaní nemôžete stratiť respskresliť jeden prenášaný bit v správe. Ak sa stratí čo i len jeden bit, informácia bude skreslená. Všetky skutočné komunikačné kanály však neposkytujú 100-percentnú istotu, že všetky časti správy sa dostanú k príjemcovi neskreslené.
Ak chcete tento problém vyriešiť, musíte urobiťkód nie je optimálny, ale nadbytočný. Napríklad odošlite spolu so správou jej kontrolný súčet - špeciálne vypočítanú hodnotu získanú pri konverzii kódu správy, ktorú možno overiť prepočítaním po prijatí správy. Ak sa prenášaný kontrolný súčet zhoduje s vypočítaným, pravdepodobnosť, že prenos bol bezchybný, bude dosť vysoká. A ak sa kontrolný súčet nezhoduje, musíte požiadať o opakovaný prenos. Zhruba takto dnes funguje väčšina komunikačných kanálov, napríklad pri prenose paketov informácií cez internet.
Správy prirodzeného jazyka
Zvážte priestor udalostí, ktorý sa skladáz pracovných miest v prirodzenom jazyku. Toto je osobitný prípad, ale jeden z najdôležitejších. Udalosti tu budú prenášané znaky (písmená pevnej abecedy). Tieto znaky sa nachádzajú v jazyku s rôznou pravdepodobnosťou.
Symbol najfrekvenčnejšej frekvencie (t. J. Jedennajčastejšie sa nachádza vo všetkých textoch písaných v ruštine) je medzera: tisíc znakov, priemerný priestor sa nachádza 175-krát. Druhou frekvenciou je symbol "o" - 90, za ktorým nasledujú ďalšie samohlásky: "e" (alebo "e" - nebudeme ich rozlišovať) - 72, "a" - 62 a i - 62 a iba ďalšie prvá spoluhláska "t" - 53. A najvzácnejšie "f" - tento symbol sa nachádza len dvakrát na tisíc znakov.
Použijeme ruskú abecedu s 31 písmenamijazyk (nelíši sa „e“ a „e“, ako aj „ъ“ a „ь“). Ak by sa všetky písmená vyskytovali v jazyku s rovnakou pravdepodobnosťou, potom by entropia na symbol bola H = 5 bitov, ale ak vezmeme do úvahy skutočné frekvencie symbolov, entropia bude nižšia: H = 4,35 bitov. (Toto je takmer dvakrát menej ako pri tradičnom kódovaní, keď je znak prenášaný ako bajt - 8 bitov).
Ale entropia postavy v jazyku je ešte nižšia. Pravdepodobnosť výskytu ďalšieho znaku nie je úplne vopred určená priemernou frekvenciou znaku vo všetkých textoch. Ktorý znak bude nasledovať závisí od už prenesených znakov. Napríklad, v modernej ruštine potom, čo symbol "ъ" nemôže nasledovať zvuk spoluhlásky symbol. Po dvoch po sebe idúcich samohláskách "e" nasleduje tretia samohláska "e" veľmi zriedka, pokiaľ nie je v slove "long-necked". To znamená, že ďalší znak je do určitej miery vopred určený. Ak vezmeme do úvahy takúto predurčenosť ďalšieho symbolu, neistota (to znamená informácia) nasledujúceho symbolu bude ešte menšia ako 4,35. Podľa niektorých odhadov, nasledujúci symbol v ruštine je predurčený štruktúrou jazyka o viac ako 50%, to znamená, že pri optimálnom kódovaní môžu byť všetky informácie prenášané vymazaním polovice písmen zo správy.
Ďalšia vec je, že nie každý list môže byť bezpečne vymazaný. Napríklad vysokofrekvenčné „o“ (a všeobecne samohlásky) sa dajú ľahko vynechať, ale zriedkavé „f“ alebo „e“ sú dosť problematické.
Prirodzený jazyk, v ktorom spolu komunikujeme, je vysoko nadbytočný, a preto spoľahlivý, ak niečo zle započujeme, je to v poriadku, informácie sa budú stále prenášať.
Ale kým Shannon neuviedol mieru informácií, nemohli sme pochopiť, že jazyk je nadbytočný, a do akej miery môžeme komprimovať správy (a prečo sú textové súbory archívom tak komprimované).
Redundancia prirodzeného jazyka
V článku "O tom, ako vorpsimanie tektkt"(názov znie presne takto!) fragment románu Ivana Turgeneva Noble Nest bol vzatý a podrobený určitej transformácii: 34% písmen, ale nie náhodných, bolo z fragmentu vymazaných. Prvé a posledné písmená v slovách boli ponechané, iba samohlásky boli vymazané a nie všetky. Cieľom bolo nielen získať možnosť získať všetky informácie o prevedenom texte, ale aj zabezpečiť, aby osoba, ktorá čítala tento text, nezažila žiadne osobitné ťažkosti v dôsledku chýbajúcich písmen.
Prečo je relatívne ľahké prečítať toto poškodenétext? V skutočnosti obsahuje potrebné informácie na rekonštrukciu celých slov. Rodený hovorca ruštiny má určitý súbor udalostí (slová a celé vety), ktoré používa na rozpoznávanie. Okrem toho má hovorca k dispozícii aj štandardné jazykové štruktúry, ktoré mu pomáhajú obnoviť informácie. napr."Ona je blae blee"- s vysokou pravdepodobnosťou možno čítať ako"Bola citlivejšia.". Ale brané oddelene"Je viac bla", skôr bude obnovená ako„Bola belšia“. Keďže v každodennej komunikácii riešimes kanálmi, v ktorých je šum a rušenie, sme celkom dobrí v obnovovaní informácií, ale iba tých, ktoré už vopred poznáme. Napríklad fráza"Jej funkcie nie sú v najmenej príjemné, htya nmngo rspkhli a splash"číta sa dobre až na posledné slovo"Splash" - "zhromaždené". Toto slovo nie je v modernom slovníku. Pri rýchlom čítaní slova"Splls"číta sa skôr ako „prilepené“ pri pomalom, jednoducho to zneistí.
Digitalizácia signálu
Zvuk alebo akustické kmity sú sínusoidy. Môžete to vidieť napríklad na obrazovke zvukového editora. Na presné vyjadrenie zvuku budete potrebovať nekonečné množstvo hodnôt - celú sínusovú vlnu. Toto je možné pri analógovom pripojení. Spieva - počúvate, kontakt nie je prerušený, kým pieseň trvá.
V digitálnej komunikácii cez kanál môžeme prenášať iba konečný počet hodnôt. Znamená to, že zvuk nie je možné presne reprodukovať? Ukazuje sa, že nie.
Rôzne zvuky sú rôzne modulovaná sínusoida.Prenášame iba diskrétne hodnoty (frekvencie a amplitúdy) a samotná sínusová vlna sa nemusí prenášať - prijímacie zariadenie ho môže generovať.Vytvára sínusoidu a je na ňu prekrytámodulácia vytvorená z hodnôt prenášaných cez komunikačný kanál. Existujú presné princípy, ktorých diskrétne hodnoty sa musia prenášať, aby sa zvuk na vstupe do komunikačného kanála zhodoval so zvukom na výstupe, kde sú tieto hodnoty superponované na nejakej štandardnej sínusoide (to je Kotelnikovova veta o).
Kotelnikovova veta (v anglickej jazykovej literatúre - Nyquist - Shannonova veta, veta o čítaní)- zásadný výrok v oblasti digitáluspracovanie signálu, prepojenie spojitých a diskrétnych signálov a vyhlásenie, že „akákoľvek funkcia F(t), pozostávajúca z frekvencií od 0 do f1, môže byť nepretržite prenášaná s akoukoľvek presnosťou pomocou čísel nasledujúcich za sebou počas 1/(2*f1) sekundy
Kódovanie proti rušeniu. Hammingove kódy
Ak na nespoľahlivý kanál vysielaťKódovaný text Ivana Turgeneva, aj keď s niektorými chybami, bude mať za následok dosť zmysluplný text. Ak však potrebujeme všetko preniesť, úloha bude nevyriešená: nevieme, ktoré bity sú nesprávne, pretože chyba je náhodná. Dokonca aj kontrolný súčet nie je vždy uložený.
To je dôvod, prečo dnes pri prenose údajovsiete nemajú tendenciu k takému optimálnemu kódovaniu, v ktorom je možné maximálne množstvo informácií vtlačiť do kanála, ale skôr k takémuto kódovaniu (samozrejme nadbytočnému), v ktorom sa dajú chyby obnoviť - ako keď čítame slová vo fragmente Ivana Turgeneva.
Existujú špeciálne kódy na opravu chýb, ktoré umožňujú obnoviť informácie po zlyhaní. Jedným z nich je Hammingov kód.Povedzme, že celý náš jazyk pozostáva z troch slov:111000, 001110, 100011. Zdroj správy aj príjemca tieto slová poznajú. A vieme, že chyby sa vyskytujú v komunikačnom kanáli, ale pri prenose jedného slova nie je skreslený viac ako jeden bit informácie.
Predpokladajme, že najprv prejdeme slovom 111000. Výsledkom je, že nie viac ako jedna chyba (identifikovali sme chybu) sa môže premeniť na jedno zo slov:
1) 111 000,011 000, 101000, 110000, 111100, 111010, 111001,
Pri prenose slova 001110 môže byť ktorékoľvek zo slov:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111,
Nakoniec, za 100011 sa môžeme dostať na recepciu:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010,
Všetky tri zoznamy nie sú párové.pretínajú. Inými slovami, ak sa na druhom konci komunikačného kanála objaví akékoľvek slovo zo zoznamu 1, príjemca si je istý, že slovo 111000 mu bolo odoslané, a ak sa objaví nejaké slovo zo zoznamu 2, zobrazí sa slovo 001110 a zo zoznamu 3 slovo 100011. Hovorí sa, že náš kód stanovil jednu chybu.
Korekcia nastala v dôsledku dvoch faktorov.Po prvé, príjemca pozná celý „slovník“to znamená, že priestor udalostí príjemcu správy sa zhoduje s priestorom toho, kto správu odoslal. Keď bol kód odoslaný len s jednou chybou, vyšlo slovo, ktoré nebolo v slovníku.
Po druhé, slová v slovníku boli vybrané špeciálnym spôsobom.Aj keby sa vyskytla chyba, príjemca to nedokázalzamieňať jedno slovo s druhým. Napríklad, ak slovník pozostáva zo slov „dcéra“, „bodka“, „hrčka“ a počas prenosu bol výsledkom „vochka“, príjemca by s vedomím, že také slovo neexistuje, nemohol opravte chybu – ktorékoľvek z troch slov sa môže ukázať ako správne. Ak slovník obsahuje „bodku“, „daw“, „vetvu“ a vieme, že nie je povolená viac ako jedna chyba, potom „vochka“ je určite „bodka“ a nie „daw“. V kódoch na opravu chýb sa slová vyberajú presne tak, aby boli „rozpoznateľné“ aj po chybe. Jediný rozdiel je v tom, že kód „abeceda“ má iba dve písmená - nulu a jednu.
Redundancia takéhoto kódovania je veľmi veľká a počet slov, ktoré môžeme takto prenášať, je relatívne malý.Musíme vylúčiť akékoľvek slovo zo slovníka,ktorý sa v prípade chyby môže zhodovať s celým zoznamom zodpovedajúcim prenášaným slovám (napríklad slová „dcéra“ a „bodka“ nemôžu byť v slovníku). Presný prenos správ je však taký dôležitý, že sa vynakladá veľké úsilie na výskum kódov odolných voči chybám.
senzácia
Pojmy entropie (alebo neistota a. \ Tnepredvídateľnosť) správy a nadbytočnosti (alebo predurčenia a predvídateľnosti) veľmi prirodzene korešpondujú s našimi intuitívnymi predstavami o meradle informácií. Čím viac je táto správa nepredvídateľná (tým väčšia je entropia, pretože je menej pravdepodobná), tým viac informácií prenáša. Pocit (napríklad stretnutie s krokodílom na Tverskej) je zriedkavá udalosť, jej predvídateľnosť je veľmi nízka, a preto je informačná hodnota vysoká. Často sa informácie nazývajú novinky - správy o udalostiach, ku ktorým práve došlo, o ktorých stále nič nevieme. Ale ak nám povedia o druhom a treťom čase o tých istých slovách, nadbytočnosť správy bude veľká, jej nepredvídateľnosť klesne na nulu a my jednoducho nebudeme počúvať, mávať od rečníka slovami "Ja viem, ja viem." Preto sa médiá tak usilovne snažia byť prvými. Táto korešpondencia s intuitívnym zmyslom pre novosť, ktorá vedie k skutočne neočakávaným novinkám, zohrala významnú úlohu v tom, že Shannonov článok, ktorý nebol určený všeobecnému čitateľovi, sa stal senzáciou, ktorú tlačila ako univerzálny kľúč k poznaniu prírody. - od lingvistov a literárnych kritikov až po biológov.
AleShannon informačný koncept - prísna matematická teóriaa jeho aplikácia mimo komunikačnej teórie je veľmi nespoľahlivá. V samotnej teórii komunikácie však zohráva ústrednú úlohu.
Sémantické informácie
Shannon, zavádzajúc koncept entropie ako mieruinformácie, dostali možnosť pracovať s informáciami - v prvom rade ich merať a vyhodnocovať charakteristiky ako kapacita kanála alebo optimálne kódovanie. Ale hlavným predpokladom, ktorý umožnil Shannonovi úspešne operovať s informáciami, bol predpoklad, že generovanie informácií je náhodný proces, ktorý možno úspešne opísať z hľadiska teórie pravdepodobnosti.Ak je tento proces náhodný, to znamená, že dodržiava zákony (okrem toho nie je vždy jasné, ako sa to deje v prirodzenom jazyku), potom Shannonovo odôvodnenie sa naň nevzťahuje.Nič, čo Shannon hovorí, nemá nič spoločné so zmysluplnosťou informácií.
Kým hovoríme o znakoch (alebo písmenách abecedy),môžeme dobre argumentovať, pokiaľ ide o náhodné udalosti, ale akonáhle sa dostaneme k slovám jazyka, situácia sa dramaticky zmení. Reč je proces, ktorý je špeciálne organizovaný a štruktúra správy nie je o nič menej dôležitá ako postavy, ktorými sa prenáša.
Len nedávno sa zdalo, že nemôžeme nič robiť.urobil, aby sa aspoň ako-tak priblížil k meraniu zmysluplnosti textu, no v posledných rokoch sa situácia začína meniť. A to predovšetkým vďaka využívaniu umelých neurónových sietí na úlohy strojového prekladu, automatickej sumarizácie textov, extrahovania informácií z textov a generovania správ v prirodzenom jazyku. Všetky tieto úlohy zahŕňajú transformáciu, kódovanie a dekódovanie zmysluplných informácií obsiahnutých v prirodzenom jazyku. A postupne sa vytvára predstava o stratách informácií pri takýchto premenách, a teda o rozsahu zmysluplných informácií. Ale dnes jasnosť a presnosť, ktorú má Shannonova informačná teória, ešte nie je k dispozícii v týchto zložitých problémoch.