Acest articol reprezintă partea a doua a unei mini-serii de 2 articole referitoare la teoria informaţiei. Dacă în prima parte au fost prezentate informaţii referitoare la limita Shannon, în prezentul articol vor fi explicate unele noţiuni despre codurile Gallager.
În 1993, cercetării au atins rata maximă de transfer a datelor, doar pentru a descoperi că au fost întrecuţi cu 30 de ani mai devreme de către un absolvent al MIT.
În articolul publicat în 1948 de Claude Shannon, tânărul absolvent al MIT (şi viitor profesor) a creat domeniul teoriei informaţiei, stabilind ţelul pentru următoarele generaţii de cercetători. În acele zile „pre-digitale”, canalele de comunicaţii (de exemplu liniile de telefon sau benzile radio) erau susceptibile, în mod particular, la distorsiuni electrice sau electromagnetice, denumite „zgomot”. Shannon a dovedit contrariul, demonstrând că informaţia poate fi transmisă fără erori pe un canal, indiferent cât de mult zgomot există. Tot ce era necesar era o modalitate de a adăuga destulă redundanţă la informaţie astfel încât erorile să poată fi corectate. Totodată, el a mai demonstrat că exista o limită a eficienţei pe care o puteau avea aceste coduri corectoare de erori (o cantitate minimă de informaţii suplimentare care ar garanta valori ale erorilor aproape zero). Din moment ce codurile mai lungi au nevoie de mai mult timp pentru a fi transmise, o lungime minimă a codului implică o rată maximă de transfer, denumită limita lui Shannon. În final, Shannon a dovedit că anumite coduri care se aproprie de acea limită trebuie să existe. Însă nu a arătat şi cum pot fi găsite.
În următorii 45 de ani, cercetătorii au căutat acele coduri. Pe parcursul acestei perioade au avut loc descoperiri care au ajutat la mărirea vitezei de transmisie a modemurilor de la 9.6 kilobiţi pe secundă la 14.4 kilobiţi pe secundă, la începutul anilor 1980. Însă conform lui Muriel Médard, profesor de ştiinţa calculatoarelor (informatică) şi inginerie electrică la MIT, codurile propuse au avut tendinţa de a se opri la aşa-numita rată maximă de suportabilitate a mecanismului de calcul („computational cutoff rate”). Această rată varia în funcţie de puterea transmisiei şi de caracteristicile zgomotului prezent pe acel canal, însă în cazul sistemelor practice de comunicaţii, ar putea fi doar jumătate din valoarea limitei Shannon.
Apoi, în 1993, la Conferinţa Internaţională de Comunicaţii, desfăşurată la Institutul de Inginerie Electrică şi Electronică, Alain Glavieux şi Claude Berrou, de la şcoala Naţională Superioară de Telecomunicaţii, din Bretania, au prezentat un set nou de coduri care erau foarte aproape de limita Shannon, după cum susţineau ei. „Cei prezenţi au râs de ei până ce au părăsit sala”, spune Médard, „în special pentru că nu erau programatori; erau electronişti”. Cercetătorii îşi dezvoltaseră codurile (supranumite „coduri turbo”) mai ales prin încercări şi rezolvări ale problemelor apărute, şi nu aveau nici o explicaţie formală, elegantă, de ce acestea funcţionau atât de bine. Cu toate acestea, investigaţii ulterioare au confirmat rapid rezultatele acestora.
Codurile turbo sunt aşa-numitele coduri iterative, care înseamnă că decodificatorul face o serie de presupuneri despre care ar trebui să fie mesajul codificat. Fiecare presupunere succesivă este reintrodusă în decodificator, astfel încât rezultatul următor este o presupunere mai precisă. În mod ideal, repetând acest proces de mai multe ori, se va reduce rata de erori până la nivelul acceptat.
Performanţele surprinzătoare ale codurilor turbo au mobilizat cercetătorii să încerce a explica care este cauza funcţionării uimitoare a codurilor. În câţiva ani, investigaţiile asupra schemelor de codificări iterative au indicat un rezultat, posibil şi mai surprinzător: un set de coduri care funcţionau la fel de bine precum codurile turbo existau încă din 1960, când au fost introduse, pentru prima dată, în teza de doctorat a lui Robert Gallager, teză prezentată la MIT.
Revoluţia tăcută
Puterea codurilor lui Gallager a trecut neobservată pentru o perioadă atât de îndelungată, deoarece procesul de decodificare pe care acesta îl propunea era pur şi simplu prea complex pentru tehnologia anilor 1960. Acest lucru este ironic, din moment ce motivul creării acestor coduri a fost tocmai simplificarea procesului de decodificare. „ Dificultatea întregului sistem era, 'Cum să proiectezi un algoritm de decodificare bun?' ”, spune Gallager, care a predat la MIT între anii 1960 şi 2001, şi care încă supervizează studenţii din anii terminali, ca profesor emerit. „Apoi, după ce ai găsit ideea cum să realizezi acest lucru, cum generezi codurile care vor fi decodificate în asemenea manieră?”. Totuşi, la acel timp, cercetarea în scopul găsirii unor noi scheme de codificare depindea de afirmaţiile statistice referitoare la performanţa decodificatoarelor ideale ipotetice. Pentru cercetători precum Gallager, care încercau să creeze coduri care să se apropie de limita Shannon, specificarea unui algoritm de decodificare concret era deja un pas neobişnuit în direcţia testărilor practice.
Codurile lui Gallager folosesc aşa-numiţii biţi de paritate, adică biţi care conţin informaţii despre biţii din mesajul propriu-zis. Un bit de paritate poate indica, de exemplu, dacă suma biţilor 1, 2 şi 4 ai mesajului este un număr par sau impar; următorul bit de paritate poate face acelaşi lucru pentru biţii 3, 4 şi 6 ai mesajului; şi aşa mai departe, prin intermediul unor triplete de biţi. Informaţia fiabilă despre oricare 2 biţi dintr-un triplet, furnizează date fiabile despre al treilea bit. „Metodele iterative presupun crearea unei prime asumpţii despre înţelesul primului bit recepţionat şi acordarea acestuia a unei ponderi în funcţie de cât de fiabil a fost”, spune David Forney, profesor adjunct în Laboratorul de Sisteme Informaţionale şi Decizionale, din MIT. „Apoi, poate se vor avea mai multe informaţii despre el, datorită participării acestuia la verificări de paritate împreună cu alţi biţi, astfel obţinându-se o estimare îmbunătăţită a fiabilităţii sale (care poate fi de aceeaşi natură sau se poate modifica), iar prin intermediul unor serii de asemenea calcule, se va spera ca el să conveargă spre punctul în care toţi biţii sunt consideraţi fiabili”. Problemele apar, declară Forney, „dacă se va începe o confuzie prin reintroducerea unor asumpţii deja utilizate, în aceleaşi calcule, astfel că se obţine o creştere a rezultatelor pozitive false la nivelul fiabilităţii. Este asemeni unei „fabrici” de zvonuri. Dacă se va auzi mereu acelaşi zvon de la aceleaşi persoane, toţi vom începe să credem că este adevărat, când de fapt este doar un circuit închis”. „Artificiul proiectării codurilor lui Gallager”, spune Forney, „a fost minimizarea probabilităţii de apariţie a unor asemenea circuite închise”. „Va dura o perioadă îndelungată pentru ca lanţul telefonic să străbată globul înainte de a primi un răspuns”, adaugă el.
Până în prezent, codurile lui Gallager au permis realizarea sistemelor cele mai apropiate de limita Shannon pentru un canal de comunicaţii specificat (sisteme cu performanţe mai bune chiar decât cele cu coduri turbo). Acestea au integrate în standarde pentru transmisii de date pe canale fără fir, iar microprocesoare dedicate codurilor de decodificare ale lui Gallager pot fi găsite în telefoanele mobile comerciale. Oare Gallager a avut vreo suspiciune, în timpul eclipsei de faimă a codurilor sale, despre cât de bune sunt acestea?
„Am avut unele mici suspiciuni că ar fi bune, însă am avut, de asemenea, şi unele suspiciuni că nu ar fi”, spune Gallager. „Şi am petrecut mult timp încercând să dezleg această dilemă”. Concluzia sa este echivocă: „Ceea ce am arătat este că folosind diferite clase ale acestor coduri, se pot atinge rate pozitive de transmisie. Pe măsură ce se va modifica clasa, făcând-o mai complicată, rata va continua să se mărească. Dacă se va face o clasă suficient de complicată, se poate atinge capacitatea maximă a canalului, însă este posibil ca acel mesaj să nu mai poată fi decodificat. De atunci, cercetătorii au descoperit metode de a liniariza modalitatea de alegere a codurilor pentru a le îmbunătăţi”.
Articolul reprezintă traducerea articolului Explained: Gallager codes, publicat pe site-ul web.mit.edu.
Traducere: Arseni Ştefan Ciprian
