Ko podavimo vse, ki nas poznajo

Ko je matematik Richard Hamming kmalu po drugi svetovni vojni v Bellovih laboratorijih skrbel za enega prvih računalnikov, se je moral spopadati s težavami, kakršnih danes ne poznamo več. Ker je isti računalnik uporabljalo več raziskovalcev, je moral vsakič, ko je hotel nadaljevati delo na svojem projektu, v računalnik ponovno vnesti program in podatke, ki jih je s programom obdeloval.

Danes se vse to zgodi skoraj v trenutku in praviloma brez zapletov, a v pionirski dobi računalništva so bila tudi taka opravila zahtevne operacije. Težave so nastajale predvsem zato, ker je računalnik podatke pogosto prebral narobe, s čimer je povzročil hude zaplete in raziskovalce spravljal ob živce. Že če je pri branju algoritma nastala ena sama napaka, so lahko bili vsi izračuni neuporabni, zelo verjetno pa se je tudi sam računalnik med izvajanjem programa nehal pravilno odzivati, zato ga je bilo treba ponovno zagnati.

Hamming je tako leta 1947, da bi se vsaj delno izognil težavam pri branju podatkov, iznašel algoritem, ki je znal sam v omejenem obsegu odkrivati in odpravljati napake. Svojo iznajdbo je sicer objavil šele nekaj let pozneje, a zanesljivost prenosa informacij je z njo precej popravil in sprožil celo nove izboljšave, zato računalnikom danes lahko povsem zaupamo, da bodo, denimo, po spletu poslani podatki prišli do naslovnika nespremenjeni, tudi če bodo na poti naleteli na motnje.
 

Kako vemo, da v podatkih ni napake?

Najpreprostejša ideja, kako preprečiti, da bi nastale napake pri shranjevanju ali prenosu informacij, je, da podatke preprosto shranimo v več enakih kopijah. Za povečanje zanesljivosti prenosa informacij je treba naslovniku namreč poslati več kot le eno samo različico podatkov. Vendar se je takšen najpreprostejši pristop hitro izkazal za zelo nepraktičnega in nezanesljivega, zato so morali prvi uporabniki računalnikov najti nove načine, kako povečati zanesljivost prenosa informacij. Kot se pogosto zgodi v takšnih primerih, se je kot dober vir idej izkazala kar vsakdanja uporaba jezika, s katerim poteka prenos informacij med ljudmi, recimo po telefonu.

Tudi računalniki se morajo, podobno kot telefoni, spopadati s šumom in najrazličnejšimi popačenji na liniji. A v telefonskem pogovoru nam, tudi če močno šumi in prekinja, ponavadi uspe prenesti informacijo. Praviloma je skrivnost prenosa informacije po liniji z veliko šuma v tem, da za razumevanje ni ključen vsak posamezen glas. Tudi če se vmes kaj izgubi, informacija pride na drugo stran.

Lep primer trika, ki nazorno opiše tak način prenosa informacije, je zapis števil z besedami. Če želimo z zapisom na papirju nekomu poslati denimo število 36172 in nas skrbi, da se bodo vmes posamezni deli zapisa izbrisali ali spremenili, bo precej večja verjetnost, da bo naslovnik dobil v roke pravo število, če bomo številke zapisali z besedami: tri šest ena sedem dva. V tem primeru bo tudi iz popačenega prenosa, recimo, »fri šst ema sedim dva« znal ugotoviti, da gre za število 36172.

Hamming je leta 1947 posebej za digitalne računalnike iznašel način zapisa informacij, ki je temeljil na povsem enakem pristopu, kot smo ga uporabili v primeru zapisa besed za posamezne številke. Razvil je kodo v računalniškemu dvojiškem zapisu z enicami in ničlami, s katero je računalnik lahko kar sam ugotovil, ali je pri prenosu nastala napaka, in napako tudi avtomatično popravil. Vendar se je znala ta najpreprostejša metoda učinkovito spopasti z le eno samo napako pri posameznem simbolu. Če je naključno nastalo več sočasnih napak, so spet bile težave.
 

Dovolj je že opozorilo

Poleg algoritmov, ki znajo sami odkrivati in popravljati napake, so zelo pomembne tudi metode, ki nam povedo le, ali se je informacija pri prenosu spremenila. Če posumimo, da je pri prenosu nastala napaka, preprosto prosimo za novo kopijo. To je tudi način preverjanja, ki ga uporablja večina spletnih povezav.

Najpreprostejša tovrstna metoda, ki zna preveriti, ali preneseni podatki niso popačeni, je metoda preverjanja vsote (ang. checksum). Gre preprosto za to, da preneseni kos informacije, ki je navadno zakodiran kot število, seštejemo in zraven pripišemo še vsoto vseh števil, ki jih prenašamo. V praksi se izkaže, da je dovolj že, če zapišemo zgolj zadnjo decimalko vsote.



Prej omenjene številke števila 36172 preprosto seštejemo, ugotovimo, da je njihova vsota 19, in zraven zapišemo zadnjo decimalko vsote, kar pomeni, da naslovniku pošljemo zaporedje 361729. Prejemnik informacije mora v tem primeru vedeti, da uporabljamo tak protokol preverjanja. Tako bo brez težav ugotovil, da je nekaj narobe, če bo prejel recimo zaporedje 361129. Vsota številk brez zadnje, ki služi za odkrivanje napak, je v tem primeru 13, kar pomeni, da bi morala biti zadnja kontrolna številka 3, če bi bil prenos izveden brez napak. V praksi protokol tako informacijo avtomatično zavrže in zahteva ponoven prenos istega zaporedja.

Vendar pa tudi metoda preverjanja vsote ni popolnoma zanesljiva, saj v sporočilu lahko nastane več napak, ki se medsebojno izničijo oziroma je vsota spremenjenih števil enaka kot pri izvornem sporočilu. Zato so metode preverjanja sčasoma nadgradili, tako da izvedejo na številih več različnih operacij in ne izračunajo samo njihove vsote, s čimer lahko zaznajo veliko več napak.

****
Sašo Dolenc je urednik Kvarkadabre, spletnega časopisa za popularizacijo znanosti.