Corectarea erorilor

Canalul cu zgomot

Până în acest punct, am presupus că mesajele noastre călătoresc printr-un univers ideal și aseptic: orice caracter expediat de emițător ajungea la destinație curat și neatins. Lumea fizică reală este însă mult mai aspră și mai agitată. Fie că semnalul trece printr-un fir de cupru străbătut de căldură, printr-o rază de lumină într-o fibră optică, prin văzduh ca undă radio sau așteaptă răbdător ani la rând pe suprafața unui disc dur, el este permanent pândit de imperfecțiuni. Lecția de față privește această degradare drept în ochi: nu ca pe un accident regretabil, ci ca pe o lege fundamentală a naturii, care poate fi măsurată, stăpânită și, în cele din urmă, biruită.

Numim canal orice mediu fizic care transportă biți dintr-un punct în altul al spațiului sau dintr-un moment în altul al timpului: un cablu de rețea, un canal Wi-Fi, o celulă minusculă de memorie RAM sau chiar o bucățică de siliciu dintr-un cip. Niciun canal din univers nu funcționează perfect. Din când în când, o fluctuație de tensiune sau o interferență rătăcită face ca un 0 să fie citit ca 1, sau un 1 ca 0.

Cel mai simplu și intuitiv model pentru un astfel de canal imperfect se numește canal binar simetric: ne imaginăm că fiecare bit expediat are, absolut independent de vecinii săi, o mică probabilitate p de a fi răsturnat pe drum. Această probabilitate poartă numele de rată de eroare. În mod obișnuit, ea este mică — de pildă un procent (1%) —, dar mesajele din viața digitală conțin milioane sau miliarde de biți, astfel că micile greșeli se adună inevitabil. La o rată de un procent, un text modest de o mie de biți va sosi la destinație cu vreo zece biți stricați, destul pentru a transforma cuvintele într-un talmeș-balmeș greu de recunoscut.

În exemplul interactiv de mai sus, fiecare caracter este codificat pe 5 biți dintr-un alfabet de 32 de semne (literele uzuale, literele românești cu diacritice și spațiul). Orice răsturnare a unui bit transformă caracterul inițial într-o altă literă validă din alfabet, astfel încât efectul zgomotului se poate citi cu ochiul liber în textul primit.

Detectarea unei erori

Care este cel mai simplu și mai ieftin truc prin care putem afla dacă un mesaj s-a stricat pe drum? Răspunsul este adăugarea unui singur bit de veghe la capătul mesajului, numit bit de paritate. Valoarea lui este aleasă astfel încât numărul total de cifre 1 din întregul grup să fie întotdeauna un număr par. Acest bit suplimentar nu adaugă nicio noutate despre conținut; el funcționează ca o garanție matematică, ca un sigiliu de ceară aplicat pe scrisoare.

Dacă un singur bit este lovit de zgomot și își schimbă valoarea pe traseu, numărul total de cifre 1 devine impar. Destinatarul numără biții de 1, observă neregula și trage imediat alarma: ceva s-a stricat! Totuși, acest mecanism simplu are două mari limite: în primul rând, ne spune că există o eroare, dar nu ne poate spune unde se află ea (toate pozițiile rămân la fel de suspecte); în al doilea rând, dacă zgomotul lovește nefericit doi biți deodată, numărul cifrelor 1 redevine par, iar eroarea dublă se strecoară complet neobservată. Bitul de paritate este așadar un paznic modest: detectează doar numărul impar de greșeli și nu poate repara nimic de la sine.

Distanța dintre cuvinte

Pentru a trece de la simpla detectare la repararea automată a greșelilor, avem nevoie de o viziune geometrică intuitivă. Dintre toate combinațiile teoretice de biți care se pot scrie, noi vom conveni să declarăm valide doar o mică parte dintre ele. Un astfel de șir autorizat se numește cuvânt de cod. Toate celelalte combinații sunt considerate ilegale și nu ar trebui să apară niciodată într-o transmisie normală. Dacă destinatarul primește o combinație ilegală, el știe că a intervenit o eroare; iar dacă cuvintele valide au fost așezate suficient de departe unele de altele, el poate ghici fără greș de unde a plecat mesajul!

