Ji°φ Peterka

Chyby se vyskytujφ vÜude - chybujφ nejen lidΘ, ale i nejr∙zn∞jÜφ p°enosovΘ mechanismy, prost°edky i celΘ technologie. N∞kdy, za urΦitΘ situace, nemusφ p°i p°enosu dat chyby vadit. Nap°φklad kdy₧ z n∞jakΘho d∙vodu je nejvyÜÜφ prioritou rychlost, a p°φpadnΘ napravovßnφ chyb by pouze zdr₧ovalo. P°φkladem m∙₧e b²t p°enos ₧ivΘho obrazu, p°i kterΘm velmi zßle₧φ na rychlosti a pravidelnosti p°φsunu dat, zatφmco drobnΘ chyby v jednotliv²ch snφmcφch lidskΘ oko nemusφ ani zaregistrovat.

P°i v∞tÜin∞ datov²ch p°enos∙ ovÜem b²vajφ p°φpadnΘ chyby na zßvadu, a je t°eba na n∞ n∞jak reagovat. Jak, to ji₧ zßvisφ na konkrΘtnφ strategii a celkovΘm p°φstupu komunikujφcφch stran (a tato problematika by si jist∞ zaslou₧ila samostatn² dφl tohoto serißlu). Dnes se ale reakcemi na p°φpadnΘ chyby nebudeme jeÜt∞ zab²vat - dnes nßm p∙jde o n∞co zßkladn∞jÜφho: jak v∙bec poznat, ₧e n∞jakß data doÜla poÜkozena?. Nenφ jist∞ t∞₧kΘ nahlΘdnout, ₧e mß-li n∞kterß z komunikujφcφch stran reagovat na chybu p°i p°enosu, musφ ji um∞t rozpoznat (tzv. detekovat). Dnes tedy p∙jde o metody detekce, konkrΘtn∞ o tu z nich, kterß je dnes zdaleka nejpou₧φvan∞jÜφ: o pou₧itφ tzv. cyklick²ch k≤d∙ (Cyclic Redundacy Check), znßm∞jÜφch spφÜe pod anglickou zkratkou CRC.

Princip, na kterΘm jsou zalo₧eny obecn∞ vÜechny detekΦnφ k≤dy (tedy k≤dy, umo₧≥ujφcφ rozpoznat chybu), je velmi jednoduch²: k p°enßÜen²m dat∙m se p°ipojφ urΦitß dopl≥ujφcφ informace äzabezpeΦovacφho" charakteru, a ta je p°enesena k p°φjemci spoleΦn∞ s"u₧iteΦn²mi" daty. P°φjemce p°itom musφ b²t s odesilatelem domluven na pou₧itΘ technice zabezpeΦenφ, a musφ tedy znßt p°esn² v²znam onoho zabezpeΦovacφho ·daje, kter² p°ijme spoleΦn∞ s vlastnφmi daty. P°φjemce pak aplikuje na vlastnφ data stejn² algoritmus, podle kterΘho odesilatel stanovil dopl≥ujφcφ zabezpeΦovacφ ·daj, a sv∙j v²sledek porovnß s v²sledkem druhΘ strany. Pokud se nerovnajφ, mß p°φjemce tΘm∞° jistotu, ₧e p°i p°enosu doÜlo k chyb∞. OvÜem pokud se oba v²sledky rovnajφ, nemß jistotu ₧e k ₧ßdnΘ chyb∞ nedoÜlo - vφ jen, ₧e k chyb∞ nedoÜlo s urΦitou pravd∞podobnostφ, jejφ₧ hodnota je dßna prßv∞ vlastnosti pou₧itΘho zp∙sobu zabezpeΦenφ.

NejjednoduÜÜφm p°φkladem zabezpeΦovacφho mechanismu m∙₧e b²t tzv. parita - nap°φklad v takovΘ variant∞, p°i kterΘ je ke ka₧dΘmu p°enßÜenΘmu bytu p°idßn jeÜt∞ jeden paritnφ bit, dopl≥ujφcφ p∙vodnφ poΦet jedniΦek v danΘm bytu na lich² poΦet (v p°φpad∞ tzv. lichΘ parity, analogicky p°i tzv. sudΘ parit∞). Lze ovÜem snadno nahlΘdnout, ₧e takovΘto zabezpeΦenφ nenφ p°φliÜ ·ΦinnΘ - staΦφ jej obelstφt nap°φklad ji₧ chyba ve dvou bitech danΘho bytu, obecn∞ v sudΘm poΦtu bit∙ najednou. Navφc p°idßnφ paritnφho bitu ke ka₧dΘmu p°enßÜenΘmu bytu zv²Üφ celkov² objem p°enßÜen²ch dat o jednu osminu, co₧ rozhodn∞ nenφ zanedbatelnΘ.

