{"id":369,"date":"2020-04-06T08:28:09","date_gmt":"2020-04-06T06:28:09","guid":{"rendered":"http:\/\/tech.sosthe.sk\/?p=369"},"modified":"2020-04-06T16:58:55","modified_gmt":"2020-04-06T14:58:55","slug":"5-2-odhalovanie-chyb","status":"publish","type":"post","link":"http:\/\/tech.sosthe.sk\/index.php\/2020\/04\/06\/5-2-odhalovanie-chyb\/","title":{"rendered":"5.2.\u2002Odha\u013eovanie ch\u00fdb"},"content":{"rendered":"

Odha\u013eovanie ch\u00fdb sl\u00fa\u017ei na to, aby si pr\u00edjemca bol primerane ist\u00fd t\u00fdm, \u017ee dostal presne tie ist\u00e9 d\u00e1ta, ktor\u00e9 boli odoslan\u00e9 odosielate\u013eom. Za chybu sa typicky pova\u017euje v\u00fdmena nejak\u00fdch bitov na opa\u010dn\u00e9. Chyby s\u00fa sp\u00f4sobovan\u00e9 r\u00f4znymi vplyvmi extern\u00e9ho prostredia na fyzick\u00fd spoj.<\/p>\n

Kontrola je umo\u017enen\u00e1 tak, \u017ee sa k odosielan\u00fdm d\u00e1tam pribalia \u010fal\u0161ie tzv. kontroln\u00e9 bity. Chyba m\u00f4\u017ee nasta\u0165 v p\u00f4vodn\u00fdch d\u00e1tach, ale aj v kontroln\u00fdch bitoch. Odhalenie v\u0161etk\u00fdch druhov ch\u00fdb nie je vo v\u0161eobecnosti stopercentn\u00e9. \u010c\u00edm viac je kontroln\u00fdch bitov, t\u00fdm je v\u00e4\u010d\u0161ia \u0161anca na odhalenie pr\u00edpadnej chyby. Samozrejme z\u00e1vis\u00ed aj na sp\u00f4sobe, ak\u00fdm sa samotn\u00e1 kontrola realizuje. Uk\u00e1\u017eeme si tri sp\u00f4soby kontroly ch\u00fdb: kontrola parity, kontroln\u00fd s\u00fa\u010det a CRC.<\/p>\n

5.2.1\u2002 Kontrola parity<\/h3>\n

Kontrola parity je najjednoduch\u0161ie realizovate\u013en\u00e1 kontrola d\u00e1t. Pri z\u00e1kladnej kontrole parity prid\u00e1vame k d\u00e1tam iba jeden kontroln\u00fd bit, tzv.\u00a0paritn\u00fd bit<\/strong>. Jeho hodnotu ur\u010d\u00edme tak, \u017ee spo\u010d\u00edtame po\u010det jednotiek v bin\u00e1rnej reprezent\u00e1cii d\u00e1t. Ak je tento po\u010det p\u00e1rny, paritn\u00fd bit m\u00e1 hodnotu nula a ak je nep\u00e1rny, tak paritn\u00fd bit m\u00e1 hodnotu jedna. Ak sa v takto odoslan\u00fdch d\u00e1tach zmen\u00ed nep\u00e1rny po\u010det bitov, tak pr\u00edjemca odhal\u00ed chybu. \u00daspe\u0161nos\u0165 tejto met\u00f3dy je teda 50 %.<\/p>\n

\u0160peci\u00e1lny sp\u00f4sob kontroly parity je\u00a0blokov\u00e1 kontrola parity<\/strong>. Pri tomto sp\u00f4sobe rozdel\u00edme d\u00e1ta na\u00a0m<\/em>\u00a0blokov po\u00a0n<\/em>\u00a0bitoch. Najprv vypo\u010d\u00edtame paritu ka\u017ed\u00e9ho bloku a paritn\u00fd bit zap\u00ed\u0161eme na koniec bloku ako (n<\/em>\u00a0+ 1)-v\u00fd bit bloku. Nakoniec vypo\u010d\u00edtame parity\u00a0i<\/em>-t\u00fdch bitov zo v\u0161etk\u00fdch blokov pre\u00a0i<\/em>\u00a0z intervalu <1,n+1>. Z\u00edskame tak\u00a0n<\/em>+m<\/em>+1 paritn\u00fdch inform\u00e1ci\u00ed, ktor\u00e9 sa pribalia k p\u00f4vodn\u00fdm d\u00e1tam ako kontroln\u00e9 bity. Ak sa pri prenose vyskytne chyba iba v jednom bite, pr\u00edjemca je schopn\u00fd t\u00fato chybu\u00a0opravi\u0165<\/strong>, preto\u017ee je schopn\u00fd identifikova\u0165 presn\u00e9 miesto, kde chyba nastala. Ak vie pr\u00edjemca chybu opravi\u0165, nie je potrebn\u00e9 \u017eiada\u0165 o op\u00e4tovn\u00e9 zaslanie d\u00e1t. Ak sa vyskytne viac ch\u00fdb, tak oprava pri tomto sp\u00f4sobe u\u017e mo\u017en\u00e1 nie je. Na druhej strane m\u00e1 tento sp\u00f4sob vy\u0161\u0161iu \u0161ancu odhali\u0165 chyby ako jedin\u00fd paritn\u00fd bit. \u00daspe\u0161nos\u0165 je zhruba 70 \u2013 80%.<\/p>\n

\"\"<\/p>\n

5.2.2\u2002 Kontroln\u00fd s\u00fa\u010det<\/h3>\n

Kontroln\u00fd s\u00fa\u010det sme u\u017e vysvet\u013eovali na\u00a04. predn\u00e1\u0161ke<\/a>. Tento sp\u00f4sob kontroly sa vyu\u017e\u00edva v transportnej vrstve. Kontroln\u00fd s\u00fa\u010det je n\u00e1ro\u010dn\u00e9 po\u010d\u00edta\u0165 hardv\u00e9rovou implement\u00e1ciou, je ur\u010den\u00fd sk\u00f4r na softv\u00e9rov\u00e9 spracovanie. \u00daspe\u0161nos\u0165 tejto met\u00f3dy je vy\u0161e 95 percentn\u00e1.<\/p>\n

5.2.3\u2002 CRC : kontrola cyklick\u00fdm polyn\u00f3mom<\/h3>\n

CRC (cyclic redundancy check) je met\u00f3da, ktor\u00e1 m\u00e1 hne\u010f dve v\u00fdhody. Prvou je \u013eahk\u00e1 hardv\u00e9rov\u00e1 implement\u00e1cia a druhou je vysok\u00e1 \u00faspe\u0161nos\u0165 odha\u013eovania ch\u00fdb \u2013 a\u017e 99,99999998 % ch\u00fdb r\u00e1mcov pri pou\u017eit\u00ed 32 kontroln\u00fdch bitov.<\/p>\n

Aj ke\u010f hardv\u00e9rov\u00e1 implement\u00e1cia je jednoduch\u00e1, na jej pochopenie je potrebn\u00e9 pozna\u0165 aj matematick\u00e9 pozadie tejto met\u00f3dy. Najprv si povedzme, \u010do je to\u00a0cyklick\u00fd polyn\u00f3m<\/strong>. Cyklick\u00fd polyn\u00f3m s koeficientami zo zvy\u0161kovej triedy modulo\u00a0m<\/em>, je tak\u00fd polyn\u00f3m, ktor\u00e9ho koeficienty m\u00f4\u017eu ma\u0165 hodnoty iba cel\u00e9 \u010d\u00edsla z intervalu <0,m-1>. V met\u00f3de CRC pou\u017e\u00edvame cyklick\u00e9 polyn\u00f3my s koeficientami zo zvy\u0161kovej triedy modulo 2. To znamen\u00e1, \u017ee koeficientami polyn\u00f3mu m\u00f4\u017eu by\u0165 iba \u010d\u00edsla 0 alebo 1. Pre jednoduchos\u0165 u\u017e budeme namiesto cyklick\u00e9ho polyn\u00f3mu s koeficientami zo zvy\u0161kovej triedy modulo 2 hovori\u0165 iba cyklick\u00fd polyn\u00f3m.<\/p>\n

Na d\u00e1ta\u00a0D<\/strong>\u00a0sa budeme pozera\u0165 ako na koeficienty cyklick\u00e9ho polyn\u00f3mu\u00a0D(x)<\/strong>.<\/p>\n

\"\"<\/p>\n

Odosielate\u013e aj pr\u00edjemca musia ma\u0165 vopred dohodnut\u00fd kontroln\u00fd cyklick\u00fd polyn\u00f3m\u00a0G(x)<\/strong>\u00a0stup\u0148a\u00a0r<\/strong>. Kontroln\u00e9 polyn\u00f3my s\u00fa ur\u010den\u00e9 pr\u00edslu\u0161n\u00fdmi normami pre jednotliv\u00e9 protokoly. Napr\u00edklad v Ethernete sa pou\u017e\u00edva \u0161tandardizovan\u00fd cyklick\u00fd polyn\u00f3m stup\u0148a 32: x32<\/sup>+x26<\/sup>+x23<\/sup>+x22<\/sup>+x16<\/sup>+x12<\/sup>+x11<\/sup>+x10<\/sup>+x8<\/sup>+x7<\/sup>+x5<\/sup>+x4<\/sup>+x2<\/sup>+x+1.<\/p>\n

Pre \u00fa\u010dely vysvetlenia fungovania CRC predpokladajme kontroln\u00fd cyklick\u00fd polyn\u00f3m stup\u0148a 3: x3<\/sup>+x+1.<\/p>\n

Ako prv\u00fd krok v\u00fdpo\u010dtu vyn\u00e1sob\u00edme d\u00e1tov\u00fd polyn\u00f3m\u00a0D(x)<\/strong>\u00a0s xr<\/strong><\/sup>\u00a0teda v tomto pr\u00edpade s x3<\/sup>. Predpokladajme, \u017ee na\u0161e d\u00e1ta\u00a0D<\/strong>\u00a0s\u00fa 10101.\u00a0D(X)<\/strong>\u00a0je potom x4<\/sup>+x2<\/sup>+1. Ten v prvom kroku vyn\u00e1sob\u00edme s x3<\/sup>\u00a0a dostaneme tak cyklick\u00fd polyn\u00f3m x7<\/sup>+x5<\/sup>+x3<\/sup>.<\/p>\n

V druhom kroku tento polyn\u00f3m vydel\u00edme kontroln\u00fdm polyn\u00f3mom x3<\/sup>+x+1. Pri v\u00fdpo\u010dte n\u00e1s nezauj\u00edma v\u00fdsledok delenia, ale zvy\u0161ok po delen\u00ed. Koeficienty zvy\u0161ku po delen\u00ed tvoria kontroln\u00fa inform\u00e1ciu, ktor\u00e1 sa priklad\u00e1 k odosielan\u00fdm d\u00e1tam. Zn\u00e1zornime si, ako by prebiehal na papieri v\u00fdpo\u010det delenia t\u00fdchto cyklick\u00fdch polyn\u00f3mov.<\/p>\n

\"\"<\/p>\n

V prvom kroku sme vyn\u00e1sobili kontroln\u00fd polyn\u00f3m (delite\u013e) s x4<\/sup>, \u010d\u00edm sme dostali polyn\u00f3m x7<\/sup>+x5<\/sup>+x4<\/sup>. Ten sme od\u010d\u00edtali od delenca a vy\u0161iel n\u00e1m zvy\u0161ok x4<\/sup>+x3<\/sup>. Ten sa st\u00e1le d\u00e1 deli\u0165 kontroln\u00fdm polyn\u00f3mom, tak\u017ee sme vyn\u00e1sobili kontroln\u00fd polyn\u00f3m s x, \u010d\u00edm sme dostali polyn\u00f3m x4<\/sup>+x2<\/sup>+x. Ten sme od\u010d\u00edtali od x4<\/sup>+x3<\/sup>\u00a0a vy\u0161iel n\u00e1m zvy\u0161ok x3<\/sup>+x2<\/sup>+x. Ten sa st\u00e1le d\u00e1 deli\u0165 kontroln\u00fdm polyn\u00f3mom, tak\u017ee sme vyn\u00e1sobili kontroln\u00fd polyn\u00f3m s 1, \u010d\u00edm sme dostali polyn\u00f3m x3<\/sup>+x+1. Ten sme od\u010d\u00edtali od x3<\/sup>+x2<\/sup>+x a vy\u0161iel n\u00e1m zvy\u0161ok x2<\/sup>+1. Ten sa u\u017e \u010falej deli\u0165 kontroln\u00fdm polyn\u00f3mom ned\u00e1, tak\u017ee m\u00e1me kone\u010dn\u00fd zvy\u0161ok po delen\u00ed reprezentovan\u00fd polyn\u00f3mom\u00a0R(x)<\/strong>. Ak z neho extrahujeme iba koeficienty, dostaneme kontroln\u00e9 bity R s hodnotami 101, ktor\u00e9 sa maj\u00fa pripoji\u0165 za d\u00e1ta.<\/p>\n

V tomto pr\u00edklade sme pou\u017e\u00edvali oper\u00e1ciu od\u010d\u00edtania. T\u00e1to oper\u00e1cia je v pr\u00edpade cyklick\u00fdch polyn\u00f3mov identick\u00e1 s oper\u00e1ciou s\u010d\u00edtania a s oper\u00e1ciou XOR, preto\u017ee koeficienty polyn\u00f3mov s\u00fa zo zvy\u0161kovej triedy modulo 2. V tejto zvy\u0161kovej triede teda plat\u00ed:<\/p>\n

\n\n\n\n\n\n\n
0 + 0 = 0<\/td>\n0 \u2013 0 = 0<\/td>\n0 XOR 0 = 0<\/td>\n<\/tr>\n
0 + 1 = 1<\/td>\n0 \u2013 1 = 1<\/td>\n0 XOR 1 = 1<\/td>\n<\/tr>\n
1 + 0 = 1<\/td>\n1 \u2013 0 = 1<\/td>\n1 XOR 0 = 1<\/td>\n<\/tr>\n
1 + 1 = 0<\/td>\n1 \u2013 1 = 0<\/td>\n1 XOR 1 = 0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n

Ke\u010f\u017ee pri delen\u00ed n\u00e1sob\u00edme kontroln\u00fd polyn\u00f3m v\u017edy len s nejak\u00fdm 1xk<\/sup>, v\u00fdsledn\u00fd polyn\u00f3m, ktor\u00fd ideme od\u010d\u00edtava\u0165 od predch\u00e1dzaj\u00faceho zvy\u0161ku, m\u00e1 a\u017e na r\u00e1d mocn\u00edn st\u00e1le rovnak\u00fd tvar. V pr\u00edpade n\u00e1\u0161ho kontroln\u00e9ho polyn\u00f3mu x3<\/sup>+x+1, \u010do je to ist\u00e9 ako 1x3<\/sup>+0x2<\/sup>+1x1<\/sup>+1x0<\/sup>, je to 1x3+k<\/sup>+0x2+k<\/sup>+1x1+k<\/sup>+1x0+k<\/sup>. Ak si vyp\u00ed\u0161eme iba koeficienty dost\u00e1vame \u010d\u00edslo 1011, za ktor\u00fdm nasleduje k n\u00fal. Napr\u00edklad v prvom kroku delenia sme n\u00e1sobili kontroln\u00fd polyn\u00f3m s x4<\/sup>, teda koeficienty, ktor\u00e9 dost\u00e1vame s\u00fa 10110000. Toto pozorovanie vyu\u017eijeme.<\/p>\n

Zjednodu\u0161me si teraz cel\u00fd z\u00e1pis v\u00fdpo\u010dtu iba na koeficienty, teda na p\u00f4vodn\u00e9 bin\u00e1rne d\u00e1ta, ktor\u00e9 chceme prenies\u0165. Namiesto s\u010d\u00edtavania\/od\u010d\u00edtavania budeme p\u00edsa\u0165 XOR, lebo je to prirodzenej\u0161ie pre bin\u00e1rne z\u00e1pisy \u010d\u00edsiel.<\/p>\n

    10101000 : 1011 = v\u00fdsledok n\u00e1s nezauj\u00edma\r\nXOR 1011\r\n    ----\r\n    0001100\r\n   XOR 1011\r\n       ----\r\n       01110\r\n    XOR 1011\r\n        ----\r\n         101\r\n<\/pre>\n
Vid\u00edme, \u017ee koeficienty kontroln\u00e9ho polyn\u00f3mu 1011, sme pou\u017eili na oper\u00e1ciu XOR v\u017edy so zarovnan\u00edm na prv\u00fa jednotku predch\u00e1dzaj\u00faceho zvy\u0161ku. V tomto pr\u00edpade to znamen\u00e1, \u017ee na za\u010diatku si \u010d\u00edslo 1011 (za n\u00edm si predstav\u00edme 4 nuly) nap\u00ed\u0161eme pod \u010d\u00edslo 10101000 so zarovnan\u00edm do\u013eava a urob\u00edme XOR. V\u00fdsledkom je 00011000. Ke\u010f si odmysl\u00edme prv\u00e9 tri nuly tak m\u00e1me zvy\u0161ok 11000. Pod neho si zap\u00ed\u0161eme zn\u00e1me \u010d\u00edslo 1011 so zarovnan\u00edm do\u013eava (za n\u00edm si predstav\u00edme e\u0161te jednu nulu) a vypo\u010d\u00edtame XOR. V\u00fdsledok je 01110. Urob\u00edme e\u0161te jeden XOR s \u010d\u00edslom 1011. V\u00fdsledok 101 je u\u017e krat\u0161\u00ed ako 1011 a m\u00f4\u017eeme skon\u010di\u0165. Nakoniec sme dostali zvy\u0161ok 101, ako v predch\u00e1dzaj\u00facom v\u00fdpo\u010dte. Odosielame d\u00e1ta 10101 spolu so zvy\u0161kom 101, teda 10101101.<\/p>\n
\u010co s t\u00fdm sprav\u00ed pr\u00edjemca? Vezme doru\u010den\u00fa postupnos\u0165 10101101, pozrie sa na \u0148u ako na cyklick\u00fd polyn\u00f3m x7<\/sup>+x5<\/sup>+x3<\/sup>+x2<\/sup>+1 a ten vydel\u00ed vopred dohodnut\u00fdm kontroln\u00fdm cyklick\u00fdm polyn\u00f3mom\u00a0G(x)<\/strong>=x3<\/sup>+x+1. Ak je zvy\u0161ok po tomto delen\u00ed nula, pova\u017eujeme postupnos\u0165 s ve\u013ekou pravdepodobnos\u0165ou za neporu\u0161en\u00fa . Naopak, ak zvy\u0161ok po delen\u00ed nie je nula, odhalili sme chybu. Nap\u00ed\u0161me si u\u017e rovno v\u00fdpo\u010det v zjednodu\u0161enej forme iba s koeficientmi.<\/p>\n
    10101101 : 1011 = v\u00fdsledok n\u00e1s nezauj\u00edma\r\nXOR 1011\r\n    ----\r\n    0001110\r\n   XOR 1011\r\n       ----\r\n       01011\r\n    XOR 1011\r\n        ----\r\n        0000\r\n<\/pre>\n
Ako vid\u00edme, v\u00fdpo\u010det \u201ena papieri\u201c je vcelku jednoduch\u00fd. Re\u00e1lne sa ale v\u00fdpo\u010det realizuje inak, aby bol v\u00fdpo\u010det r\u00fdchly a hlavne jednoducho hardv\u00e9rovo realizovate\u013en\u00fd. Pri n\u00e1vrhu \u201ev\u00fdpo\u010dtov\u00e9ho\u201c obvodu sa vych\u00e1dza z kontroln\u00e9ho cyklick\u00e9ho polyn\u00f3mu. Samotn\u00fd obvod sa sklad\u00e1 iba z posuvn\u00fdch registrov a XOR hradiel. Ak pou\u017e\u00edvame kontroln\u00fd cyklick\u00fd polyn\u00f3m stup\u0148a\u00a0r<\/strong>, zapoj\u00edme ved\u013ea seba\u00a0r<\/strong>\u00a0posuvn\u00fdch 1 bitov\u00fdch registrov a v\u0161ade tam, kde sa nach\u00e1dza koeficient 1 e\u0161te vlo\u017e\u00edme XOR hradlo okrem jednotky pri xr<\/sup>. Pre n\u00e1\u0161 kontroln\u00fd cyklick\u00fd polyn\u00f3m\u00a0G(x)<\/strong>=x3<\/sup>+x+1 by tento obvod vyzeral nasledovne:<\/p>\n
\"\"<\/p>\n
Po spracovan\u00ed cel\u00e9ho vstupu je v registroch v\u00fdsledn\u00fd zvy\u0161ok po delen\u00ed. Pekn\u00e9 anim\u00e1cie o tom, ako v\u00fdpo\u010det prebieha m\u00f4\u017eete n\u00e1js\u0165 napr\u00edklad na\u00a0wikipedii<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Odha\u013eovanie ch\u00fdb sl\u00fa\u017ei na to, aby si pr\u00edjemca bol primerane ist\u00fd t\u00fdm, \u017ee dostal presne tie ist\u00e9 d\u00e1ta, ktor\u00e9 boli odoslan\u00e9 odosielate\u013eom. Za chybu sa…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"_links":{"self":[{"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/posts\/369"}],"collection":[{"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/comments?post=369"}],"version-history":[{"count":3,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/posts\/369\/revisions"}],"predecessor-version":[{"id":476,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/posts\/369\/revisions\/476"}],"wp:attachment":[{"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/media?parent=369"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/categories?post=369"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/tech.sosthe.sk\/index.php\/wp-json\/wp\/v2\/tags?post=369"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}