Bit, informační entropie Shannon a Hammingův kód. Jak měřit jakékoli informace a přenášet je bez ztráty

Náhodný prostor událostí

V roce 1946 navrhl americký statistický vědec John Tukey jméno BIT

(BIT, BInary digiT - “binární číslo” - “High-tech”)- Jedna z hlavních koncepcí XX století. Tukey si vybral bit pro označení jedné binární číslice, která je schopna převzít hodnotu 0 nebo 1. Ve svém článku programu „Teorie matematické komunikace“ navrhl Claude Shannon měření množství informací v bitech. To však není jediný koncept, který Shannon ve svém článku představil a prozkoumal.

Představte si prostor náhodných událostíkterý sestává z házení jedné falešné mince, na jehož obou stranách je orel. Kdy padne orel? Je jasné, že vždy. Víme to předem, protože náš prostor je uspořádán. Pád orla je spolehlivá událost, to znamená, že jeho pravděpodobnost je rovna 1. Dáme mnoho informací, pokud řekneme o orli? Ne Množství informací v takové zprávě, které budeme považovat za rovné 0.

Nyní hodíme správnou minci: na jedné straně má orla a na druhé ocasy, jak má být. Pád orla nebo ocasu budou dvě různé události, které tvoří náš prostor náhodných událostí. Pokud oznámíme výsledek jednoho hodu, budou to skutečně nové informace. Když padne orel, oznámíme 0, a když je to rozhodující 1. Abychom tyto informace sdělili, potřebujeme jen 1 bit.

Co se změnilo? V našem prostoru událostí se objevila nejistota. Máme o tom něco říct někomu, kdo minci nehodí a nevidí výsledek hodu. Aby však bylo možné správně pochopit naše poselství, musí přesně vědět, co děláme, co znamená 0 ​​a 1. Naše prostory pro události musí odpovídat a proces dekódování jedinečně obnovuje výsledek hodu. Pokud vysílací a přijímací události nemají shodnou nebo žádnou možnost jednoznačného dekódování zprávy, informace zůstane pouze v komunikačním kanálu.

Pokud nezávisle a současně házet dvatam budou čtyři různé stejně pravděpodobné výsledky: orel orel, ocasy, ocasy-hlavy a ocasy. K přenosu informací budeme potřebovat již 2 bity a naše zprávy budou následující: 00, 01, 10 a 11. Informace se staly dvakrát více. Stalo se to proto, že se zvýšila nejistota. Pokud se pokusíme odhadnout výsledek takové dvojice, pak máme dvakrát šanci udělat chybu.

Čím větší je nejistota prostoru událostí, tím více informací obsahuje zprávu o jeho stavu.

Pojďme trochu zkomplikovat prostor událostí. Všechny události, které se staly, byly stejně pravděpodobné. Ale v reálných prostorech, ne všechny události jsou stejně pravděpodobné. Například pravděpodobnost, že vrána uvidíme, bude černá, se blíží 1. Pravděpodobnost, že první kolemjdoucí na ulici bude muž, je asi 0,5. Ale je téměř neuvěřitelné potkat krokodýla na moskevské ulici. Intuitivně chápeme, že hlášení schůzky s krokodýlem má mnohem větší informační hodnotu než o černé vráně. Čím nižší je pravděpodobnost události, tím více informací ve zprávě o takové události.

Nechť prostor událostí není tak exotický. Jen stojíme u okna a podíváme se na projíždějící auta. Projíždějí se auta čtyř barev, které musíme hlásit. Abychom to dokázali, zakódujeme barvy: černá - 00, bílá - 01, červená - 10, modrá - 11. Abychom přesně informovali o tom, které auto řídilo, stačí přenést 2 kousky informací.

Ale na dlouhou dobu sleduji auta,Všimněte si, že barva auta je nerovnoměrně rozložena: černá - 50% (každou sekundu), bílá - 25% (jedno ze čtyř), červená a modrá - o 12,5% (jeden v osmi). Poté můžete optimalizovat přenášené informace.

Většina černých aut, taknechte černou - 0 - nejkratší kód, a nechte zbytek kódu začínat na 1. Zbývající polovina, bílá je 10, a zbývající barvy začínají na 11. Na závěr označujeme červenou - 110 a modrou - 111.

Nyní, když předáváme informace o barvě auta, můžeme ho více zakódovat.

Shannon Entropie

