Ji°φ Peterka: Co je Φφm ... v poΦφtaΦov²ch sφtφch (3):

ZabezpeΦenφ dat p°i p°enosech

P°i p°enosech dat m∙₧e dochßzet k chybßm, a v jejich d∙sledku m∙₧e p°φjemce p°ijmout jinΘ znaky, ne₧ jakΘ mu odesilatel p∙vodn∞ vyslal. Jednφm mo₧n²m prost°edkem pro nßslednou detekci vznikl²ch chyb je p°idßnφ paritnφho bitu ke ka₧dΘmu p°enßÜenΘmu znaku (jak jsme si naznaΦili minul² t²den) - to je vÜak jen nejjednoduÜÜφ (a takΘ nejmΘn∞ ·Φinn²) p°φpad pou₧itφ tzv. bezpeΦnostnφch k≤d∙.

Zßkladnφ myÜlenka pou₧itφ bezpeΦnostnφch k≤d∙ je velmi jednoduchß - p∙vodnφ znaky se podle p°esn∞ definovan²ch pravidel transformujφ na znaky jinΘho typu (nap°. osmibitovΘ znaky se p°idßnφm jednoho paritnφho bitu p°evedou na devφtibitovΘ). Teprve ty se pak skuteΦn∞ p°enesou a p°φjemce si je p°evede zp∞t do jejich p∙vodnφho tvaru. N∞kterΘ znaky onoho "jinΘho typu" vÜak nemohou z p∙vodnφch znak∙ °ßdn²m zp∙sobem nikdy vzniknout (nap°. p°i pou₧φvßnφ lichΘ parity bychom nem∞li nikdy zφskat znak se sudou paritou). Pokud pak p°φjemce p°ijme takov² znak, kter² p°i dan²ch pravidlech transformace nemß ₧ßdn² "vzor", m∙₧e jej oprßvn∞n∞ pova₧ovat za chybn∞ p°enesen² znak.

BezpeΦnostnφ k≤dy jsou v zßsad∞ dvojφho typu, a to:

• detekΦnφ k≤dy - error-detection codes, kterΘ umo₧≥ujφ pouze rozpoznat (detekovat), ₧e p°ijat² znak je chybn², a
• samoopravnΘ k≤dy - self-correcting codes, kterΘ krom∞ detekce chyby umo₧≥ujφ i opravu chybn∞ p°enesenΘho znaku, tak₧e jej nenφ nutnΘ p°enßÜet znovu (co₧ u detekΦnφho k≤du obecn∞ nutnΘ je).

Pou₧itφ bezpeΦnostnφch k≤d∙ v₧dy znamenß, ₧e se v rßmci ka₧dΘho znaku ve skuteΦnosti p°enßÜφ vφce bit∙, ne₧ kolik by bylo k vyjßd°enφ vlastnφho znaku nezbytn∞ nutnΘ. ZabezpeΦenφ proti chybßm nenφ navφc nikdy stoprocentnφ, jeho ·Φinnost vÜak roste s poΦtem bit∙ "navφc". NejjednoduÜÜφ detekΦnφ k≤d (zabezpeΦenφ sudou nebo lichou paritou) p°idßvß k datov²m bit∙m jeden dalÜφ bit a dokß₧e detekovat chybu v jednom bitu. Samoopravn² k≤d, kter² umo₧≥uje nßslednou opravu chyby v jedinΘm bitu (tzv. rozÜφ°en² Hamming∙v k≤d), p°idßvß ke ka₧dΘmu 8-bitovΘmu bytu navφc p∞t bit∙ (resp. 6 bit∙ ke ka₧dΘmu 16-bitovΘmu slovu).

V praxi je v²hodn∞jÜφ nezabezpeΦovat proti chybßm jednotlivΘ znaky, ale celΘ posloupnosti znak∙ resp. celΘ p°enßÜenΘ bloky dat. DodateΦnΘ bity, pou₧φvanΘ k detekci chyb, se pak nep°idßvajφ znovu ke ka₧dΘmu znaku, ale jen jednou k celΘmu bloku dat (a p°enesou se spolu s nφm). Je-li pak chyba detekovßna, nelze ji v rßmci bloku lokalizovat a₧ na jednotlivΘ znaky. Mφsto toho musφ b²t cel² blok prohlßÜen za chybn² a p°enesen znovu. To ovÜem nemusφ b²t v∙bec na zßvadu - staΦφ si uv∞domit, ₧e p°enosy dat tΘm∞° v₧dy probφhajφ po cel²ch blocφch, a nejmenÜφ jednotkou dat, jejφ₧ opakovanΘ vyslßnφ si m∙₧e p°φjemce vy₧ßdat, je prßv∞ cel² blok a nikoli jednotlivΘ znaky.

