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). Objem neboli míra informace vyjadřuje množství dat obsažených 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 působí na data šumy, které mohou data poškodit a změnit. To může mít za následek ve výsledku chybnou informaci. Naším cílem je přenést data bez chyb. Pokud bezchybný přenos není možný, je potřeba dokázat chybu identifikovat a nejlépe ihned 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 ve světě informační vědy je 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, v 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í

Během 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.

Metoda kontrolního součtu

Metoda při které se přikláníme k neúsporné cestě a za cenu nadbytku informací zvyšujeme šanci zjištění vzniklých chyb během přenosu zprávy. Pokud připojíme součet zprávy (např. již uvedený paritní bit) na konec zprávy. Součet zprávy by měl být stejný po příjmu jako před odesláním. Pokud se součty liší, došlo pravděpodobně při přenosu k chybě.
Kontrolní součet můžeme použít i pro kontrolu výsledků v matematice. Ciferace je výsledek opakovaného počítání ciferného součtu čísla, dokud nezůstane jediná cifra. Ciferace tzv. zachovává běžné operace. To znamená, že např. ciferace rozdílu dvou čísel je rovna rozdílu ciferací těch čísel, neboli C(a-b) = C(a)-C(b). Pro kontrolu spočteme a porovnáme příslušné ciferace a se značnou pravděpodobností odhalíme numerickou chybu. Např. spočteme, že 92-48=54. Následně spočteme ciferace, C(92)=C(11)=2, C(48)=C(12)=3, C(54)=9. Ovšem 2-3 není 9, takže je někde chyba.

Příklady samoopravných kódů

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 na tom 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í chybě-opravných kódů používané v komunikaci. Jsou pojmenované 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 informační šum).

Shannonův limit

Každý komunikační kanál má své kapacitní omezení měřené v binárním kódu. Je matematicky nemožné provést bezchybný (bez ztráty dat) přenos dat nad hranicí limitu. Naopak pokud je přenos kapacitně pod hranicí limitu, tak je možný přenos dat s nulovou chybou.

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/
• Marek Dvorský, Pavel Nevlud. Přenos dat: učební text [online]. Ostrava: VŠB – Technická univerzita Ostrava, 2012 [cit. 2021-01-28]. str. 114, ISBN 978-80-248-2604-2. Dostupné z: http://www.person.vsb.cz/archivcd/FEI/PD/Prenos%20dat.pdf
• J. Glenn Brookshear. Informatika. Dotisk 1. vydání. Brno: Computer Press, 2013. ISBN 978-80-251-3805-2

Související články

• Shannonovo chápání informace
• Kódování
• Bit – jednotky informace
• Komunikační kanál
• Entropie v pojetí informační vědy
• Informace
• Shannon a weaver model
• Teorie informace
• Lasswellův model
• David Berlo
• Informační a komunikačních bariéry
• Komunikační šum
• Charakterizujte výhody a omezení Shannon-Weaverova modelu z pohledu sociální komunikace
• Claude Shannon

Klíčová slova

kódování, Hamming, bit, Hammingův kód, Shannon-Weaver model, informační kanál, komunikační kanál, samoopravné kódy, samodetekční kódy, komnukační šum, přenos informace, přenos dat, Shannonův limit, kapacita kanálu, limity kanálu, BCH kódy.