Samoopravné kódy a limity přenosu zpráv informačním kanálem

Přenos dat informačním kanálem

Informační kanál představuje prostředek (médium) nebo souhrn prostředků, prostřednictvím kterých jsou přenášena data (informace, zpráva). Objem neboli míra informace vyjadřuje množství informace obsažené ve zprávě. Jednoduše řečeno jde o přenos dat z jednoho místa na druhé přičemž během cesty informačním kanálem na data působí šumy, které mohou data poškodit a změnit, což má za následek chybnou informaci v konečném bodě. Naším cílem je přenést data bez chyb a nebo nakonec chybu identifikovat a nejlépe opravit do původní podoby. V historii teorie informace, bylo vytvořeno mnoho modelů a schémat přenosu informace. Tím nejznámějším je ve světě informační vědy tzv. Shannon-Weaver model of communication. V tomto modelu nezáleží na tom co zpráva vyjadřuje (text, zvuk, obraz, video...). Vše může být převedeno do binárního kódu - 0 nebo 1 (bit byl navržen pro jednotku informace aby bylo možné hodnotit kapacitu přenosu).

• Noise Source - informační šum, označení pro jakékoliv zkreslení (deformaci) informace
• Channel capacity - Kapacita kanálu je maximální množství dat, které je možno přenést za určitou časovou jednotku. (rovnice: Kapacita kanálu = Informace + šum)
• Entropy - Entropie je míra neuspořádanosti / neurčitosti. Míra nejistoty v jakém stavu zpráva dorazí.

Kanálové kódování (FEC)

V telekomunikaci, teorii informace a teorii kódů je Forward Error Correction (FEC) neboli kanálové kódování, technika užívaná ke kontrole chyb při přenosu dat skrze komunikační kanály, na nichž dochází k šumu a tudíž ztrátě informací. Hlavní ideou je, že odesílatel informaci kóduje nadbytečně pomocí samoopravného kódu. Nadbytečnost informací (resp. její dostatek) umožní příjemci detekovat a limitovat množství chyb, jež se mohou objevit kdykoliv a kdekoliv během přenosu informací a často také opravit tyto chyby bez nutnosti přeposílání. FEC dává příjemci možnost opravit chyby bez nutnosti užití zpětného kanálu pro přeposlání dat. FEC je tedy aplikováno v situacích, kde je přeposílání drahé nebo nemožné, tak jako jednosměrné komunikační kanály nebo při skupinové komunikaci. Jedná se například o vesmírné satelity, kde by přeposílání v případě vzniklých chyb, vytvořilo několikahodinové zpoždění. FEC je obvykle přidáváno do zařízení s velkým uložištěm, které umožňuje obnovení poškozených dat. Je často užíváno v modemech a serverech.

Komunikační chyby a jejich řešení

Behem přenosu informací mezi částmi počítače, ze Země na Měsíc nebo pouze při jednoduchém ukládání dat je riziko, že přenesená data nebudou odpovídat původní odeslané informaci. Pro tento případ, bylo vyvinuto mnoho kódovacích metod, díky kterým je možné chyby zjistit a dokonce někdy i opravit. Mezi tyto metody patří paritní bity, samodetekující nebo samoopravné kódy.

Paritní bity

Jde o jednoduchou metodu detekce chyb. Jeho podstata tkví v tom, že pokud má každý zpracovávaný bitový vzor lichý počet jedniček a objeví se vzor se sudým počtem jedniček pak muselo dojít k chybě. Aby tato metoda fungovala, je nutné docílit toho, aby měly všechny bitové vzory lichý počet jedniček. Jednoduše toho dosáhneme tak, že ke každému existujícímu vzoru v systému kódování přidáme tzv. paritní bit navíc. Paritnímu bitu přiradíme hodnotu 1 nebo 0 tak, aby výsledná posloupnost měla lichý počet jedniček.

Samodetekující kódy

