Codurile corectoare de erori explicate
Niciun canal nu este perfect. Razele cosmice inversează biți în memorie, zgârieturile șterg părți ale unui disc, iar semnalele radio slăbesc. În loc să spere la ce e mai bun, sistemele digitale adaugă redundanță într-un mod ingenios, astfel încât receptorul să poată deduce ce s-a trimis chiar și atunci când o parte ajunge greșit. Matematica acestor coduri, începută la sfârșitul anilor 1940, protejează discret aproape fiecare bit pe care îl stocăm sau îl trimitem.
Detectarea erorilor prin paritate
Cea mai simplă protecție este un singur bit de paritate: adăugați un 1 sau un 0 astfel încât numărul total de cifre 1 să fie par. Dacă un bit se inversează pe drum, numărul devine impar, iar receptorul știe că ceva nu a mers bine. Paritatea nu poate spune care bit este greșit, iar două inversări se anulează reciproc fără să fie observate, dar este ieftină și a fost folosită zeci de ani în memorii și în legături seriale. Detectarea unei erori este însă doar jumătate din treabă: apoi datele trebuie trimise din nou.
Corectarea prin repetiție
Pentru a corecta o eroare fără să mai ceară o dată, receptorul are nevoie de suficientă redundanță ca s-o învingă la vot. Trimiterea fiecărui bit de trei ori, 000 sau 111, îi permite receptorului să aleagă majoritatea: o inversare într-un triplet este corectată. Prețul este mare: trei biți pentru fiecare bit de date, iar două inversări în același triplet tot câștigă. Întrebarea care a pornit teoria codurilor a fost dacă se poate mai bine.
Codul lui Hamming
În 1947, Richard Hamming lucra la Bell Labs la un calculator cu relee care citea programe de pe cartele perforate. Când găsea o eroare în weekend, pur și simplu se oprea, iar Hamming se întorcea luni la rulări irosite. Dacă o mașină poate detecta o eroare, s-a întrebat el, de ce n-ar putea s-o localizeze și s-o corecteze? Răspunsul său, publicat în 1950, trimite 4 biți de date ca 7. Trei biți de paritate, pe pozițiile 1, 2 și 4, verifică fiecare un alt grup suprapus de poziții, ales astfel încât fiecare eroare simplă să strice o combinație unică de verificări.
Sindromul
Receptorul recalculează cele trei verificări. Dacă toate trec, cuvântul este acceptat. Dacă unele eșuează, scrierea verificărilor eșuate ca cifre binare, cu verificarea 4 drept cifra cea mai semnificativă, dă un număr de la 1 la 7: sindromul, care este exact poziția bitului inversat. Inversarea lui înapoi restabilește cuvântul de cod. Trucul funcționează pentru că pozițiile sunt numerotate astfel încât scrierea binară a fiecăreia enumeră verificările din care face parte, și de aceea codul arată atât de ordonat când este desenat ca trei cercuri suprapuse.
Distanța Hamming
Distanța Hamming dintre două cuvinte este numărul de poziții în care ele diferă. În codul (7,4), oricare două cuvinte de cod se află la o distanță de cel puțin 3. Un cuvânt cu o eroare se află încă la distanța 1 de cuvântul de cod trimis și la cel puțin 2 de oricare altul, așa că decodarea la cel mai apropiat cuvânt de cod îl corectează. În general, un cod ale cărui cuvinte de cod se află la o distanță de cel puțin d unul de altul detectează d − 1 erori și corectează (d − 1)/2 dintre ele, rotunjit în jos. Adăugarea unui bit de paritate pentru întregul cuvânt ridică distanța la 4, rezultând codul extins care corectează o eroare și detectează două.
Limita lui Shannon
În 1948, cu doi ani înaintea articolului lui Hamming, Claude Shannon a demonstrat o teoremă uimitoare. Fiecare canal cu zgomot are o capacitate, iar datele pot fi trimise cu orice rată sub ea, cu oricât de puține erori doriți, folosind coduri suficient de lungi; peste ea, erorile nu pot fi evitate. Shannon a arătat că astfel de coduri există, dar nu și cum se construiesc. Găsirea unor coduri practice care să se apropie de limita sa a durat o jumătate de secol, de la codurile Reed-Solomon din 1960 la codurile turbo din 1993 și la redescoperirea codurilor LDPC (low-density parity-check).
Coduri peste tot în jurul nostru
Codurile Reed-Solomon permit CD-urilor să cânte în ciuda zgârieturilor și codurilor QR să fie scanate chiar cu până la 30% din simbol deteriorat. Memoria serverelor folosește coduri Hamming extinse pentru a repara biții izolați inversați de razele cosmice. Imaginile planetelor exterioare trimise de Voyager au fost protejate de coduri Golay și apoi de coduri Reed-Solomon, iar codurile LDPC și polare din 5G și Wi-Fi stoarc aproape fiecare bit pe care îl permite canalul. Chiar și codul de bare de pe o carte și ultima cifră a unui număr de cont bancar sunt coduri simple de detectare a erorilor.
Explorați
Deschideți simulatorul de coduri corectoare de erori pentru a codifica oricare patru biți de date cu codul Hamming (7,4), a inversa biți făcând clic pe ei în cercuri sau în rând și a urmări cum cercurile care eșuează și sindromul indică eroarea înainte ca decodorul s-o repare. Activați bitul de paritate suplimentar ca să vedeți cum sunt detectate erorile duble și trimiteți un mesaj printr-un canal cu zgomot pentru a compara ce ajunge cu și fără cod.
Întrebări frecvente
Care este diferența dintre detectarea și corectarea erorilor?
Detectarea îi spune receptorului doar că ceva nu este în regulă, așa că acesta trebuie să ceară din nou datele; asta face un bit de paritate sau o sumă de control. Corectarea îi permite receptorului să reconstituie originalul fără să ceară, ceea ce necesită mai multă redundanță. Sistemele care nu pot cere din nou, precum o sondă spațială aflată la milioane de kilometri sau un DVD, se bazează pe corectare.
De ce să nu trimitem pur și simplu totul de două ori?
Două copii arată că s-a produs o eroare, dar nu și care copie este corectă, și dublează costul. Trei copii permit un vot majoritar, dar îl triplează. Codul lui Hamming corectează o eroare simplă pe bloc de șapte biți cu mai puțin decât dublul biților, iar codurile mai lungi se descurcă mult mai bine.
Cine a fost Richard Hamming?
Un matematician american, 1915–1998, care a lucrat la Proiectul Manhattan și apoi timp de treizeci de ani la Bell Labs. Pe lângă codurile sale, este cunoscut pentru fereastra Hamming din prelucrarea semnalelor, pentru distanța Hamming și pentru prelegerea sa „You and Your Research”. A primit Premiul Turing în 1968.
Poate un cod să corecteze oricâte erori?
Numai cu suficientă redundanță. Un cod poate corecta până la (d − 1)/2 erori pe bloc, unde d este distanța minimă dintre cuvintele de cod, iar codurile mai lungi, cu mai mulți biți de control, ating un d mai mare. Teorema lui Shannon stabilește limita supremă: niciun cod nu poate depăși capacitatea canalului.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Deschideți simulatorul de coduri corectoare de erori