Zabezpečení proti chybám

Z MiS
(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
(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, abych příjemce poznal, zda při přenosu došlo k poškození dat (chybě).
+
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&nbsp;chybě, která data a&nbsp;kontrolní posloupnost změnila tak, že odpovídají jiným datům a&nbsp;jiné platné kontrolní posloupnosti.<br />(Nikdy nemůžeme vědět na 100&nbsp;%, že jsou data v&nbsp;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
+
; CRC kódy
** Velká skupina kódů s&nbsp;podobnými vlastnostmi
+
* Velká skupina kódů s&nbsp;podobnými vlastnostmi
** Ze sítí známe CRC32, které se používá v&nbsp;protokolu Ethernet na linkové vrstvě.
+
* Ze sítí známe CRC32, které se používá v&nbsp;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.
+
; Hammingovy kódy
** CRC kódy pouze zjistí, že byla zpráva poškozena, ale opravit ji neumí.
+
* 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&nbsp;sítích je parita příliš slabým způsobem zabezpečení. Používá se ale například u&nbsp;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&nbsp;sítích je parita příliš slabým způsobem zabezpečení. Používá se ale například u&nbsp;některých typů operačních pamětí (jiné typy operačních pamětí nepoužívají kontrolní mechanizmy vůbec.
  
== Postup zabezpečení dat paritou ==
+
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 kontroly dat na straně příjemce ==
+
=== Postup zabezpečení (odesilatel) ===
 +
* Odesilatel k&nbsp;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 &rarr; lichý počet jedniček celkem, sudá parita &rarr; sudý počet jedniček celkem).
 +
 
 +
=== Postup ověření (příjemce) ===
 +
* Příjemce zkontroluje, zda je v&nbsp;přijaté posloupnosti dodrženo stanovené pravidlo.
 +
* Pokud jsou data poškozená, zahodí je a&nbsp;vyžádá si jejich zopakování.
 +
* Pokud jsou data vyhodnocena jako OK, pak příjemce odstraní kontrolní (paritní) bity a&nbsp;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&nbsp;sudém počtu bitů (2 bity, 4 bity, 6 bitů,...), pak paritní bit bude vyhovovat i&nbsp;poškozené posloupnosti a&nbsp;příjemce chybu nepozná. U&nbsp;lichého počtu bitů (1, 3, 5,...) chybu příjemce rozpozná.
 +
 +
Z&nbsp;tohoto důvodu je parita vhodná pouze tam, kde je velmi malá pravděpodobnost chyby a&nbsp;případné chyby nastávají obvykle jen v&nbsp;jednom bitu. (Například u&nbsp;čtení z&nbsp;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 &rarr; 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
  1. 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.
  2. Odesilatel k odesílaným datům připojí navíc kontrolní posloupnost bitů, vytvořenou podle smluveného pravidla.
  3. 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 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
Hammingovy kódy



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:

Postup zabezpečení (odesilatel)

Postup ověření (příjemce)

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.)


Další zdroje

Osobní nástroje
Jmenné prostory
Varianty
Akce
Výuka
Navigace
Nástroje