Nechť náš prostor událostí sestává z nrůzných událostí. Při házení mincí se dvěma orly je taková akce přesně jedna, při házení jedné správné mince - 2 při házení dvou mincí nebo při sledování vozů - 4. Každá událost odpovídá pravděpodobnosti jejího výskytu. Když je mince s dvěma orly hozena, událost (ztráta orla) je jedna a její pravděpodobnost je p1 = 1. Když je správná mince hozena, dvě události jsou stejně pravděpodobné a pravděpodobnost každého je 0,5: p1 = 0,5, p2 = 0,5. Když jsou hozeny dvě správné mince, existují čtyři události, všechny jsou stejně pravděpodobné a pravděpodobnost každého je 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Při pozorování automobilových událostí jsou čtyři akce a mají různé pravděpodobnosti: černá - 0,5, bílá - 0,25, červená - 0,125, modrá - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.

To není náhoda. Shannon si vybral entropii (míru nejistoty v prostoru události) tak, že byly splněny tři podmínky:

  • 1Entropie spolehlivé události, jejíž pravděpodobnost je 1, je 0.
  • Entropie dvou nezávislých událostí se rovná součtu entropií těchto událostí.
  • Entropie je maximální, pokud jsou všechny události stejně pravděpodobné.

Všechny tyto požadavky jsou plně v souladu s našimipředstavy o nejistotě prostoru událostí. Je-li událost jedna (první příklad) - neexistuje žádná nejistota. Pokud jsou události nezávislé, nejistota součtu se rovná součtu nejistot - jednoduše se sčítají (příklad hodu dvou mincí). A konečně, pokud jsou všechny události stejně pravděpodobné, pak stupeň nejistoty systému je maximální. Stejně jako v případě házení dvou mincí jsou všechny čtyři události stejně pravděpodobné a entropie je 2, je to více než v případě automobilů, když existují i ​​čtyři události, ale mají jinou pravděpodobnost - v tomto případě je entropie 1,75.

Hodnota H hraje ústřední roli v teorii informací jako měřítko kvantity informací, výběru a nejistoty.

Claude Shannon

Claude Elwood Shannon - americký inženýr, kryptoanalytik amatematik. Je považován za „otce informačního věku“. Zakladatel teorie informací, která našla uplatnění v moderních high-tech komunikačních systémech. Poskytl základní pojmy, myšlenky a jejich matematické formulace, které v současné době tvoří základ moderních komunikačních technologií.

V roce 1948 navrhl použít slovo "bit"označit nejmenší jednotku informací. On také demonstroval, že entropie zadaná jím je ekvivalentní nejistotě informací v přenášené zprávě. Shannon je články “matematická teorie komunikace” a “teorie komunikace v tajných systémech” být zvažován základní pro teorii informací a kryptografii.

Během druhé světové války, Shannon u laboratoří Bell pracoval na vývoji kryptografických systémů, později toto pomohlo jemu objevit metody kódování s opravou chyby.

Shannon významně přispěl k teorii pravděpodobnostních schémat, teorii her, teorii automatů a teorii řídících systémů - oblastech vědy, které jsou součástí konceptu kybernetiky.

Kódování

A hozené mince a projíždějící auta nejsoujsou podobné číslům 0 a 1. Chcete-li nahlásit události, ke kterým dochází v prostorech, musíte si představit způsob, jak tyto události popsat. Tento popis se nazývá kódování.

Zprávy můžete kódovat nekonečným počtem různých způsobů. Shannon ale ukázal, že nejkratší kód nemůže být menší než v entropii.

Proto je entropií poselství mírainformace ve zprávě. Protože ve všech uvažovaných případech je počet bitů v kódování roven entropii, znamená to, že kódování prošlo optimálně. Stručně řečeno, již není možné kódovat zprávy o událostech v našich prostorách.

S optimálním kódováním nemůžete ztratit nebozkreslení jednoho vysílaného bitu ve zprávě. Pokud se i jeden bit ztratí, budou informace zkresleny. Ale všechny skutečné komunikační kanály nedávají 100% jistotu, že všechny bity zprávy se dostanou k příjemci nezkreslené.

Chcete-li tento problém vyřešit, musíte provéstkód není optimální, ale nadbytečný. Například pro přenos spolu se zprávou jeho kontrolní součet - speciálně vypočtená hodnota získaná při převodu kódu zprávy a který může být zkontrolován přepočtem po přijetí zprávy. Pokud přenesený kontrolní součet odpovídá vypočtenému součtu, pravděpodobnost, že přenos proběhne bez chyb, bude poměrně vysoká. A pokud se kontrolní součet neshoduje, musíte požádat o opakovaný přenos. Tak dnes funguje většina komunikačních kanálů, například při přenosu informačních paketů přes internet.

