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

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ánv 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.[1]

Hammingův kód

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.[2]

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

Reference

  1. Cruise, Brit, “Error correction” (video). Khan Academy. Accessed August 24, 2018. https://www.khanacademy.org/computing/computer-science/informationtheory/moderninfotheory/v/testtest
  2. Wikipedie: Otevřená encyklopedie: BCH kód [online]. c2018 [citováno 26. 08. 2018]. Dostupný z WWW:<https://cs.wikipedia.org/w/index.php?title=BCH_k%C3%B3d&oldid=16333637>

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

Klíčová slova

kódování, Hamming, bit