| Název školy: | Vyšší odborná škola a Střední průmyslová škola, Božetěchova 3 |
| Autor: | Ing. Marek Nožka |
| Anotace: | Detekce a korekce chyb -- kanálové kódování |
| Vzdělávací oblast: | Informační a komunikační technologie |
| Předmět: | Počítačové sítě a komunikační technika (PSK) |
| Tematická oblast: | Vrstvy protokolu TCP/IP |
| Výsledky vzdělávání: | Žák objasňuje princip detekce a korekce chyb |
| Klíčová slova: | otisk, hash, detekce a korekce chyb |
| Druh učebního materiálu: | Online vzdělávací materiál |
| Typ vzdělávání: | Střední vzdělávání, 3. ročník, technické lyceum |
| Ověřeno: | VOŠ a SPŠE Olomouc; Třída: 3L |
| Zdroj: | Vlastní poznámky, Wikipedia, Wikimedia Commons |
Pojem kanálové kódování je odvozen z toho, že toto kódování přizpůsobuje zprávu pro daný přenosový kanál. Jeho úkolem je zabezpečit data proti cybám. K~přenášeným datům se přidají další data, která zprávu zabezpečují. Zvětšuje se tedy redundance.
Při přenosu dat jakoukoli přenosovou trasou dochází vždy k chybám. Ty je nutné detekovat nebo opravit.
Chybovost je podíl špatně a správně přenesených bitů:
$\Rightarrow$ volba zabezpečovacího kódu
Detekční kódy slouží k detekci chyb. Pokud je chyba detekována, přijímací strana chybu pouze detekuje (a musí si od vysílací strany vyžádat opakování zprávy).
Paritní kód je nejjednodušším detekčním kódem. Značka má $(n-1)$ míst informačních a jedno místo zabezpečující. K přenášeným datům doplníme vždy jeden bit tak, aby počet jedniček byl sudý (sudá parita) nebo lichý (lichá parita).
Poslední bit je vždy paritní.
10011011 1
00110111 1
01101001 0
00011000 0
Chybu nelze detekovat pokud \tecky{5} % dojde k dvěma chýbám najednou
Kódy K z N mají $n$-místné značky a v~každé je právě $k$~jedniček. Kontrola spočívá ve spočítání jedniček. U těchto kódů nelze oddělit data a zabezpečení.
| Platná data | Chybná data |
|---|---|
| 0 0 1 1 | 0 0 0 0 |
| 0 1 0 1 | 0 0 0 1 |
| 0 1 1 0 | 0 0 1 0 |
| 1 0 0 1 | 0 1 0 0 |
| 1 0 1 0 | 0 1 1 1 |
| 1 1 0 0 | 1 0 0 0 |
| 1 0 1 1 | |
| 1 1 0 1 | |
| 1 1 1 0 | |
| 1 1 1 1 |
Hašovací funkce nebo jen Hash je reprodukovatelná (opakovatelná) metoda pro převod vstupních dat do (relativně) malého čísla, které vytváří jejich otisk -- můžeme ho označit jako charakteristiku dat.
Výsledný otisk se označuje také jako výtah, miniatura, fingerprint či hash. Funkce může sloužit ke kontrole integrity (neporušenosti) dat, k rychlému porovnání dvojice zpráv, indexování, vyhledávání apod. Je důležitou součástí kryptografických systémů pro elektronický podpis.
Jestliže mají dvě zprávy stejný hash je velká pravděpodobnost, že se shodují.
Nejznámější hashovací funkce jsou MD5, CRC nebo SHA.
Hašovací algoritmy jsou bezpečné pokud je velmi obtížné (tj. se současnými prostředky prakticky nemožné):
Například následující zpráva:...
Alenko!
Oběd máš v lednici. Vrátím se až večer.
Máma`--> stáhnout
... má tento MD5 otisk:
b99ed1417ff6469b94a605b9c789c161
a tento SHA1 otisk:
834bfc7d8ced0c10963dd8ef9123020bd441f450
Pokud změním zprávu, změní se i otisky. Všimněte si, že různě dlouhé zprávy mají vždy stejně dlouhé otisky.
Alenko!
Oběd máš v lednici. Vrátím se až večer.
--
Ahoj
Tvoje Máma
`--> stáhnout
MD5:
b35d7d1cc5874b6440f1eb0cca312314
SHA1:
7badc8f34d34ef422b833071dc7529595d958e19
Některé přenosové linky vykazují tak velkou chybovost, že bychom si s pouhým detekčním kódem nevystačili. Pravděpodobnost výskytu chyby je tak velká, že téměř nepřeneseme jedinou značku bez chyby. Proto se používají kódy, které umí chybu nejen detekovat, ale do určitého množství chyb i opravit.
Na obrázku je schematické znázornění detekce a opravy chyb. Tečky představují množinu možných stavů. Černé tečky stavy povolené jsou , šedé tečky jsou stavy zakázané -- tedy chyby. U některých chybových stavů lze určit, který platný stav je mu nejblíže. U některých to ale nelze, a je možné pouze konstatovat, že došlo k chybě.