Zprávy přirozeného jazyka

Zvažte prostor událostí, který se skládáz pracovních míst v přirozeném jazyce. To je zvláštní případ, ale jeden z nejdůležitějších. Události zde budou přenášené znaky (písmena pevné abecedy). Tyto znaky se nacházejí v jazyce s různými pravděpodobnostmi.

Nejfrekvenční symbol (tj. Jeden, kterýje nejvíce často nalezený ve všech textech psaných v ruštině) je prostor: tisíce charakterů, průměrný prostor je nalezený 175 časů. Druhá frekvence je symbol “o” - 90, následovaný jinými samohláskami: “e” (nebo “e” - my nebudeme rozlišovat je) - 72, “a” - 62, a i - 62, a jediný další \ t první souhláska "t" - 53. A nejvzácnější "f" - tento symbol se nachází pouze dvakrát na tisíc znaků.

Použijeme ruskou abecedu 31 písmenjazyk (neliší se „e“ a „e“, stejně jako „ъ“ a „ь“). Pokud by se všechna písmena vyskytovala v jazyce se stejnou pravděpodobností, pak by entropie na symbol byla H = 5 bitů, ale pokud vezmeme v úvahu skutečné frekvence symbolů, entropie bude menší: H = 4,35 bitů. (To je téměř dvakrát méně než u tradičního kódování, když je znak přenášen jako bajt - 8 bitů).

Ale entropie charakteru v jazyce je ještě nižší. Pravděpodobnost výskytu dalšího znaku není zcela předurčena průměrnou frekvencí znaku ve všech textech. Který znak bude následovat závisí na již přenesených postavách. Například v moderním ruštině po symbolu "ъ" nemůže následovat zvuk souhlásky. Po dvou následných samohláskách “e”, třetí samohláska “e” následuje extrémně zřídka, ledaže ve slově “dlouho-hrdelný”. To znamená, že další znak je do jisté míry předem určen. Pokud vezmeme v úvahu takovou předurčenost dalšího symbolu, nejistota (tj. Informace) dalšího symbolu bude ještě menší než 4,35. Podle některých odhadů, následující symbol v ruštině je předurčený strukturou jazyka více než 50%, to znamená, s optimálním kódováním, všechny informace mohou být přenášeny smazáním poloviny dopisů od zprávy.

Další věc je, že ne každý dopis lze bezpečně smazat. Vysokofrekvenční "o" (a obecně samohlásky), například, je snadno překračovat, ale vzácné "f" nebo "e" je poměrně problematické.

Přirozený jazyk, ve kterém spolu komunikujeme, je vysoce nadbytečný, a proto spolehlivý, pokud něco neslyšíme - žádná škoda, informace budou stále předávány.

Do doby, než Shannon zavedl měřítko informací, jsme nemohli pochopit, že jazyk je nadbytečný, a do jaké míry můžeme zprávy komprimovat (a proč jsou textové soubory archivátorem tak dobře komprimovány).

Redundance přirozeného jazyka

V článku "O tom, jak vorpsimanie tektkt"(název zní přesně takhle!) fragment románu Ivana Turgeneva Noble Nest byl vzat a podroben nějaké transformaci: 34% písmen, ale ne náhodných, bylo z fragmentu odstraněno. První a poslední písmena ve slovech byla ponechána, pouze samohlásky byly vymazány a ne všechny. Cílem nebylo pouze získat zpět všechny informace o převedeném textu, ale také zajistit, aby osoba, která tento text přečetla, nezažila žádné zvláštní potíže kvůli chybějícím písmenům.

Proč je poměrně snadné číst tuto zkaženoutext? Skutečně obsahuje potřebné informace k obnovení celých slov. Ruský mluvčí má určitý soubor událostí (slov a celých vět), které používá jako uznání. Dopravce má navíc standardní jazykové konstrukce, které mu pomáhají obnovit informace. Například "Ona je blae blee" - lze číst s vysokou pravděpodobností jako "Byla citlivější.". Ale samostatná fráze "Je víc bla"spíše bude obnovena jako „Byla bělejší“. Protože se jedná o každodenní komunikacis kanály, ve kterých je hluk a rušení, jsme poměrně dobře schopni obnovit informace, ale pouze takové, které již známe předem. Například fráze "Její funkce nejsou v nejmenším příjemné, htya nmngo rspkhli a splash" čitelné kromě posledního slova "Splash" - "shromáždil". Toto slovo není v moderním lexikonu. S rychlým čtením slova "Splash" čte více jako "slepený dohromady", zatímco pomalý - jen odrazy.