Pon∞kud inteligentn∞jÜφ je pou₧itφ kontrolnφch souΦt∙. JednotlivΘ byty p°enßÜen²ch dat se p°i tΘto metod∞ chßpou jako Φφsla (obvykle celß Φφsla bez znamΘnka), a jako takovΘ se seΦtou. Z v²slednΘho souΦtu se pak vezme vhodn∞ velkß Φßst (nap°φklad nejni₧Üφch 16 bit∙), a ta se p°ipojφ k vlastnφm dat∙m a odeÜle p°φjemci. ten pak obdobn∞ äposΦφtß" p°ijatß data, sv∙j v²sledke porovnß s p°ijat²m kontrolnφm souΦtem. Re₧ie na p°enos je v²razn∞ ni₧Üφ, ale i zde se m∙₧e snadno stßt, ₧e i p°i poÜkozenφ p°enßÜen²ch dat bude jejich v²sledn² kontrolnφ souΦet stejn² (a p°φjemce tudφ₧ chybu p°i p°enosu nerozpoznß). Spolehlivost kontrolnφch souΦt∙ je sice vyÜÜφ ne₧ u parity, ale stßle nenφ dostateΦnß.

DostateΦnou spolehlivost nabφzφ a₧ v²Üe avizovanΘ pou₧itφ tzv. cyklick²ch k≤d∙ - pou₧ijeme-li zabezpeΦovacφ ·daj v nejΦast∞ji pou₧φvanΘm rozsahu 16 bit∙, dokß₧e p°φjemce s jeho pomocφ rozpoznat vÜechny shluky chybn²ch bit∙ se stoprocentnφ jistotou, shluky dΘlky 17 bit∙ s pravd∞podobnostφ 99,9968%, a ostatnφ chyby s pravd∞podobnostφ 99,9984%. Neznφ to jako fantazie, nebo dokonce jako nemo₧nost?

Pokud nechcete mΘmu tvrzenφ v∞°it a chcete si sami dokßzat jeho pravdivost, budete k tomu pot°ebovat velmi siln² matematick² aparßt, konkrΘtn∞ aparßt algebry, zab²vajφcφ se okruhy polynom∙ nad t∞lesem dimenze 2. Za fungovßnφm cyklick²ch k≤d∙ toti₧ stojφ opravdu pokroΦilß matematika. Pokud ale nejsou tyto partie zrovna vaÜφm konφΦkem, v∙bec to nevadφ - k praktickΘmu pou₧φvßnφ detekΦnφch mechanism∙ na bßzi cyklick²ch k≤d∙ ₧ßdn² matematick² aparßt nepot°ebujete. Pot°ebujete pouze velmi konkrΘtnφ a ryze praktick² nßvod na to, jak z p°enßÜen²ch dat vyrobit onen zabezpeΦovacφ ·daj, kter² pak k dat∙m p°ipojφte a odeÜlete sm∞rem k p°φjemci. Ten pak zase pot°ebuje v∞d∞t, co mß s p°ijat²mi daty a zabezpeΦovacφm ·dajem ud∞lat, aby si mohl odvodit zda jsou poÜkozenß, nebo s hodn∞ velkou pravd∞podobnostφ nepoÜkozenß. V obou p°φpadech p°itom staΦφ äprohnat" p°enßÜenß data p°φmo trivißlnφm logick²m obvodem, kter² na stran∞ odesilatale vyrobφ zabezpeΦovacφ ·daj, a na stran∞ p°φjemce °ekne ano Φi ne.

Pokud by vßs ale p°eci jen zajφmalo, na jakΘm principu zabezpeΦenφ cyklick²mi k≤dy pracuje, pak se pokusφm o maximßlnφ mo₧nΘ zjednoduÜenφ: odesilatel si data urΦenß k odeslßnφ na chvφli p°edstavφ jako jedno velkΘ Φφslo (co₧ nenφ tak t∞₧kΘ, v₧dy¥ jde ve svΘ podstat∞ jen o posloupnost nul a jedniΦek). Toto Φφslo pak vyd∞lφ jin²m Φφslem, na kterΘm je s p°φjemcem domluven. Podφl, kter² mu vyjde, okam₧it∞ zapomene, ale vyu₧ije zbytek po d∞lenφ - ten p°ipojφ k vlastnφm dat∙m jako zabezpeΦujφcφ ·daj, a vÜe pak odeÜle. P°φjemce pak opakuje stejn² postup a dφvß se, zda dostal stejn² zbytek. Podstatnou roli zde p°itom hraje Φφslo (d∞litel), kter²m se p°enßÜenß data d∞lφ, a na kterΘm musφ b²t ob∞ strany domluveny - toto Φφslo samoz°ejm∞ nem∙₧e b²t ledajakΘ. Jeho konkrΘtnφ hodnotu lze nalΘzt jen s vyu₧itφm onoho silnΘho matematickΘho aparßtu. Z konkrΘtnφ hodnoty tohoto Φφsla (ve skuteΦnosti polynomu, resp. tzv. vytvß°ejφcφ mnohoΦlenu, ale p°i naÜem maximßlnφm zjednoduÜenφ pouhΘho Φφsla) pak p°φmo vypl²vß funkce i struktura jednoduchΘho (Φi spφÜe p°φmo trivißlnφho obvudu), kter² ob∞ strany pou₧φvajφ pro praktickΘ generovßnφ zabezpeΦovacφch ·daj∙ a kontrolu sprßvnosti p°enesen²ch dat.