Un document din anul 1948 scris de Claude Shannon (Master of Science în 1937, PhD în 1940), a creat domeniul teoriei informaţiei - şi a stabilit agenda pentru cercetarea în domeniu pentru următorii 50 de ani. Detalii, în cele ce urmează.
Este începutul anilor 1980 şi tu eşti un producător de echipamente pentru noile calculatoare personale de pe piaţă. De ani de zile, modemurile care transmit date prin liniile telefonice au fost blocate la o rată maximă de 9.6 kilobiţi pe secundă: dacă încercaţi să creşteţi rata, un număr intolerabil de erori se strecoară în date.
Apoi, un grup de ingineri au demonstrat că nou dezvoltatele coduri de corecţie a erorilor pot creşte rata de transmisie a unui modem cu 25 la sută. Ai simţit că asta este o oportunitate de afaceri. Există coduri care pot mări viteza de transmisie a datelor chiar şi mai mult? Dacă da, cât de mult? Şi care sunt aceste coduri?
De fapt, la începutul anilor 1980, răspunsurile la primele două întrebări erau deja mai vechi de 30 de ani. Ele au fost furnizate în 1948 de către Claude Shannon într-o lucrare revoluţionară, care a creat, în esenţă, disciplina teoriei informaţiei. "Oamenii care cunosc munca lui Shannon din întregul domeniu al ştiinţei cred că este vorba, pur şi simplu, de una dintre cele mai strălucite realizări pe care le-au văzut vreodată", spune David Forney, profesor la MIT’s Laboratory for Information and Decision Systems.
Shannon, care a predat la MIT din 1956 până la pensionarea sa din 1978, a arătat că orice canal de transmisii de date - o linie telefonică, o bandă radio, un cablu de fibră optică - ar putea fi caracterizat prin doi factori: lăţimea de bandă şi zgomotul. Lăţimea de bandă este gama de frecvenţe electronice, optice sau electromagnetice, care pot fi folosite pentru a transmite un semnal; zgomotul este orice poate perturba semnalul.
Luând în considerare un canal cu anumite caracteristici ale lăţimii de bandă şi ale zgomotului, Shannon a arătat cum să se calculeze rata maximă la care datele pot fi trimise prin canale cu o eroare zero. El a numit acea rată capacitatea canalului, dar astăzi este adesea numită limita Shannon.
Într-un canal afectat de zgomot, singura modalitate de a te apropia de eroare zero este de a adăuga nişte redundanţă la o transmisie. De exemplu, dacă aţi încerca să transmiteți un mesaj cu doar trei biţi, cum ar fi 001, aţi putea să-l trimiteți de trei ori: 001001001. Dacă o eroare se strecoară şi receptorul a primit în schimb 001011001, ar putea fi suficient de sigur că şirul corect a fost 001.
Orice astfel de metodă de adăugare de informaţii suplimentare unui mesaj, astfel încât erorile să poată fi corectate este denumită cod de corecţie a erorilor. Cu cât este mai afectat de zgomot un canal, cu atât mai multe informaţii aveţi nevoie să adăugaţi pentru a compensa erorile. Însă cu cât lungimea codurilor se măreşte, rata de transmisie se micşorează: ai nevoie de mai mulţi biţi pentru a trimite acelaşi mesaj fundamental. Astfel, codul ideal ar reduce numărul de biţi suplimentari, maximizând în acelaşi timp şansa de corectare a erorilor.
După acest standard, trimiterea unui mesaj de trei ori este de fapt un cod groaznic. Acesta reduce rata de transmisie a datelor cu două treimi, deoarece este nevoie de de trei ori mai mulţi biţi pe mesaj, dar este încă foarte vulnerabil la erori: două erori în locurile potrivite ar face mesajul original irecuperabil.
Dar Shannon ştia că era posibilă dezvoltarea unor coduri mai bune pentru corecţia erorilor. De fapt, el a fost în măsură să dovedească faptul că, pentru orice canal de comunicare, trebuie să existe un cod de corecţie a erorilor care permite transmisiei să se apropie de limita Shannon.
Doar că demonstraţia sa nu explică cum anume se poate construi un astfel de cod. În schimb, aceasta are la bază calcule probabilistice. Spuneţi că doriţi să trimiteţi un singur mesaj de patru biţi pe un canal afectat de zgomot. Există 16 mesaje posibile de patru biţi. Demonstraţia lui Shannon ar aloca pentru fiecare dintre ele propriul cod selectat aleator - practic propriul său număr serial.
Luaţi în considerare cazul în care canalul este îndeajuns de afectat de zgomot ca un mesaj de patru biţi să necesite un cod de corecţie de opt biţi. Receptorul, ca şi transmiţătorul, ar avea un dicţionar care corelează cele 16 posibilităţi ale mesajelor de patru biţi cu 16 coduri de opt biţi. Deoarece există 256 de secvenţe posibile de opt biţi, există cel puţin 240 care nu apar în dicţionar. În cazul în care receptorul primeşte una dintre aceste 240 de secvenţe, va şti că o eroare s-a strecurat în date. Dar, din cele 16 coduri permise, e probabil ca doar unul să se potrivească cel mai bine secvenţei primite - care diferă, de exemplu, cu doar un bit.
Shannon a arătat că, statistic, dacă iei în considerare toate asocierile posibile de coduri aleatorii la mesaje, trebuie să existe cel puţin unul care se apropie de limita Shannon. Cu cât un cod este mai mare, cu atât poţi fi mai aproape: codurile de opt biţi pentru mesajele de patru biţi nu te-ar apropia foarte mult, dar codurile de două mii de biţi pentru mesaje de o mie de biţi ar putea.
Desigur, sistemul de codificare Shannon este total nepractic: un dicţionar cu un cod separat, repartizat aleatoriu pentru fiecare mesaj posibil de o mie de biţi nu va putea să încapă nici măcar pe toate hard disc-urile tuturor calculatoarelor din lume. Dar demonstraţia lui Shannon a scos la iveală posibilitatea chinuitoare că, din moment ce trebuie să existe coduri care se apropie de limita Shannon, ar putea exista o modalitate mai eficientă de a le găsi.
Căutarea pentru un astfel de cod a durat până în 1990. Asta numai pentru că cel mai performant cod pe care îl ştim în prezent, şi care a fost inventat la MIT, a fost ignorat pentru mai mult de 30 de ani. Dar despre asta într-un articol viitor.
Articolul reprezintă traducerea articolului Explained: The Shannon limit, publicat pe site-ul web.mit.edu.
Traducere: Anamaria Spătaru