In teoria informatiei si teoria codificarii cu aplicatii in informatica si telecomunicatii, detectarea si corectarea erorilor sau controlul erorilor sunt tehnici care permit livrarea fiabila a datelor digitale pe canale de comunicatie nesigure.
Multe canale de comunicatie sunt supuse zgomotului canalului si astfel pot fi introduse erori in timpul transmisiei de la sursa la un receptor. Tehnicile de detectare a erorilor permit detectarea unor astfel de erori, in timp ce corectarea erorilor permite reconstructia datelor originale, in multe cazuri.
Definitii
Detectarea erorilor este procesul de cautare a erorilor cauzate de zgomot sau alte deteriorari in timpul transmisiei de la emitator la receptor.
Corectarea erorilor este detectarea erorilor si reconstructia datelor originale, fara erori.
Introducere
Toate schemele de detectare si corectare a erorilor adauga o oarecare redundanta (adica, niste date suplimentare) unui mesaj, pe care receptorii o pot folosi pentru a verifica consistenta mesajului livrat si pentru a recupera datele care s-au determinat a fi corupte. Schemele de detectare si corectare a erorilor pot fi fie sistematice, fie nesistematice.
Intr-o schema sistematica, transmitatorul trimite datele originale si ataseaza un numar fix de biti de verificare (sau date de paritate), care sunt derivati din bitii de date printr-un algoritm determinist. Daca este necesara doar detectarea erorilor, un receptor poate aplica pur si simplu acelasi algoritm bitilor de date receptionati si poate compara iesirea sa cu bitii de verificare primiti; daca valorile nu se potrivesc, a aparut o eroare la un moment dat in timpul transmisiei. Intr-un sistem care foloseste un cod nesistematic, mesajul original este transformat intr-un mesaj codificat care poarta aceeasi informatie si care are cel putin la fel de multi biti ca mesajul original.
O performanta buna de control al erorilor necesita selectarea schemei pe baza caracteristicilor canalului de comunicatie.
Modelele de canal obisnuite includ modele fara memorie in care erorile apar aleatoriu si cu o anumita probabilitate si modele dinamice, in care erorile apar in principal in rafale. In consecinta, codurile de detectare si corectare a erorilor pot fi in general diferentiate intre detectarea/corectarea erorilor aleatoare si detectarea/corectarea erorilor in rafala. Unele coduri pot fi, de asemenea, potrivite pentru un amestec de erori aleatoare si erori de rafala.
Daca caracteristicile canalului nu pot fi determinate sau sunt foarte variabile, o schema de detectare a erorilor poate fi combinata cu un sistem de retransmisii de date eronate. Aceasta este cunoscuta sub denumirea de cerere de repetare automata (ARQ) si este folosita in special pe Internet. O abordare alternativa pentru controlul erorilor este cererea hibrida de repetare automata (HARQ), care este o combinatie de codificare ARQ si corectare a erorilor.
Tipuri de corectare a erorilor
Exista trei tipuri majore de corectare a erorilor.
Cerere de repetare automata (ARQ)
Automatic Repeat ReQuest (ARQ) este o metoda de control al erorilor pentru transmisia de date care utilizeaza coduri de detectare a erorilor, mesaje de confirmare si/sau confirmare negativa si timeout-uri pentru a obtine o transmisie fiabila a datelor. O confirmare este un mesaj trimis de receptor pentru a indica faptul ca a primit corect un cadru de date.
De obicei, atunci cand transmitatorul nu primeste confirmarea inainte de expirarea timpului (adica intr-o perioada rezonabila de timp dupa trimiterea cadrului de date), retransmite cadrul pana cand este fie receptionat corect, fie eroarea persista dincolo de un numar predeterminat de retransmisii.
Exista trei tipuri de protocoale ARQ: Stop-and-wait ARQ, Go-Back-N ARQ si Selective Repeat ARQ.
ARQ este adecvat daca canalul de comunicare are capacitate variabila sau necunoscuta, cum este cazul pe Internet. Cu toate acestea, ARQ necesita disponibilitatea unui canal din spate, are ca rezultat o posibila latenta crescuta din cauza retransmisiilor si necesita intretinerea bufferelor si a temporizatoarelor pentru retransmisii, care, in cazul congestiei retelei, pot pune presiune pe server si pe capacitatea generala a retelei.
De exemplu, ARQ este utilizat pe legaturile de date radio cu unde scurte sub forma de ARQ-E sau combinat cu multiplexarea ca ARQ-M.
Redirectionarea erorilor
Redirectionarea erorilor (FEC) este un proces de adaugare a datelor redundante, cum ar fi un cod de corectare a erorilor (ECC), la un mesaj, astfel incat acesta sa poata fi recuperat de catre un receptor chiar si atunci cand exista un numar de erori (pana la capacitatea codului de a fi utilizate) care au fost introduse, fie in timpul procesului de transmitere, fie la depozitare. Deoarece receptorul nu trebuie sa ceara expeditorului retransmiterea datelor, nu este necesar un canal inapoi in corectarea erorilor inainte si, prin urmare, este potrivit pentru comunicatii de tip simplex, cum ar fi difuzarea. Codurile de corectare a erorilor sunt utilizate frecvent in comunicatiile de nivel inferior, precum si pentru stocarea fiabila pe medii precum CD-uri, DVD-uri, hard disk-uri si RAM.
Codurile de corectare a erorilor se disting de obicei intre codurile convolutionale si codurile bloc:
Codurile convolutionale sunt procesate bit cu bit. Sunt deosebit de potrivite pentru implementare in hardware, iar decodorul Viterbi permite o decodare optima.
Codurile bloc sunt procesate bloc cu bloc. Exemplele timpurii de coduri bloc sunt codurile de repetitie, codurile Hamming si codurile de verificare a paritatii multidimensionale. Au fost urmate de o serie de coduri eficiente, codurile Reed-Solomon fiind cele mai notabile datorita utilizarii lor actuale pe scara larga. Codurile Turbo si codurile de verificare a paritatii cu densitate scazuta (LDPC) sunt constructii relativ noi care pot oferi o eficienta aproape optima.
Teorema lui Shannon este o teorema importanta in corectarea erorilor directe si descrie rata maxima de informare la care este posibila o comunicare fiabila pe un canal care are o anumita probabilitate de eroare sau raport semnal-zgomot (SNR). Aceasta limita superioara stricta este exprimata in termeni de capacitate a canalului. Mai precis, teorema spune ca exista coduri astfel incat, odata cu cresterea lungimii de codare, probabilitatea de eroare pe un canal discret fara memorie poate fi redusa in mod arbitrar, cu conditia ca rata codului sa fie mai mica decat capacitatea canalului. Rata de codare este definita ca fractiunea k/n din k simboluri sursa si n simboluri codificate.
Rata de cod maxima reala permisa depinde de codul de corectare a erorilor utilizat si poate fi mai mica. Acest lucru se datoreaza faptului ca demonstratia lui Shannon a fost doar de natura existentiala si nu a aratat cum se construiesc coduri care sunt optime si au algoritmi eficienti de codificare si decodare.
Scheme hibride
Hybrid ARQ este o combinatie de ARQ si corectarea erorilor inainte. Exista doua abordari de baza:
- Mesajele sunt intotdeauna transmise cu date de paritate FEC (si redundanta de detectare a erorilor). Un receptor decodifica un mesaj utilizand informatiile de paritate si solicita retransmisia folosind ARQ numai daca datele de paritate nu au fost suficiente pentru o decodificare cu succes (identificate printr-o verificare a integritatii esuata).
- Mesajele sunt transmise fara date de paritate (numai cu informatii de detectare a erorilor). Daca un receptor detecteaza o eroare, solicita informatii FEC de la transmitator folosind ARQ si o foloseste pentru a reconstrui mesajul original.
Ultima abordare este deosebit de atractiva pe un canal de stergere atunci cand se utilizeaza un cod de stergere fara rate.
Scheme de detectare a erorilor
Detectarea erorilor este realizata cel mai frecvent utilizand o functie hash adecvata (sau in mod specific, o suma de control, verificare a redundantei ciclice sau alt algoritm). O functie hash adauga o eticheta cu lungime fixa la un mesaj, ceea ce le permite receptorilor sa verifice mesajul livrat recalculand eticheta si comparand-o cu cea furnizata.
Exista o mare varietate de modele diferite de functii hash. Cu toate acestea, unele sunt de utilizare deosebit de raspandita, fie datorita simplitatii lor, fie a adecvarii lor pentru detectarea anumitor tipuri de erori (de exemplu, performanta verificarii redundantei ciclice in detectarea erorilor de rafala).
Codare la distanta minima
Un cod de corectare aleatoare a erorilor bazat pe codarea la distanta minima poate oferi o garantie stricta asupra numarului de erori detectabile, dar este posibil sa nu protejeze impotriva unui atac inainte de imagine.
Codurile de repetitie
Un cod de repetitie este o schema de codare care repeta bitii pe un canal pentru a obtine o comunicare fara erori. Avand in vedere un flux de date care trebuie transmis, datele sunt impartite in blocuri de biti. Fiecare bloc este transmis de un numar prestabilit de ori. De exemplu, pentru a trimite modelul de biti „1011”, blocul de patru biti poate fi repetat de trei ori, producand astfel „1011 1011 1011”. Daca acest model de doisprezece biti a fost primit ca „1010 1011 1011” – unde primul bloc este diferit de celelalte doua – a aparut o eroare.
Un cod de repetitie este foarte ineficient si poate fi susceptibil la probleme daca eroarea apare exact in acelasi loc pentru fiecare grup (de exemplu, „1010 1010 1010” in exemplul anterior ar fi detectat ca fiind corect). Avantajul codurilor de repetitie este ca sunt extrem de simple si sunt de fapt folosite in unele transmisii de statii de numere.
Aplicatii
Aplicatiile care necesita o latenta scazuta (cum ar fi conversatiile telefonice) nu pot utiliza cererea de repetare automata (ARQ); trebuie sa utilizeze corectarea erorilor inainte (FEC). In momentul in care un sistem ARQ descopera o eroare si o retransmite, datele retrimise vor ajunge prea tarziu pentru a fi utilizabile.
Aplicatiile in care transmitatorul uita imediat informatiile de indata ce sunt trimise (cum ar fi majoritatea camerelor de televiziune) nu pot utiliza ARQ; trebuie sa utilizeze FEC deoarece atunci cand apare o eroare, datele originale nu mai sunt disponibile.
Aplicatiile care folosesc ARQ trebuie sa aiba un canal de retur; aplicatiile care nu au canal de intoarcere nu pot utiliza ARQ.
Aplicatiile care necesita rate de eroare extrem de scazute (cum ar fi transferurile de bani digitale) trebuie sa utilizeze ARQ din cauza posibilitatii de erori necorectabile cu FEC.
Fiabilitatea si ingineria de inspectie folosesc, de asemenea, teoria codurilor de corectare a erorilor.
Internet
Intr-o stiva tipica TCP/IP, controlul erorilor este efectuat la mai multe niveluri:
- Fiecare cadru Ethernet utilizeaza detectarea erorilor CRC-32. Cadrele cu erori detectate sunt eliminate de hardware-ul receptorului.
- Antetul IPv4 contine o suma de control care protejeaza continutul antetului. Pachetele cu sume de control incorecte sunt aruncate in retea sau la receptor.
- Suma de verificare a fost omisa din antetul IPv6 pentru a minimiza costurile de procesare in rutarea retelei si pentru ca se presupune ca tehnologia actuala a stratului de legatura ofera o detectare suficienta a erorilor.
- UDP are o suma de verificare optionala care acopera incarcarea utila si informatiile de adresare din anteturile UDP si IP. Pachetele cu sume de verificare incorecte sunt aruncate de stiva de retea. Suma de verificare este optionala in IPv4 si obligatorie in IPv6. Cand este omis, se presupune ca stratul de legatura de date ofera nivelul dorit de protectie impotriva erorilor.
- TCP ofera o suma de control pentru protejarea incarcaturii utile si a informatiilor de adresare din anteturile TCP si IP. Pachetele cu sume de control incorecte sunt aruncate de stiva de retea si, in cele din urma, sunt retransmise folosind ARQ.
