Ji°φ Peterka

Sv∞t poΦφtaΦ∙, poΦφtaΦov²ch komunikacφ a digitßlnφch p°enos∙ obecn∞ vd∞Φφ za svou existenci a za svΘ fungovßnφ v²sledk∙m mnoha v∞dnφch obor∙ - nejen fyziky, kterß stajφ za celou technologiφ v²roby souΦßstek, ze kter²ch jsou dneÜnφ poΦφtaΦe a dalÜφ aktivnφ prvky postaveny. Stejn∞ tak vd∞Φφ digitßlnφ sv∞t za mnohΘ nap°φklad i matematice.

Velmi p∞kn²m p°φkladem zde m∙₧e b²t pou₧φvßnφ tzv. cyklick²ch zabezpeΦovacφch k≤d∙ (anglicky: Cyclic Redundancy Checks, zkratkou CRC). Jde o k≤dy, pou₧φvanΘ k zabezpeΦenφ dat p°i jejich p°enosu (nebo i p°i jakΘmkoli jejich äskladovßnφ"), a majφ za ·kol umo₧nit detekci p°φpadn²ch chyb v t∞chto datech. Jsou to tedy k≤dy detekΦnφ, podobn∞ jako tzv. parita Φi kontrolnφch souΦty, o kter²ch jsme si povφdali minule. Analogick² je zßkladnφ princip jejich vyu₧itφ: odesilatel aplikuje na odesφlanß data algoritmus, na kterΘm je dohodnut s p°φjemcem, a kter² vypl²vß z povahy detekΦnφho k≤du. V²sledkem je pak zabezpeΦovacφ ·daj, kter² odesilatel äp°iÜpendlφ" k p∙vodnφm dat∙m, a odeÜle je p°φjemci. Ten aplikuje na p°ijatß data p°esn∞ stejn² algoritmus, a v²sledek porovnß se zabezpeΦovacφm ·dajem, kter² obdr₧el od odesilatele. Jde-li nap°φklad o zabezpeΦenφ kontrolnφm souΦtem, spoΦφvß zmφn∞n² algoritmus v prostΘm seΦtenφ jednotliv²ch datov²ch byt∙ Φi slov, chßpan²ch pro tento ·Φel jako Φφsla, a zabezpeΦovacφm ·dajem je pak v²sledn² souΦet. Jak jsme si ale ji₧ uvßd∞li minule, Spolehlivost zabezpeΦenφ pomocφ kontrolnφch souΦt∙ ovÜem nenφ p°φliÜ velikaß, a pro mnohΘ ·Φely nedostateΦnß.

DostateΦnou spolehlivost nabφzφ a₧ v²Üe avizovanΘ cyklickΘ k≤dy (CRC)- nap°φklad zabezpeΦovacφ ·daj, generovan² podle tΘto metody v nejΦast∞ji pou₧φvanΘm rozsahu 16 bit∙, umo₧≥uje p°φjemci 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 p°edem 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, a tent²₧ aparßt je pak t°eba i k d∙kazu toho, ₧e s tφmto d∞litelem vÜe funguje s onou v²Üe uvedenou bßjeΦnou spolehlivostφ, velmi se blφ₧φcφ stu procent. Z konkrΘtnφ hodnoty tohoto Φφsla-d∞litele (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 (ba p°φmo trivißlnφho obvodu), kter² ob∞ strany pou₧φvajφ pro praktickΘ generovßnφ zabezpeΦovacφch ·daj∙ a kontrolu sprßvnosti p°enesen²ch dat.