Cât de „depărtate” sunt două șiruri de biți? Numărul de poziții în care două secvențe diferă între ele se numește distanță Hamming. O singură eroare pe fir deplasează cuvântul primit la distanța 1 față de original; două erori îl împing la distanța 2, și așa mai departe.

Gândiți-vă la cuvintele valide ca la niște insule într-un ocean de biți. Dacă oricare două insule se află la o distanță de cel puțin 3 pași una de alta, atunci o barcă deviată de o singură greșeală (1 pas) va rămâne mult mai aproape de insula de unde a plecat decât de oricare alta! Destinatarul nu are altceva de făcut decât să aleagă cea mai apropiată insulă validă și va nimeri exact mesajul original. Această distanță minimă d dintre cuvintele unui cod dictează întreaga sa putere protectoare: putem detecta întotdeauna d−1 erori și putem repara complet jumătate din acest număr.

Cea mai naivă și directă metodă de a obține o distanță de 3 pași este repetiția triplă: în loc de un singur bit, trimitem fiecare bit de trei ori (0 devine 000, iar 1 devine 111). Dacă pe drum un bit se răstoarnă și primim 101, facem un vot democratic simplu: avem doi de 1 și un singur 0, deci decidem că mesajul a fost 1! Corectarea prin vot rezolvă admirabil orice eroare izolată.

Prețul plătit pentru repetiție este însă uriaș: adăugăm doi biți de pază pentru fiecare bit util, ceea ce triplează lungimea întregului mesaj și congestionează rețeaua. Întrebarea genială pe care și-au pus-o inginerii a fost: oare nu putem construi o plasă de siguranță la fel de puternică, dar cu mult mai puțini biți de prisos?

Codul Hamming

Răspunsul a venit în anul 1950 de la matematicianul Richard Hamming de la laboratoarele Bell. El a demonstrat că într-un pachet de 7 biți putem transporta 4 biți de date utile protejați impecabil de doar 3 biți de verificare. În loc să repete mecanic biții de mesaj, Hamming a împletit verificările într-un mod sclipitor: fiecare dintre cei trei biți de control supraveghează un grup diferit de poziții, astfel încât combinația celor trei rezultate de control (0 sau 1), citită ca un număr binar, indică direct numărul de ordine al bitului stricat!

Cum lucrează această magie? Prima verificare supraveghează pozițiile a căror scriere binară se termină cu 1 (pozițiile 1, 3, 5, 7); a doua verificare supraveghează pozițiile care au 1 pe a doua poziție binară (pozițiile 2, 3, 6, 7); iar a treia verificare privește pozițiile care au 1 pe al treilea rang (pozițiile 4, 5, 6, 7). Dacă o poziție oarecare — să zicem poziția 5 — este avariată de zgomot, ea va declanșa alarma exact în prima și în a treia verificare (fiindcă 5 se scrie în binar 101). Citind cele trei alarme ca un număr, obținem chiar 101, adică 5! Am arătat cu degetul spre vinovat și îl putem inversa pe loc la starea corectă. Recunoașteți aici jocul de întrebări din prima noastră lecție: trei întrebări binare de tip da/nu disting perfect între cele opt situații posibile (starea „fără erori” plus cele șapte poziții potențial defecte).

Economia este spectaculoasă: nu mai adăugăm opt biți de pază la patru biți utili (cum cerea codul de repetiție), ci doar trei biți de verificare pentru patru biți de mesaj! Dacă însă pe fir se produc două erori simultane, verificările se păcălesc reciproc și indică o a treia poziție, inocentă, iar corecția automată va strica încă un bit. Codul Hamming clasic este proiectat să corecteze garantat o singură eroare, dar principiul său deschide poarta către coduri moderne capabile să repare sute de erori simultane.

