Corectare eroare

Alice și Bob şi-au dat seama de un truc incredibil. Ei schimbă mesaje prin ciupirea unei corzi, ciupire care poate fi dură sau moale, transmiţând astfel zero sau unu. Cu toate acestea, datorită unor rafale de vânt, există semnale de zero și unu false, care pot apărea în timpul transmisiunii, dând astfel naştere unor erori. Totuşi, ei au găsit o cale de a comunica fără erori, chiar și în prezenţa zgomotului. Cum au putut face asta? În anii 1940, Richard Hamming s-a confruntat cu o problemă similară în timp ce lucra la laboratoarele Bell. Richard - la Bell Telephone Laboratories: Am făcut 10% din experimente pe un calculator și aproape 90% în laborator. Mă aștept ca, în timp, să executăm 90% din experimente pe calculator și 10% in laborator. Viteza, costul și efortul recomandă calculatorul faţă de abordarea în laborator. La acel moment, computerele utilizau informații stocate pe cartele perforate care reprezentau unu faţă de zero prin zone de marcaj cu perforații, respectiv fără perforații. Acest sistem era predispus erorii, pentru că se întâmpla adesea ca prima zonă a cartelei să fie sărită sau îndoită. Astfel, perforațiile puteau fi ratate sau se putea întâmpla să nu fie făcută nici o perforație, dând naştere unor deplasări de fragmente. Aceste erori cauzau oprirea întregului sistem, până când eroarea era localizată şi corectată manual. Hamming şi-a asumat sarcina de a crea o metodă care putea în mod automat să detecteze şi să corecteze erori de bit, fără să întrerupă calculele. Soluţia lui se baza pe ideea intuitivă a repetiției, ceva ce facem cu toţii când suntem confruntaţi cu interferenţe sau cu posibilitatea ca o parte din mesajul nostru să fie înţeles greşit. Codurile lui de corectare a greşelilor erau construite pe simplul concept de bit de paritate. Bitul de paritate este un singur bit care se adăugă la sfârşitul unui mesaj și indică dacă numărul de valori 1 dintr-un mesaj este par sau impar. Dacă apare o singură greşeală, receptorul o poate detecta, deoarece paritatea bitului nu se va mai potrivi. Cu toate acestea, pentru a detecta şi corecta erori singulare, Hamming a avut nevoie să adauge mai mulți biți de paritate pentru a identifica locația erorii. Aceasta a dus la codul său 7-4, care adăuga 3 biți de paritate fiecărui bloc de câte 4 biți de informație, după cum urmează. Începem cu cei 3 biți de pariate, care pot fi reprezentați prin câte un cerc. Aceste cercuri se intersectează şi produc 4 regiuni. Cei 4 biți de informație sunt plasați în interiorul acestor regiuni, într-o ordine specifică. Pentru a calcula biții de paritate, ne uităm la fiecare cerc pe rând, fiecare conţinând câte 3 biți de date. Determinăm bitul de paritate ca mai înainte. Adunăm biții de date şi, dacă obţinem 0 sau 2, bitul de paritate este 0 - pentru par, iar dacă obţinem 1 sau 3, bitul de paritate este - pentru impar. Facem la fel pentru toate cercurile și obţinem 3 biți de paritate care să se potrivească cu cei 4 biți de date. Aceștia sunt apoi aranjați într-o secvenţă standard, după cum urmează. Să observăm că sistemul acesta poate corecta automat erori singulare cu o regulă simplă. Dacă apare o singură eroare, doi sau mai mulți biți de paritate vor fi incorecți și acolo unde se intersectează este locația erorii. Acest bit de date de la intersecție este inversat automat, astfel încât toți biții de paritate să fie din nou valizi. Acesta este trucul lui Alice și Bob. Biții de paritate adăugați sunt cunoscuți ca biți redundanți, deoarece ei nu poartă nici o informaţie nouă. Toate codurile de corectare a greşelilor funcţionează în acest fel. Toate măresc uşor sursa mesajelor cu preţul corectării automate a greşelilor. Noi folosim de asemenea coduri de corectare a greşelilor pentru stocare. De exemplu, pe un CD informația este codificată folosind coduri speciale pentru a corecta erori masive cauzate de zgârieturi sau praf, care distrug secvenţe mai lungi de 0 şi 1 stocate pe suprafaţa discului. De aceea este posibil să fi zgâriat un CD și totuși el să funcționeze încă perfect. Claude Shannon a folosit această idee a redundanței pentru a redefini capacitatea unui canal de comunicare, pentru că pe măsură ce zgomotul din canalul vostru creşte, trebuie să creştem și mărimea redundanţei pentru a comunica fără erori. Aceasta trebuie apoi să descrească cantitatea efectivă de informaţie pe care o poţi trimite într-un anumit interval de timp.