Zabezpečení proti chybám
Obsah |
Cíle a omezení kontroly chyb
- Cíl
Cílem je upravit odesílaná data tak, aby příjemce poznal, zda při přenosu došlo k poškození dat (chybě).
- Princip kontroly dat
- Příjemce a odesilatel musí předem vědět, jaký kontrolní mechanizmus budou používat!
- Buď je to stanoveno protokolem, nebo se dohodnou předem.
- Odesilatel k odesílaným datům připojí navíc kontrolní posloupnost bitů, vytvořenou podle smluveného pravidla.
- Příjemce zkontroluje, jestli kontrolní posloupnost odpovídá datům.
- Pokud kontrolní posloupnost odpovídá datům, příjemce považuje data za správná.
- Pokud kontrolní posloupnost neodpovídá přijatým datovým bitům, došlo k chybě při přenosu.
- Můžeme najít všechny chyby?
- Žádný kontrolní mechanizmus nemůže odhalit všechny chyby!
- Pokud jsme našli chybu, máme jistotu, že chyba nastala a data jsou poškozená.
- Pokud kontrolní posloupnost odpovídá, pak buď:
- Jsou data v pořádku,
- nebo došlo k chybě, která data a kontrolní posloupnost změnila tak, že odpovídají jiným datům a jiné platné kontrolní posloupnosti.
(Nikdy nemůžeme vědět na 100 %, že jsou data v pořádku. Můžeme jen minimalizovat pravděpodobnost chyby, která se nepozná.)
Můžeme si představit, že náhodné poškození dat vnějšími vlivy způsobí stejnou změnu zprávy, jako by zprávu zničil útočník a příjemci záměrně odeslal jinou zprávu se stejným způsobem zabezpečení. U dobrých způsobů zabezpečení je sice velmi málo pravděpodobné, že by taková situace nastala, ale vyloučená není. Takovou chybu žádný mechanizmus kontroly neodhalí.
Běžně používané kódy pro zajištění proti chybám
- CRC kódy
- Velká skupina kódů s podobnými vlastnostmi
- Ze sítí známe CRC32, které se používá v protokolu Ethernet na linkové vrstvě.
- Hammingovy kódy
- Na rozdíl od CRC kódů umí při malém poškození zprávy dokonce zprávu opravit.
- CRC kódy pouze zjistí, že byla zpráva poškozena, ale opravit ji neumí.
Parita
Parita je nejjedndušší CRC kód (CRC1). Její výhodou je, že se snadno počítá a můžeme si na ní tedy ukázat principy hledání chyb.
Pro praktické použití v sítích je parita příliš slabým způsobem zabezpečení. Používá se ale například u některých typů operačních pamětí (jiné typy operačních pamětí nepoužívají kontrolní mechanizmy vůbec.
Při použití parity vždy doplníme ke stanovenému počtu datových bitů jeden bit paritní.
Existují dvě varianty:
- lichá parita: doplníme paritní bit tak, aby celkový počet jedniček ve vzniklé posloupnosti byl lichý
- sudá parita: doplníme paritní bit tak, aby celkový počet jedniček ve vzniklé posloupnosti byl sudý
Postup zabezpečení (odesilatel)
- Odesilatel k datům připojí kontrolní bity (například ke každým 7 datovým bitům jeden kontrolní/paritní).
- Každý blok musí splňovat stanovené pravidlo (lichá parita → lichý počet jedniček celkem, sudá parita → sudý počet jedniček celkem).
Postup ověření (příjemce)
- Příjemce zkontroluje, zda je v přijaté posloupnosti dodrženo stanovené pravidlo.
- Pokud jsou data poškozená, zahodí je a vyžádá si jejich zopakování.
- Pokud jsou data vyhodnocena jako OK, pak příjemce odstraní kontrolní (paritní) bity a předá data vyšší vrstvě.
- Příklad
Chceme předat data: 1101001
Příjemce i odesilatel se dohodli předem, že použijí lichou paritu:
Odesilatel odešle: 11010011
Příjemce obdrží posloupnost: 11010011
Příjemce zkontroluje zda paritní bit odpovídá pravidlu:
celkový počet 1 musí být lichý
=> Vyhodnotí přenos jako OK!
Odstraní paritní bit: 1101001
Příklady
Příklad 1:
Odesilatel chce odeslat data: 1001010
S příjemcem se dohodli na použití liché parity.
Jak budou vypadat odeslaná data?
Odpověď: 10010100
Příklad 2:
Odesilatel chce odeslat data: 0011110110010001
S příjemcem se dohodli na použití liché parity tak, že paritní bit vždy předchází každých 8 datových bitů.
Jak budou vypadat odeslaná data?
Odpověď: 000111101010010001
Příklad 3:
Příjemce obdržel posloupnost bitů:
101001111
Ví, že odesilatel používá sudou paritu a paritní bit je vždy před osmicí datových bitů. Jsou data v pořádku? Jak vypadají data?
Odpovědi: ano, data vyhodnotíme jako OK
(POZOR! Není to 100 % garance, že jsou data správná. Ale tu nemám nikdy.)
Data: 01001111
Příklad 4:
Příjemce obdržel posloupnost bitů zabezpečenou lichou paritou, paritní bit následuje po 7 datových bitech. Jsou data v pořádku? Jak vypadají data?
Přijatá posloupnost: 101101110111011101111111
Odpověď:
101101110111011101111111 xxxxxxxxxxxxxxxx0111111
Kdy parita selhává?
Pokud nastane chyba v sudém počtu bitů (2 bity, 4 bity, 6 bitů,...), pak paritní bit bude vyhovovat i poškozené posloupnosti a příjemce chybu nepozná. U lichého počtu bitů (1, 3, 5,...) chybu příjemce rozpozná.
Z tohoto důvodu je parita vhodná pouze tam, kde je velmi malá pravděpodobnost chyby a případné chyby nastávají obvykle jen v jednom bitu. (Například u čtení z operační paměti, kde by mohla být poškozena jedna paměťová buňka.)