Digitalizace signálu

Zvuk nebo akustické kmity jsou sinusoidy. To lze vidět například na obrazovce zvukového editoru. Pro přesné vyjádření zvuku budete potřebovat nekonečný počet hodnot - celou sinusovou vlnu. To je možné s analogovým připojením. Zpívá - posloucháte, kontakt není přerušen, dokud trvá píseň.

S digitální komunikací přes kanál, můžeme přenášet pouze konečný počet hodnot. Znamená to, že zvuk nelze přesně přenášet? Ukázalo se, že ne.

Různé zvuky jsou odlišně modulované sinusoidy. Vysíláme pouze diskrétní hodnoty (frekvence a amplitudy) a samotná sinusová vlna nemusí být přenášena - přijímací zařízení jej může generovat. Generuje sinusoid a je na něm navrstven.modulace vytvořená hodnotami přenášenými přes komunikační kanál. Existují přesné principy toho, jaké diskrétní hodnoty mají být přenášeny, takže zvuk na vstupu do komunikačního kanálu se shoduje se zvukem na výstupu, kde jsou tyto hodnoty superponovány na některém standardním sinusoidu (to je právě Kotelnikovova věta).

Kotelnikovův teorém (v anglicky psané literatuře - Nyquist - Shannonova věta, věta o čtení) - základní prohlášení v oblasti digitálníhozpracování signálů, spojité spojité a diskrétní signály a uvádějící, že „jakákoli funkce F (t) sestávající z frekvencí od 0 do f1 může být nepřetržitě přenášena s jakoukoliv přesností pomocí čísel po sobě přes 1 / (2 * f1) sekund

Kódování proti rušení. Hammingovy kódy

Pokud je na nespolehlivém kanálu vysílatKódovaný text Ivana Turgeneva, i když s některými chybami, bude mít za následek poměrně smysluplný text. Pokud ale potřebujeme všechno přenést, úloha bude nevyřešena: nevíme, které bity jsou špatné, protože chyba je náhodná. Ani kontrolní součet neukládá vždy.

To je důvod, proč dnes při přenosu datsítě nemají tendenci k optimálnímu kódování, ve kterém může být do kanálu zasunuto maximální množství informací, ale spíše k takovému kódování (zjevně nadbytečnému), ve kterém mohou být chyby obnoveny - stejně jako když čteme slova ve fragmentu Ivana Turgeneva.

Existují speciální kódy oprav chyb, které umožňují obnovit informace po poruše. Jedním z nich je Hammingův kód. Předpokládejme, že náš celý jazyk se skládá ze tří slov: 111000, 001110, 100011. Tato slova znají jak zdroj zprávy, tak přijímač. A víme, že v komunikačním kanálu dochází k chybám, ale při přenosu jednoho slova je zkresleno více než jeden bit informací.

Předpokládejme, že nejprve projdeme slovo 111000. Výsledkem je, že ne více než jedna chyba (identifikovali jsme chybu) se může změnit na jedno ze slov:

1) 111 000 011 000, 101000, 110000, 111100, 111010, 111001.

Při přenosu slova 001110 lze získat libovolné slovo:

2) 001110, 101110, 011110, 000110, 001010, 001100, 001111.

Konečně za 100011 se můžeme dostat na recepci:

3) 100011, 000011, 110011, 101011, 100111, 100001, 100010.

Všimněte si, že všechny tři seznamy nejsou párové.protínají se. Jinými slovy, pokud se na druhém konci komunikačního kanálu objeví jakékoli slovo ze seznamu 1, příjemce ví, že slovo 111000 mu bylo předáno, a pokud se objeví nějaké slovo ze seznamu 2, zobrazí se slovo 001110 a ze seznamu 3 slovo 100011. Říká se, že náš kód stanovil jednu chybu.

K opravě došlo v důsledku dvou faktorů. Za prvé, příjemce zná celý „slovník“, tj. prostor událostí příjemce zprávy se shoduje s prostorem toho, kdo zprávu odeslal. Když byl kód odeslán pouze s jednou chybou, vyšlo slovo, které nebylo ve slovníku.

