Korekce chyb

Alice a Bob přišli na úžasný trik. Předávají si informace brnkáním na strunu, silně nebo lehce, aby přenesli 0 nebo 1. Nicméně díky poryvu větru, se během přenosu mohou vyskytnout špatné 0 nebo 1 a vznikají chyby. Každopádně přišli nato, jak komunikovat bez chyb i za přítomnosti rušení. Jak to mohli udělat? V letech 1940 čelil Richard Hamming podobnému problému během práce v Bellových laboratořích. "V Bellových laboratořích děláme okolo 10 % experimentů na počítači a okolo 90% v laboratoři." "Očekáváme ale, že v budoucnu budeme dělat 90% na počítači a 10% v laboratoři." "Rychlost, cena a úsilí zvýhodňuje počítač před laboratorním přístupem." Tehdy počítače používaly děrné štítky k uchovávání informací. 1 reprezentovala dírku, 0 byla reprezentováná bez dírky. Systém byl náchylný k chybám, protože bylo běžné, že štítky se ohýbaly nebo docházelo ke špatnému vyražení dírky. Dírky tehdy mohly být minuty nebo mohly být omylem vyraženy, což znamenalo převrácení bitů. Tyto chyby mohly znamenat zastavení systému, dokud se chyby nenajdou a neopraví ručně. Hamming to vzal do svých rukou a vymyslel metodu, která automaticky detekuje a opravuje jedno-bitové chyby bez přerušení výpočtů. Jeho řešení bylo založeno na intuitivní myšlence opakování, které děláme vždy, když čelíme rušení nebo možnosti, že naše zpráva bude poškozená. Jeho oprava chyb byla vytvořena na jednoduchém konceptu paritního bitu. Paritní bit je jeden bit, který je přidán na konec zpráv, a indikuje, jestli je počet jedniček ve zprávě sudý nebo lichý. Pokud se vyskytne jedna chyba, příjemce ji může detekovat, protože paritní bit se nebude shodovat. Nicméně pro detekci a opravu jednotlivých chyb, Hamming potřeboval přidat více paritních bitů k identifikaci pozice chyby. To vedlo k jeho (7,4) kódu, který přidává 3 paritní bity do každého bloku 4 datových bitů následovně: Začněme 3 paritními bity. Ty mohou být znázorněny jako kruh. Tyto kruhy se protínají ve 4 oblastech. A 4 datové bity jsou umístěny uvnitř těchto oblastí ve specifickém pořadí. Pro výpočet paritních bitů se podíváme do každého kruhu postupně, každý obsahuje 3 data bity (z celkových 4). Paritní bit zjistíme tak jako předtím, sečteme datové bity a pokud dostaneme 0 nebo 2 paritní bit je 0 pro sudé. A pokud dostaneme 1 nebo 3, parita bude 1 pro líché. Toto děláme pro všechny kruhy a skončíme se 3 paritními bity pro kontrolu 4 datových bitů. Ty jsou pak umístěny ve standardním pořadí jak je znázorněno. Všimněme si, že tento systém může automaticky opravit jednotlivé chyby pomocí jednoduchého pravidla. Pokud chyba nastane, 2 a více paritních bitů bude nesprávných. Tam kde se protínají, je poloha chyby. Protínající datový bit je převrácen, takže všechny paritní bity jsou opět správné. A toto je trik Alice a Boba. Další paritní bity jsou známé jako redudantní bity. Protože nejsou použity pro přenos nových informací. Všechny opravné kódy fungují tímto způsobem. Zvětšují velikost zdrojové zpávy, na úkor automatické korekce chyb. Chybové opravné kódy používáme také pro úložiště. Například u fyzického CD jsou informace kódovány speciálním kódem pro opravu úseků kódu, které jsou poškozeny škrábanci nebo nečistotou. To poškozuje větší pořadí 0 a 1 uložených na povrchu. Právě z tohoto důvodu je možné přehrát i škrábnuté CD. Claude Shannon použil tuto myšlenku redudance pro změnu definice kapacity komunikačního kanálu. Se zvyšujícím se rušení v kanálu musíme zvýšit redudanci, abychom mohli komunikovat bez chyb. To však zmenší množství informací, které je možné poslat v jednotce času.