PodΘlnß parita - longitudinal parity

Obr. 3.1.: ZabezpeΦenφ paritou

Pou₧itφ podΘlnΘ parity se n∞kdy kombinuje i se zabezpeΦenφm jednotliv²ch znak∙ pomocφ sudΘ resp. lichΘ parity, kterß se pak pro odliÜenφ od podΘlnΘ parity oznaΦuje jako p°φΦnß Φi znakovß parita (transversal, lateral parity). Ob∞ varianty ilustruje obrßzek 3.1.

Kontrolnφ souΦet - checksum

DalÜφ mo₧nostφ zabezpeΦenφ celΘho bloku dat je souΦet jednotliv²ch znak∙ v bloku, kterΘ jsou pro tento ·Φel chßpßny jako celß dvojkovß Φφsla bez znamΘnka. Kontrolnφ souΦet se typicky provßdφ jako souΦet modulo 2⁸ nebo 2¹⁶, tj. v²sledkem je kontrolnφ souΦet o dΘlce jednoho nebo dvou byt∙.

Kontrolnφ souΦet i podΘlnou paritu lze vyhodnocovat pr∙b∞₧n∞ p°i p°ijφmßnφ jednotliv²ch znak∙ bloku. V p°φpad∞ kontrolnφho souΦtu se ka₧d² nov∞ p°ijat² znak p°iΦφtß ke stßvajφcφmu mezisouΦtu, zatφmco v p°φpad∞ podΘlnΘ parity se provßdφ operace EX-OR (tj. nonekvivalence) jednotliv²ch bit∙ novΘho znaku se stßvajφcφm meziv²sledkem.

Nej·Φinn∞jÜφ formu zabezpeΦenφ bloku dat vÜak p°edstavuje pou₧itφ tzv. cyklick²ch k≤d∙ - CRC (Cyclic Redundancy Check). TakΘ zde se podobn∞ jako u v²poΦtu podΘlnΘ parity Φi kontrolnφho souΦtu pr∙b∞₧n∞ na zßklad∞ jednotliv²ch znak∙ bloku (p°esn∞ji jednotliv²ch bit∙ t∞chto znal∙) pr∙b∞₧n∞ vypoΦφtßvß zabezpeΦovacφ ·daj. Ten se na konci celΘho bloku porovnß se zabezpeΦovacφm ·dajem, kter² podle stejn²ch pravidel vypoΦφtal odesilatel a p°ipojil k odesφlanΘmu bloku dat. Pokud se oba ·daje shodujφ, lze p°enesen² blok s vysokou pravd∞podobnostφ pova₧ovat za sprßvn² - zabezpeΦenφ pomocφ ÜestnßctibitovΘho cyklickΘho k≤du toti₧ dokß₧e spolehliv∞ odhalit vÜechny chyby a₧ v Üestnßcti po sob∞ jdoucφch bitech, a chyby ve v∞tÜφm poΦtu bit∙ s p°esnostφ 99,9984 %.

Formßlnφ d∙kaz vynikajφcφ ·Φinnosti zabezpeΦenφ pomocφ cyklickΘho k≤du sice vy₧aduje dosti pokroΦil² matematick² aparßt, vlastnφ zp∙sob v²poΦtu zabezpeΦovacφho ·daje je vÜak a₧ neuv∞°iteln∞ jednoduch² (bohu₧el vÜak zde ji₧ nemßme pot°ebn² prostor k tomu, abychom tuto jednoduchost mohli pat°iΦn∞ "vychutnat"). StaΦφ k n∞mu jednoduch² posuvn² registr, umo₧≥ujφcφ provΘst operaci EX-OR (tj. nonekvivalenci jednotliv²ch bit∙) s pevn∞ danou maskou. Hodnota tΘto masky je jednoznaΦn∞ urΦena tzv. generujφcφm polynomem (generating polynomial), na kterΘm musφ b²t p°φjemce i odesilatel p°edem dohodnuti. Pou₧iteln²ch tvar∙ t∞chto polynom∙ je vφce; v oblasti komunikacφ se nejΦast∞ji pou₧φvß polynom x¹⁶ + x¹² + x⁵ + 1, doporuΦen² organizacφ CCITT.