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

== Přenos dat informačním kanálem == 
[[Komunikační kanál|Informační kanál]] představuje prostředek ([[Marshall McLuhan|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 [[Komunikační šum|š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|modelů]] a schémat přenosu informace. Tím nejznámějším ve světě [[Informační věda|informační vědy]] je tzv. '''[[Shannon a weaver model|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ódování|kódu]] - 0 nebo 1''' (bit byl navržen pro jednotku informace, aby bylo možné hodnotit kapacitu přenosu).

[[Soubor:Mathematical information model.png|600px|bezrámu|střed]]
<br />

* '''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 v pojetí informační vědy|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é [[Komunikace|komunikační]] kanály nebo při [[Skupinová a masová komunikace |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'''.<ref>[https://www.khanacademy.org/computing/computer-science/informationtheory/moderninfotheory/v/testtest Cruise, Brit, “Error correction” (video)]</ref>

== Komunikační chyby a jejich řešení ==
Během přenosu informací mezi částmi [[Osobní počítač|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í (tzv. redundace) 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ě. 
<br />
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.<ref>[https://popelka.ms.mff.cuni.cz/~lessner/mw/index.php/U%C4%8Debnice/Informace/K%C3%B3dov%C3%A1n%C3%AD_a_redundance Učebnice MFF.cuni, Kódování a redundace] </ref>

=== 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é [[EAN|čá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ší. 

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é.
<br /> 
<br />
'''Příklad:'''
<br />
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'''.<ref>[http://home.zcu.cz/~kaisert/kody/kody.pdf home.zcu, Samoopravné kódy]</ref>

== 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 – jednotky informace|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 [[Hardware|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'''.<ref>[https://cs.wikipedia.org/w/index.php?title=BCH_k%C3%B3d&oldid=16333637 WIkipedie: Otevřená encyklopedie, BCH kód]</ref>

=== 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 [[Logika|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.<ref>[http://www.person.vsb.cz/archivcd/FEI/PD/Prenos%20dat.pdf Marek Dvorský, Pavel Nevlud. ''Přenos dat'']</ref>


== 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

=== Reference ===

<references />

=== 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.
 
[[Kategorie:Informační studia a knihovnictví]]
[[Kategorie: Státnicové otázky UISK]]