Zadruhé, slova ve slovníku byla vybrána zvláštním způsobem. I když došlo k chybě, příjemce nemohlzaměňte jedno slovo s druhým. Pokud se například slovník skládá ze slov „dcera“, „bod“, „bump“ a při převodu se ukázalo, že je „malý“, příjemce s vědomím, že takové slovo neexistuje, nemohl chybu opravit - kterékoli ze tří slov se může obrátit správné. Pokud slovník obsahuje „point“, „jackdaw“, „branch“ a víme, že není povolena více než jedna chyba, pak „little bit“ je samozřejmě „point“ a ne „daw“. V kódech pro korekci chyb jsou slova vybrána tak, aby byla rozpoznatelná i po chybě. Jediný rozdíl je v tom, že v kódu "abeceda" pouze dvě písmena - nula a jedna.

Redundance takového kódování je velmi velká a počet slov, která můžeme takto přenášet, je poměrně malý. Musíme vyloučit jakékoli slovo ze slovníku,které se mohou při chybě shodovat s celým seznamem odpovídajícím přenášeným slovům (například slova „dcera“ a „tečka“ nemohou být ve slovníku). Přesný přenos zprávy je však natolik důležitý, že na studium kódů odolných proti hluku jsou vynaloženy velké síly.

Vnímání

Pojmy entropie (nebo nejistota anepředvídatelnost) zprávy a redundance (nebo předurčení a předvídatelnost) velmi přirozeně odpovídají našim intuitivním představám o míře informací. Čím více je tato zpráva nepředvídatelná (tím větší je její entropie, protože je méně pravděpodobná), tím více informací přenáší. Pocit (například setkání s krokodýlem na Tverskaja) je vzácná událost, její předvídatelnost je velmi nízká, a proto je informační hodnota vysoká. Často se informace nazývají novinami - zprávami o událostech, ke kterým právě došlo, o kterých stále nic nevíme. Pokud nám však řeknou o druhém a třetím čase o stejných slovech, nadbytečnost zprávy bude velká, její nepředvídatelnost klesne na nulu a my prostě nebudeme poslouchat, mávat pryč od mluvčího se slovy "Já vím, já vím." Média se proto snaží tak těžké být první. Tato korespondence s intuitivním smyslem pro novost, která dává vzniknout neočekávaným novinkám, hrála významnou roli ve skutečnosti, že Shannonův článek, který nebyl určen pro čtenáře, se stal senzací, kterou tisk získal jako univerzální klíč k poznání přírody. - od lingvistů a literárních kritiků po biology.

Ale Shannon informační koncept - přísná matematická teoriea jeho aplikace mimo komunikační teorii je velmi nespolehlivá. Ale v teorii samotné komunikace hraje ústřední roli.

Sémantické informace

Shannon, představující pojem entropie jako měřítkoinformace, dostal možnost pracovat s informacemi - především měřit a vyhodnocovat takové charakteristiky, jako je kapacita kanálu nebo optima kódování. Hlavním předpokladem, který Shannonovi umožnil úspěšně pracovat s informacemi, byl předpoklad, že generování informací je náhodný proces, který lze úspěšně popsat z hlediska teorie pravděpodobnosti. Je-li proces ne náhodný, to znamená, že dodržuje zákony (navíc není vždy jasné, jak se to děje v přirozeném jazyce), pak se na něj Shannonova úvaha nevztahuje. Všechno, co říká Shannon, nemá nic společného s smysluplností informací.

Zatímco mluvíme o postavách (nebo písmenech abecedy),Můžeme se dobře dohadovat o náhodných událostech, ale jakmile se dostaneme ke slovům jazyka, situace se dramaticky změní. Řeč je proces, který je speciálně organizovaný, a zde je struktura zprávy neméně důležitá než postavy, kterými je přenášena.

V poslední době se zdálo, že to nemůžemeudělat něco pro přiblížení se významu textu, ale v posledních letech se situace začala měnit. A to především díky využití umělých neuronových sítí k úkolům strojového překladu, automatické sumarizaci textu, získávání informací z textů, generování zpráv v přirozeném jazyce. Ve všech těchto úkolech probíhá transformace, kódování a dekódování smysluplných informací obsažených v přirozeném jazyce. A postupně se formuje myšlenka ztráty informací v těchto transformacích, a tedy i rozsahu smysluplných informací. Ale dnes jasnost a přesnost, kterou Shannonova teorie informací má v těchto obtížných úkolech, ještě není.