Kako računalniki sami popravljajo napake

Ko je matematik Richard Hamming kmalu po drugi svetovni vojni v Bellovih laboratorijih skrbel za enega od prvih računalnikov, se je moral spopadati s težavami, kakršnih danes skorajda 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 skorajda v trenutku in praviloma brez kakršnihkoli zapletov, a v pionirski dobi računalništva so bila tudi tovrstna opravila kar zahtevne operacije.

Algoritmi za odkrivanje in odstranjevanje napak

Do težav je prihajalo predvsem zato, ker se je računalnik pri branju podatkov pogosto zmotil, s čimer je povzročil hude zaplete in raziskovalce spravljal ob živce. Že če je prišlo do ene same napake pri branju algoritma, so bili lahko vsi izračuni neuporabni, zelo verjetno pa se je tudi sam računalnik med izvajanjem programa prenehal pravilno odzivati, zato ga je bilo treba ponovno zagnati.

Shranjevanje in prenašanje informacij sta (ob računanju oziroma izvajanju algoritmov) že od vsega začetka osrednji opravili, ki ju izvajajo računalniki. Pri prenosu in hrambi elektronskih informacij pa je potrebna posebna natančnost, saj morajo biti podatki povsem točni in ne le natančni, denimo z verjetnostjo 99,99999 odstotka, sicer se hitro pojavijo težave. Kako doseči absolutno točnost, je bilo za prve uporabnike računalnikov kmalu po drugi svetovni vojni izjemno pomembno vprašanje, ki so ga morali hitro razrešiti.

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

Kako lahko vemo, da v podatkih ni napake?

Najbolj preprosta ideja, kako preprečiti, da bi prišlo do napak pri shranjevanju ali prenosu informacij, je, da podatke preprosto shranimo v več enakih kopijah. Za povečanje zanesljivosti prenosa informacij je treba namreč naslovniku poslati več kot le eno samo verzijo podatkov. Vendar se je takšen najbolj preprost 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 pri telefonskem pogovoru nam, tudi če močno šumi in prekinja, ponavadi uspe nekako prenesti informacijo. Praviloma je skrivnost prenosa informacije preko linije z veliko šuma v tem, da za razumevanje ni ključen vsak posamezen glas. Tudi če se vmes kaj izgubi, informacija kljub temu pride na drugo stran.

Lep primer trika, ki nazorno opiše tovrsten način prenosa informacije, je zapis števil z besedami. Če želimo s pomočjo zapisa na papirju nekomu poslati denimo število 36172 in nas skrbi, da se bodo vmes posamezni deli zapisa izbrisali ali spremenili, bo bistveno 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. Ker smo številsko informacijo zapisali z besedami, je zelo velika verjetnost, da bo prišla do naslovnika v pravi obliki, tudi če bo vmes deležna določenega popačenja.

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. Hamming je razvil kodo v računalniškemu dvojiškem zapisu z enicami in ničlami, s katero je lahko računalnik kar sam ugotovil, ali je prišlo pri prenosu do napake, in napako tudi avtomatično popravil. Vendar se je znala ta najbolj preprosta metoda učinkovito spopasti le z eno samo napako pri posameznem simbolu. Če je slučajno prišlo do več sočasnih napak, so ponovno nastopile 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 morda spremenila. Če posumimo, da je pri prenosu prišlo do napake, preprosto prosimo za novo kopijo. To je tudi način preverjanja, ki ga uporablja večina internetnih povezav.

Najbolj preprosta tovrstna metoda, ki zna preveriti, ali preneseni podatki niso popačeni, je metoda preverjanja vsote (checksum). Gre preprosto za to, da preneseni kos informacije, ki je praviloma zakodiran v obliki števil, 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 tovrstni 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 vnovičen prenos istega zaporedja.

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

Rojstvo informacijskih znanosti

Algoritmi za preverjanje napak so samo del bistveno obsežnejše vede, ki ji pravimo informacijska teorija. Običajno štejemo za rojstvo informacijskih znanosti članek z naslovom Matematična teorija komunikacij, ki ga je leta 1948 objavil Claude Shannon. Zanimivo je, da sta si Shannon in Hamming v Bellovih laboratorijih prav takrat kratek čas celo delila pisarno, poznala pa sta se še iz medvojnih let, ko sta oba sodelovala pri projektu Manhattan, v okviru katerega so izdelali prvo jedrsko bombo.

Shannon je v svojem prelomnem članku, ki so ga poimenovali kar “Magna Charta informacijske dobe”, postavil teoretske temelje informacijske znanosti. V njem je med drugim pokazal, da lahko tudi preko komunikacijskega kanala z veliko motnjami dosežemo razmeroma dober prenos podatkov. Izpeljal je tudi enačbe, s katerimi je izračunal največje možne hitrosti prenosa informacij preko nezanesljive povezave.

Brez metod, ki omogočajo zanesljivo hrambo in prenos podatkov, danes gotovo ne bi živeli v informacijski dobi, ko se že skorajda vsi pomembni podatki za delovanje družbe hranijo zgolj v elektronski obliki. CD-ji, DVD-ji, računalniški diski in drugi nosilci informacij, ki jih danes množično uporabljamo, temeljijo na zelo izpopolnjenih algoritmih, ki znajo sami odkrivati in popravljati napake. Podobno velja tudi za internet, saj tega danes osrednjega medija za prenašanje informacij ne bi bilo, če ne bi razvili zelo zanesljivih algoritmov, ki nam zagotavljajo, da se informacije pri prenosu preko interneta ne bodo prav nič spremenile.

-
Podpri Kvarkadabro!
Naroči se
Obveščaj me
guest

0 - št. komentarjev
Inline Feedbacks
View all comments