Gregor odcestoval do Kolumbie objavovať dažďové pralesy a veľmi si chce písať s Viki. Nemá však mobil, a tak posiela správy cez staré telegrafné vedenie ako postupnosti núl a jednotiek (bitov). V pralese však často zúria búrky a blesky občas spôsobia, že sa niektorý bit cestou otočí (z 0 na 1 alebo naopak).

Gregor s Viki sa preto dohodli, ako si budú posielať správy, aby ak sa aj náhodou stane nejaká chyba, tak pokiaľ sa tých chýb nestane príliš veľa, Viki bude aj z takto chybnej správy vedieť rozlúštiť, čo jej chcel pôvodne Gregor poslať. Gregor posiela správy po blokoch – teda úsekoch nejakej dopredu dohodnutej dĺžky. Keď chce Gregor poslať jeden blok, zoberie bity tohto bloku (ktoré nazveme dátové bity) a pridá k nim ešte nejaké ďalšie bity (ktoré nazveme kontrolné bity). Kontrolné bity sa môžu pridať na koniec správy, alebo aj niekde medzi dátové bity, ak treba. Takto dostane dlhší blok, ktorý pošle Viki, a ona sa z toho pokúsi dostať späť pôvodnú správu.

Úvodný príklad: Zdvojenie správy

Ako si Gregor vyberie kontrolné bity? Ukážeme si jednu možnosť: Povedzme, že chce poslať 4 dátové bity: 1011. Zakóduje ich tak, že celú štvoricu pošle dvakrát za sebou, teda odošle 8 bitov: 10111011. Cestou však do vedenia udrie blesk a Viki prijme správu: 10111001. Viki porovná prvú polovicu (1011) s druhou polovicou (1001). Vidí, že na 3. pozícii sa líšia, takže vie, že pôvodná štvorica mala tvar 10?1. Netuší však, čo je namiesto otáznika, lebo tá chyba sa mohla stať buď v prvej polovici (a správa mala byť 1001), alebo v druhej polovici (a správa mala byť 1011). Viki teda vie zistiť, že nastala chyba, no nemá ako vedieť, ako ju opraviť.

Tento príklad síce funguje, ale potrebujeme naň veľa bitov naviac a vieme iba zistiť, že nastala chyba. Nevedeli by sme to spraviť aj s oveľa menej kontrolnými bitmi? A ako by sme ich museli vymyslieť, aby sme tú chybu vedeli dokonca aj opraviť?

Úloha 1: Odhalenie chyby

Gregor chce poslať blok 7 dátových bitov a pridá k nemu iba 1 kontrolný bit (spolu odošle 8 bitov). Predpokladajme, že blesk zmení najviac 1 bit v celej odoslanej správe (môže to byť dátový bit, kontrolný bit, alebo sa nepokazí žiaden).

Navrhni pravidlo, ktorým Gregor určí hodnotu tohto kontrolného bitu. Popíš postup, ako Viki po prijatí správy spoľahlivo zistí, či nastala chyba.

Úloha 2: Mriežka $3 \times 3$

Gregor má 9 dátových bitov a usporiada si ich do štvorcovej tabuľky $3 \times 3$. K týmto 9 dátovým bitom pridá 6 kontrolných bitov (napríklad kontrolu pre každý riadok a každý stĺpec), takže celkovo odošle 15 bitov.

Ako má Gregor týchto 6 kontrolných bitov vytvoriť? Popíš, ako Viki pomocou nich zistí, či nastala chyba, na ktorej presnej pozícii v mriežke sa nachádza a ako ju opraví (za predpokladu, že v celej 15-bitovej správe nastala najviac 1 chyba).

Úloha 3: Presnejšie určovanie

V úlohe 2 sme na opravu 9 dátových bitov potrebovali až 6 kontrolných bitov. Dá sa to však spraviť omnoho úspornejšie, ak budeme podozrivé miesta postupne poliť. Kontrolné bity si môžeš v odosielanom bloku umiestniť na ľubovoľné pozície, ktoré ti vyhovujú.

• a V ktorej polovici? Predpokladajme, že vieme naisto, že v odoslanej 8-bitovej správe nastala práve jedna chyba. Navrhni, ako skombinovať 7 dátových bitov a 1 kontrolný bit (spolu 8 bitov) tak, aby Viki vedela jednoznačne určiť, v ktorej polovici (v prvých 4 bitoch alebo v druhých 4 bitoch) táto chyba nastala.

• b V ktorej štvrtine? Stále predpokladáme, že nastala práve 1 chyba. Navrhni, ako skombinovať 6 dátových bitov a 2 kontrolné bity (spolu 8 bitov) tak, aby Viki vedela presne určiť, v ktorej štvrtine (v ktorej dvojici bitov) sa chyba nachádza.

• c Presná pozícia Stále predpokladáme, že nastala práve 1 chyba. Navrhni, ako skombinovať 5 dátových bitov a 3 kontrolné bity (spolu 8 bitov) tak, aby Viki vedela určiť presné číslo pozície poškodeného bitu a opraviť ho.

• d Oprava bez podmienok V praxi vopred nevieme, či búrka správu poškodila alebo prišla celá bez chyby (môže nastať 0 alebo 1 chyba). Navrhni, ako zakódovať 4 dátové bity pomocou 3 kontrolných bitov do výslednej 7-bitovej správy tak, aby Viki vedela zistiť, či správa prišla v poriadku, a v prípade 1 chyby ju vedela presne nájsť a opraviť.