Redundanță scoasă și redundanță pusă

Privite una lângă alta, ultimele două lecții par să se contrazică: în lecția a doua am muncit din greu să curățăm redundanța dintr-un mesaj pentru a-l face cât mai scurt și mai suplu, iar acum, în lecția a treia, adăugăm de bunăvoie biți suplimentari pentru a lungi mesajul la loc! Este oare un pas înainte și unul înapoi? Nicidecum. Secretul constă în calitatea și structura redundanței folosite.

Redundanța naturală a unei limbi este haotică și ineficientă: ea există doar pentru că anumite litere se întâmplă să apară des, fără a urmări un plan de protecție. Ea ne poate ajuta uneori să ghicim o literă ștearsă, dar nu ne poate indica cu precizie matematică unde s-a produs greșeala și nici nu ne garantează că o putem repara. În schimb, redundanța adăugată de un cod corector este o capodoperă inginerească: fiecare bit adăugat are o misiune precisă, răspunde la o întrebare specifică și cooperează cu ceilalți pentru a localiza eroarea.

De aceea, ordinea operațiunilor într-un calculator este sacră: mai întâi comprimăm datele pentru a elimina toată risipa inutilă și balastul haotic, iar abia apoi le protejăm adăugând o armură fină de redundanță controlată. Un fișier comprimat inteligent și apoi protejat printr-un cod corector este deopotrivă mai suplu și incomparabil mai rezistent la intemperii decât fișierul brut original. Cele două lecții nu se bat cap în cap; ele reprezintă cele două brațe ale aceleiași discipline nobile: arta de a decide ce merită plătit dintr-un mesaj.

Capacitatea canalului

Rămâne o ultimă și măreață întrebare: cât de departe putem împinge această eficiență? Fiecare bit dedicat verificării este un bit care nu transportă mesaj propriu-zis. Se naște astfel un raport esențial, numit rata codului: raportul dintre numărul de biți utili și numărul total de biți transmiși pe fir. Codul cu repetiție triplă are o rată modestă de 1/3 (doar 33% e mesaj util), în timp ce codul Hamming atinge 4/7 (peste 57%). Putem oare să transmitem mesaje aproape 100% utile și totuși să fim pe deplin ocrotiți de zgomot?

Răspunsul oferit de Claude Shannon în 1948 a uimit întreaga comunitate științifică mondială. El a demonstrat că fiecare canal de comunicație posedă o barieră precisă numită capacitate. Dacă rata noastră de transmisie este sub această capacitate, există întotdeauna coduri matematice care pot garanta o transmisie practic fără nicio eroare, oricât de lung ar fi mesajul! În schimb, dacă încercăm să transmitem peste capacitatea canalului, nicio minte omenească nu poate scăpa de erori. Zgomotul fizic nu ne cere un sacrificiu infinit; el impune o taxă fixă și măsurabilă, egală cu entropia erorii.

Priviți graficul interactiv: capacitatea scade treptat până când atinge zero la o rată de eroare de 50%. De ce tocmai la 50%? Pentru că atunci când fiecare bit are șanse egale de a fi corect sau inversat, canalul devine o simplă monedă aruncată în aer: ieșirea nu mai are nicio legătură cu intrarea, iar informația s-a evaporat complet. Dacă rata depășește 50%, capacitatea începe curios să crească din nou: un fir care inversează aproape totul este de fapt un canal excelent, căruia trebuie doar să-i inversăm convenția la celălalt capăt!

Teorema lui Shannon a demonstrat că aceste coduri ideale există în mod cert, dar fără a lăsa o rețetă mecanică pentru construirea lor. Oamenii de știință au trudit mai bine de jumătate de secol pentru a le proiecta, iar codurile moderne care echipează astăzi telefoanele 5G, transmisiunile sondelor spațiale de la marginea sistemului solar și hard-discurile din centrele de date ating 99% din această limită teoretică supremă.