Zabezpečení proti chybám
(Vytvoření kostry stránky) |
(Doplnění, kdy parita selhává.) |
||
| (Nejsou zobrazeny 2 mezilehlé verze od 1 uživatele.) | |||
| Řádka 4: | Řádka 4: | ||
; Cíl | ; Cíl | ||
| − | Cílem je upravit odesílaná data tak, | + | 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? | ; Můžeme najít všechny chyby? | ||
| − | Žádný kontrolní mechanizmus nemůže odhalit 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.<br />(Nikdy nemůžeme vědět na 100 %, že jsou data v pořádku. Můžeme jen minimalizovat pravděpodobnost chyby, která se nepozná.) | ||
<div class="Poznamka"> | <div class="Poznamka"> | ||
| Řádka 15: | Řádka 27: | ||
== Běžně používané kódy pro zajištění proti chybám == | == 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 == | ||
| Řádka 28: | Řádka 44: | ||
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. | 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 | + | === 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ě. | ||
| + | |||
| + | <div class="Priklad"> | ||
| + | ; Příklad: | ||
| + | |||
| + | Chceme předat data: <code>1101001</code> | ||
| + | |||
| + | Příjemce i odesilatel se dohodli předem, že použijí lichou paritu: | ||
| + | Odesilatel odešle: <code>11010011</code> | ||
| + | |||
| + | Příjemce obdrží posloupnost: <code>11010011</code> | ||
| + | |||
| + | 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: <code>1101001</code> | ||
| + | </div> | ||
| + | |||
| + | |||
| + | == Příklady == | ||
| + | |||
| + | === Příklad 1: === | ||
| + | Odesilatel chce odeslat data: <code>1001010</code> | ||
| + | S příjemcem se dohodli na použití liché parity. | ||
| + | Jak budou vypadat odeslaná data? | ||
| + | |||
| + | Odpověď: <code>10010100</code> | ||
| + | |||
| + | === Příklad 2: === | ||
| + | Odesilatel chce odeslat data: <code>0011110110010001</code> | ||
| + | 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ěď: <code>000111101010010001</code> | ||
| + | |||
| + | === 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: <code>01001111</code> | ||
| + | |||
| + | === 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: <code>101101110111011101111111</code> | ||
| + | |||
| + | Odpověď: | ||
| + | 101101110111011101111111 | ||
| + | xxxxxxxxxxxxxxxx0111111 | ||
== Kdy parita selhává? == | == 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.) | ||
| + | |||
| + | |||
| + | == Další zdroje == | ||
| + | * [http://cs.wikipedia.org/wiki/Paritn%C3%AD_bit Wikipedia.org → Paritní bit] | ||
Aktuální verze z 10. 1. 2022, 21:45
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.)