Slouží k rychlému rozpoznání chyb v zadaných datech. Metoda je založena na principu dělitelnosti výsledných dat jedním určitým číslem (nejčastěji je to číslo 11 (tzv. jedenáctkový samodetekující kód). Dělitel musí splňovat dvě pravidla, musí být dvojciferný a musí být prvočíslem aby metoda bezpečně fungovala. Tuto metodu využívají kódy ISBN, ISSN, čísla bankovních účtů, platební karty či některé čárové kódy. Narozdíl od samoopravných kódů mají samodetekující kódy velký nedostatek, nejsou schopné získat původní informaci, pouze zjistí, že nastala během přenosu chyba.

Samoopravné kódy

Samooprvané kódy (error-correcting code) dokáží chyby nejen najít, ale i opravit a získat zpět původní podobu dat. Velmi důležitou roli zde hraje R. W. Hamming, který ve 40. letech začal hledat kódy na opravu chyb. Abychom byli schopni chybu opravit je nutné definovat Hammingovu vzdálenost. Hammingova vzdálenost mezi dvěma bitovými vzory je dána počtem bitů, v nichž se vzory liší. Příklad samoopravného kódu.

Samoopravné kódy jsou velice užitečné pokud potřebujeme poslat určitá data po telekomunikační lince, která není příliš spolehlivá, takže při přenosu pravděpodobně vlivem šumu dojde k řadě chyb. Pro nás je však důležité zajistit, aby příjemce obdržel data bez chyb, a za tím účelem jsme ochotni poslat i něco navíc, pokud to pomůže případné chyby eliminovat. Přenos je však drahý, a tak samozřejmě chceme, aby celkový objem posílaných dat byl co nejmenší. Data, která odesíláme jsou tvořena posloupností n bitů (0 a 1). Při přenosu může u libovolného bitu dojít k chybě (tj. přijatý bit se liší od odeslaného). Pravděpodobnost chyby je u každého bitu (p). Chyby jsou navzájem nezávislé.
Příklad:
Dejme tomu pro n = 100 a p = 0.01 je pravděpodobnost bezchybného příjmu slabých 37%. Jak ji zvýšit? Nejjednodušší způsob je poslat každý bit víckrát (řekněme třikrát) a při příjmu pro něj zvolit tzv. většinovou hodnotu (tedy tu, která v přijaté trojici převládá). Jinak řečeno, bit 0 při odesílání kódujeme jako posloupnost 000 a bit 1 jako posloupnost 111. Při příjmu pak trojice dekódujeme podle pravidel:

• 000, 001, 010, 100 → 0,
• 111, 110, 101, 011 → 1.

Tímto jsme pravděpodobnost bezchybného příjmu zvýšili na 97%. Jednotlivý bit se správně dekóduje právě tehdy, když při přenosu příslušné trojice nastane nejvýše jedna chyba. Cenu, kterou za to platíme, je trojnásobný objem posílaných dat.

Samoopravné kódy

Hammingův kód

jde o lineární binární perfektní kód, který má nejmenší redundanci. Tzn., že má nejnižší počet zabezpečovacích prvků pro opravu jedné chyby. Nevýhodou je, že nedokáže opravit více chyb.

Roku 1940 čelil Richard Hamming v Bell Telephone Laboratories problému s chybami během přenosu informací. V té době se počítačové informace uchovávaly na děrných štítcích, reprezentující 1 a 0 pomocí děr. Tento systém byl náchylný k chybám, protože bylo běžné, že byla díra vyražena tam, kde neměla nebo nebyla vyražena vůbec. Tyto chyby způsobovaly otočení bitů. To způsobovalo, že byl celý systém zastaven, dokud se chybu nepodařilo manuálně nalézt. Hamming přišel s metodou detekování a opravy jednotlivých bitů, aniž by přerušil výpočet. Jeho samoopravné kódy byly založeny na konceptu párového bitu. Párový bit je bit, který je přidán na konec zprávy, aby indikoval zda je počet 1 ve správě lichý nebo sudý. Pokud se objeví byť jen jediná chyba, příjemce jej bude moci detekovat, protože párový bit nebude souhlasit. Nicméně k detekci a opravě chyb potřeboval Hamming přidat více párových bitů, aby identifikoval polohu chyby. To vedlo k jeho kódu 7,4, který přidává 3 párové bity ke každému 4 bitovému bloku. Zaprvé začneme s třemi párovými bity, které mohou být reprezentovány jako kruh. Tyto kruhy se protínají tak, že vytváření čtyři oblasti. 4bitové bloky jsou umístěny uvnitř těchto kruhů ve specifickém pořadí.

BCH kód

V teorii kódování tvoří BCH kódy skupinu cyklických samoopravných kódů, které jsou konstruovány pomocí konečných těles. BCH kódy byly vynalezeny v roce 1959 Hocquenghemem, a nezávisle v roce 1960 Bosem a Ray-Chaudhurim. Zkratka BCH je tvořena počátečními jmény těchto objevitelů. Klíčovou vlastností BCH kódů je možnost v průběhu návrhu kódu přesně kontrolovat počet opravitelných chyb ve výsledném kódu. Další výhodou BCH kódů je jednoduchost jejich dekódování pomocí algebraických metod známých jako syndrome decoding. To zjednodušuje návrh dekodérů s použitím malého výkonnostně slabého hardwaru. BCH kódy jsou používány například v satelitní komunikaci, CD a DVD přehrávačích, pevných discích, flash discích a QR kódech.

Reed-Muller kódy

Reed-Muller kódy jsou z rodiny lineární Hchybě-opravných kódů používané v komunikaci. Jsoupojmenované podle svých objevitelů, Irving S. Reed a DE Muller. Muller objevil kódy a Reed navrhl většinu logiky dekódování poprvé. Reed-Muller kódy jsou uvedeny jako RM (n,k), kde n – počet všech prvků a k – počet informačních prvků. RM je schopen opravit vícenásobné chyby.

Informační kanál a jeho limity

Při přenosu informací může dojít k omezení související s technickými prostředky (např. poruchovost) nebo k deformaci sdělení v průběhu toku komunikačním kanálem (viz. komunikační šum). Této problematice se podrobněji věnují články Informační a komunikačních bariéry a Komunikační kanál.

Odkazy

Použitá literatura

• OLŠÁK, Petr. Úvod do algebry, zejména lineární. 2., přeprac. vyd. V Praze: České vysoké učení technické, 2013. 189 s. ISBN

978-80-01-05291-4

• THOMPSON, Thomas M. From error-correcting codes through sphere packings to simple groups. [Washington]: Mathematical Association of America, ©1983. xiv, 228 s. The carus mathematical monographs; no. 21. ISBN 0-88385-023-0.
• SHANNON, Claude Elwood a Weaver, Warren. The mathematical theory of communication. Urbana: University of Illinois Press, ©1998. ix, 125 s. ISBN 0-252-72548-4.
• KRATOCHVÍL, T. The DVB Television Signal Transmission Simulation Using the Forward Error Correction Codes. Conference proceedings ICECom 2003. ICECom 2003. Dubrovnik (Chorvatsko): 2003, s. 113 - 116, ISBN 953-6037-39-4.
• LUYI, Sui, Fu JINYI a Yang XIAOHUA, Forward Error Correction. 2012. DOI: 10.1109/ICCIS.2012.158. ISBN 978-1-4673-2406-9. Dostupné také z: http://ieeexplore.ieee.org/document/6300016/
• NAFAA, A., T. TALEB a L. MURPHY, Forward error correction strategies for media streaming over wireless networks. 2012. DOI: 10.1109/MCOM.2008.4427233. ISBN 0163-6804. Dostupné také z: http://ieeexplore.ieee.org/document/4427233/

Související články

• Shannonovo chápání informace
• Kódování
• Bit – jednotky informace

Klíčová slova

kódování, Hamming, bit