Ko si je digitalna tehnologija začela utirati pot v naša življenja, so nam govorili, da je ta tehnologija oh in sploh predvsem zato, ker v njej praktično ni degradacije oziroma zmanjšanja kakovosti signala. To je bilo sicer res, a le delno. Hudič je v tisti besedi »praktično«. Tudi pri digitalnem prenosu lahko namreč pride do napak, ki so lahko posledica marsičesa – od zunanjih vremenskih vplivov pa do težav znotraj naprav. A sodobni sistemi so zgrajeni tako, da čeravno nismo najbolj nasilni in recimo z vilicami spraskamo CD, teh napak niti ne opazimo, tudi če se pojavijo. To pa zato, ker obstajajo nekateri varnostni mehanizmi, ki poskrbijo za to, da se morebitne napake zaznajo in odpravijo. A do stanja, ko naprave to znajo, je bila dokaj dolga in naporna pot.
Ta se začne v poznih štiridesetih letih prejšnjega stoletja. V podjetju Bell Telephone Company je delal možak z imenom Richard Hamming. Delal je s takrat zelo modernim elektromehanskim računalnikom, imenovanim Bell Model V. Ta računalnik je vhodne podatke dobival prek luknjanih kartic. Te so bile dokaj nezanesljive, tako da se je redno dogajalo, da podatkov niso znale prebrati. Za takšne primere je obstajal sistem opozoril, ki je operaterje opozoril na napako, in ti so jo lahko odpravili. A le med delovnim tednom. Med vikendom operaterjev ni bilo v službi in odpravljanja napak zato takrat – ni bilo. To ne bi bilo nič tragičnega, če Hamming zaradi zasedenosti sistema ne bi imel dovoljenja za uporabo računalnika prav v tem času, torej med vikendom. Poleg tega je bil sistem nastavljen tako, da če je prišlo do napake in te v določenem času ni nihče popravil, je sistem nadaljeval z naslednjo nalogo, to, v kateri se je pojavila napaka, pa prekinil. In Hammingu, ki je svoje delo opravljal prav med vikendom, se je zato pogosto zgodilo, da je njegovo računanje šlo rakom žvižgat. To mu je šlo seveda krepko na živce in odločil se je, da bo nekaj spremenil. In nastala je znanost odkrivanja in odpravljanja napak v digitalnih prenosih.
Zgodnja leta
Takratni sistemi niso vsebovali mehanizmov popravljanja napak, ampak le odkrivanja. Ko se je napaka odkrila, je operater pač ponovil branje oziroma ponovno zahteval podatke. To seveda ni bilo najbolj praktično. Kot prva rešitev se je pojavilo dodajanje tako imenovanega paritetnega bita. Kaj to pomeni? Vzemimo, da bi radi prek neke digitalne povezave prenesli neki 7-bitni znak, recimo črko ali neki drug podatek. Paritetni bit pomeni, da se tem sedmim bitom doda še eden, osmi, ki je odvisen recimo od števila enic v nizu. Vzemimo, da je naš 7-bitni znak 1001001. Vidimo, da so v njem tri enice. Če se odločimo za tako imenovano sodo pariteto, se znaku doda še ena enica in dobimo število 10010011, v katerem so štiri enice, kar je sodo število. Če se odločimo za liho pariteto, se znaku doda ničla, tako da število enic ostane liho. Na sprejemni strani prenosa se ti biti nato preverijo glede na dogovorjeno paritetno shemo. Če izračunana pariteta ni takšna, kot bi morala biti, gre za napako. Vzemimo primer, ko bi se preneseni bit moral glasiti 10010011, a se je med prenosom nekaj sfižilo in na cilj je prispel niz 10011011, torej tak, ki ima eno enico več. Ker je bila dogovorjena soda pariteta, sprejemni del ve, da je prišlo do napake, ne ve pa, kje ta je. Spremenjen bi lahko bil kateri koli bit. Druga težava, ki se pojavi, je ta, da po sistemu paritetnega bita ni mogoče ugotoviti napake, če sta se spremenila dva bita. Ali štirje, šest in tako naprej, saj v tem primeru pariteta ostane enaka.
Te napake so na začetku omilili tako, da se je vsak bit prenesel večkrat. Namesto da bi vsak bit poslali le enkrat, se je poslal recimo trikrat. Namesto 1 se je tako poslal niz 111, namesto 0 pa 000. Naš omenjeni niz 10010011 je tako postal 111 000 000 111 000 000 111 111. Če je sprejemni del dobil tri enake znake, je vedel, da napake ni, če pa so bili znaki različni, je bilo jasno, da napaka je. Metoda je bila kar dobra, saj je poleg precej boljše zanesljivosti omogočala tudi osnovno korekcijo napak. Če se je namreč »trojček« glasil 001, 010 ali 100, je bila verjetnost, da je ničla prava vrednost, precej velika.
Toda tudi ta sistem je imel slabost. Predvsem v tem, da se je količina podatkov v primeru »trojčkov« potrojila. Če bi zadeva bila aktualna še danes, bi na 600-gigabajtni disk spravili le okoli 200 gigabajtov uporabnih podatkov, ostalo bi bili paritetni biti.
Paritetni biti torej temeljijo na dodajanju podatkov podatkovnemu toku z namenom odkrivanja in popravljanja napak. S tem načeloma ni nič narobe, vendar se je omenjeni paritetni način izkazal za premalo. Predvsem zato, ker je sposoben zaznati le eno- ali dvobitne napake, več pa ne. Zato si je bilo treba izmisliti nekaj novega. In to so bile nadzorne vsote.
Vzemimo, da bi radi poslali številko kreditne kartice prek interneta neki spletni trgovini. Trgovina se mora prepričati, ali gre za veljavno številko kreditne kartice, preden jo pošlje naprej banki, ki bo obračunala plačilo. In kako ugotoviti veljavnost? Se vsaka številka neposredno preverja? V poznejšem postopku se, na začetku pa se preveri le tako imenovana nadzorna vsota. Kreditne kartice so kodirane s tako imenovano nadzorno številko, ki je čisto desna oziroma zadnja števka v številki vaše kartice. Če ste številko vnesli napačno, bo tako imenovani Luhnov algoritem to zaznal in javil napako. In kako deluje tak sistem? Vzemimo, da je številka naše kartice 98762345100. Nadzorna številka oziroma vsota je torej 0. In kako se to preverja? Gre za dokaj preprost matematičen način. Začenši na desni vzamemo vsako drugo številko in jo podvojimo, ostale pa pustimo enake. V našem primeru bomo dobili številke 0, 0, 1, 10, 4, 6, 2, 12, 7, 16, 9. Zdaj vsa dvomestna števila razstavimo tako, da na primer število 12 postane 1 in 2, nato pa vsa števila seštejemo. V našem primeru bo to 0 + 0 + 1 + 0 + 1 + 4 + 6 + 2 + 1 + 2 + 7 + 1 + 6 + 9, kar znese točno 40. Ker je zadnja števka številke kreditne kartice 0, mora biti vsota večkratnik števila 10, kar v našem primeru je in številka je v redu. Če bi pri pisanju številke kartice prišlo do napake, ta vsota več ne bi bila prava. Če bi na primer zamenjali dve števki, kar je najpogostejša napaka, bi se v prvem koraku podvojila napačna in končna vsota ne bi bila več enaka.
Primer kreditnih kartic oziroma Luhnov algoritem je le eden od primerov tako imenovane nadzorne vsote. Gre torej za število, ki ga dodamo na konec prenesenega niza podatkov in ki precej bolje kot pariteta ugotavlja, ali gre za napako in tudi kje ta napaka je. Primerov nadzornih vsot pa je še veliko. Zelo verjetno je, da ste kdaj naleteli na sporočilo, da neki prenos ni uspel, saj je bilo nekaj narobe s CRC. Ta CRC ali Cyclic Redundancy Check je eden od prvih in najbolj znanih načinov preverjanja pravilnosti prenosa podatkov, ki smo jih bili deležni v osebnih računalnikih. CRC-32, kot se imenuje v celoti, je precej ugoden način ugotavljanja napak, saj je dokaj preprost in ga naprave brez težav izračunavajo, hkrati pa je uporaben za ugotavljanje tako napak, nastalih zaradi naključnega šuma v prenosu podatkov, kot tudi za napake, ki se pojavljajo zaradi večjih motenj.
CRC-32 pa seveda ni edini način. Jih je še kar nekaj, nosijo pa oznake SHA-256, MD5 in podobne. Napredne kriptografske nadzorne vsote so izdelane tako, da so sposobne odkriti zlonamerne napake. Izdelane so namreč tako, da je morebitnim nepridipravom izredno težko izdelati sporočilo ali kak drug komplet podatkov, ki bi imel enako nadzorno vsoto kot original. Ste že kdaj poleg programa, ki ste ga sneli, zasledili tudi kodo MD5 ali SHA-1? To so nadzorne vsote, prek katerih lahko preverite, ali so biti, ki ste jih dobili, dejansko tudi biti, ki bi jih morali dobiti. Če imate ustrezen program za izračun nadzorne vsote, lahko recimo vsoto sami izračunate, nato pa jo primerjate s to, ki je recimo navedena na spletni strani, od koder ste program sneli. Tovrstni programi so večinoma brezplačni in zelo majhni, tako da ne zasedejo veliko prostora.
Moj mikro, junij 2012 | Miha Gradišnik |
