Corecția și controlul erorilor

Pentru controlul erorilor, cel mai simplu mecanism folosit se numește “parity check” sau controlul parității. Fără a intra în aritmetica și dedesubturile acestuia, să discutăm concret despre un exemplu de control al parității. Pentru aceasta stabilim următorul set de reguli:

  • Vom calcula paritatea doar pentru biții de valoare 1.
  • Vom folosi transmisia pe 8 biți. Ca atare, pentru oricare 8 biți transmiși, vom transmite pe linie și un al nouălea bit, numit bit de paritate.
  • Bitul de paritate este 1 atunci când avem un număr par de biți de valoarea 1 în cod, sau sau zero, în caz contrar.

După cum vedeți, regulile sunt simple și la obiect. Așadar, să presupunem că avem o eroare în procesul de transmisie/ recepție:

  • S-a transmis codul: 10110011, alături de bitul de paritate cu valoarea 0 (semnalizând faptul că un cod transmis are un număr impar de valori 1);
  • Și că s-a recepționat codul 00110011, alături de bitul de paritate 0 (semnalizând faptul că un cod transmis are un număr impar de valori 1);

Rezultatele la emisie și la recepție sunt reprezentate ca în tabelele următoare (informaticienii numără întotdeauna de la 0). Am folosit scrierea pe verticală întrucât pe orizontală tabelele nu încap. Erorile sunt notate cu roșu, valorile corect cu 1. Oricum, este fix aceeași chestie:

S-a transmis codul inițial: 1011001+0
Bitul 0 1
Bitul 1 0
Bitul 2 1
Bitul 3 1
Bitul 4 0
Bitul 5 0
Bitul 6 1
Bitul 7 1
Bitul de paritate 0
Avem 5 valori de 1 în cod, deci un număr impar, evident. Așadar, bitul de paritate calculat și transmis va fi zero, semnalizând că trebuie să avem un număr impar de biți cu valoare 1 la recepție. Cel puțin teoretic, măcar.
S-a recepționat codul: 00110011+0
Bitul 0 0
Bitul 1 0
Bitul 2 1
Bitul 3 1
Bitul 4 0
Bitul 5 0
Bitul 6 1
Bitul 7 1
Bitul de paritate 0
Avem 4 valori de 1 în cod, un număr par. Bitul de paritate ar trebui să fie 1. Nu este, ceea ce înseamnă că a avut loc o eroare de recepție.

Evident, acest mecanism poate detecta doar erorile longitudinale (dea-lungul unui cuvânt), și nu poate face și corecția. Pentru implementarea unui mecanism de corecție mai de grabă rudimentar, se folosește și controlul parității transversale, despre care vom vorbi în continuare, sub mențiunea că algoritmii moderni de detecție și control a erorilor au trecut de faza asta și sunt mult mai avansați.

În primul rând, haideți să vedeți de ce nu este de ajuns mecanismul controlului parității pentru detectarea erorilor (față de exemplul precedent, doi biți au valorile inversate):

  • S-a transmis codul: 10110011, alături de bitul de paritate cu valoarea 0 (semnalizând faptul că un cod transmis are un număr impar de valori 1);
  • Și că s-a recepționat codul 01110011, alături de bitul de paritate 0 (semnalizând faptul că un cod transmis are un număr impar de valori 1);

Rezultatele la emisie și la recepție sunt reprezentate ca în tabelele următoare (informaticienii numără întotdeauna de la 0). Am folosit scrierea pe verticală întrucât pe orizontală tabelele nu încap. Erorile sunt notate cu roșu, valorile corect cu 1. Oricum, este fix aceeași chestie:

S-a transmis codul inițial: 1011001+0
Bitul 0 1
Bitul 1 0
Bitul 2 1
Bitul 3 1
Bitul 4 0
Bitul 5 0
Bitul 6 1
Bitul 7 1
Bitul de paritate 0
Avem 5 valori de 1 în cod, deci un număr impar. Așadar, bitul de paritate calculat și transmis va fi zero, semnalizând că trebuie să avem un număr impar de biți 1 la recepție. La fel, cel puțin la nivel teoretic. Evident, presupunem că transmisia e corectă, deși nu e cazul întotdeauna.
S-a recepționat codul cu eroare: 01110011+0
Bitul 0 0
Bitul 1 1
Bitul 2 1
Bitul 3 1
Bitul 4 0
Bitul 5 0
Bitul 6 1
Bitul 7 1
Bitul de paritate 0
Avem 5 valori de 1 în cod, deci un număr par. Așadar, bitul de paritate ar trebui să fie 0. Este 0, ceea ce înseamnă că nu a fost detectată o eroare de recepție. Dar sunt două erori în cod.

Evident, deși nu s-a detectat nicio eroare de transmisie/ recepție, codul recepționat este greșit. În două locuri, chiar. Așadar, se vede clar limita maximă de suportabilitate a mecanismului de calcul longitudinal al parității. De aceea, transmițând mai multe blocuri de date, le calculăm bitul de paritate atât longitudinal (dea-lungul byte-ului) cât și transversal (dea-lungul blocului de date), ca în tabelul următor.

byte

Blocul transmis Bit de 

paritate

0 1 0
1
0
1 0
1 0
1
1 1 1 0
1 1 0
1 1 1
2 1 1 1 0
0
1 0
1 0
3 0
0
1 0
0
1 0
1 0
4 0
1 1 1 0
1 1 1 1
5 1 0
0
0
0
0
0
0
0
6 0
0
1 1 1 0
0
1 1
7 0
0
1 0
1 0
0
1
0
C 1 0
1 0
1 0
0
1 0

byte

Blocul recepționat Bit de 

paritate

0 1 0
0
0
1 0
1 0
1
1 1 1 0
1 1 0
1 1 1
2 1 1 1 0
0
1 0
1 0
3 0
0
1 0
0
1 0
1 0
4 0
1 1 1 0
1 1 1 1
5 1 0
0
0
0
0
0
0
1
6 0
0
1 1 1 0
0
1 1
7 0
0
1 0
1 0
0
1
0
C 1 0
1 0
1 0
0
1 0

Având datele din tabelul de mai sus, putem calcula unde este eroarea și care este valoarea corectă, adică putem implementa un rudimentar mecanism de corecție și control al erorii. Să vedeți cum.

  • Luăm, de exemplu, byte-ul 0.
    • Cum se controlează eroarea:
      • Bitul te control al parității  longitudinale, calculat ca în exemplele de mai sus, ne semnalizează că s-a recepționat cu o eroare pe primul rând.
      • Bitul te control al parității transversale, din byte-ul notat cu “C” de la control, ne semnalizează că este o eroare pe coloana a doua.
    • Cum se corectează eroarea:
      • Satisfacem simultan condițiile necesare ca:
        • Bitul de paritate transversală să fie 1.
        • Bitul de paritate longitudinală să fie 1.
          • Soluția este doar una: bitul 2 (numerotat dinspre stânga spre dreapta, de la 0) să fie 1.

Desigur, dacă ar fi atât de simplu, tehnica n-ar trebui să mai evolueze. Dar nu este. Să vedem de ce. Să presupunem că avem o eroare de transmisie/ recepție în byte-ul 5, bitul 5  (deci rândul 6, coloana 5), și încă o eroare tot în byte-ul 5, pe coloana cu biții de control al parității (deci rândul 6, coloana 9):

byte

Blocul transmis Bit de 

paritate

0 1 0
1
0
1 0
1 0
1
1 1 1 0
1 1 0
1 1 1
2 1 1 1 0
0
1 0
1 0
3 0
0
1 0
0
1 0
1 0
4 0
1 1 1 0
1 1 1 1
5 1 0
0
0
0
0
0
0
0
6 0
0
1 1 1 0
0
1 1
7 0
0
1 0
1 0
0
1
0
C 1 0
1 0
1 0
0
1 0

byte

Blocul recepționat Bit de 

paritate

0 1 0
1
0
1 0
1 0
1
1 1 1 0
1 1 0
1 1 1
2 1 1 1 0
0
1 0
1 0
3 0
0
1 0
0
1 0
1 0
4 0
1 1 1 0
1 1 1 1
5 1 0
0
0
1
0
0
0
1
6 0
0
1 1 1 0
0
1 1
7 0
0
1 0
1 0
0
1
0
C 1 0
1 0
1 0
0
1 0
  • Luăm, după cum am spus, byte-ul 5.
    • Cum se controlează eroarea:
      • Bitul de control al parității  longitudinale, calculat ca în exemplele de mai sus, s-a transmis greșit. Așadar, nu știm că pe coloana a șasea bitul de control al parității s-a transmis greșit.
      • Știm, doar, că minim unul dintre biții de control a parității longitudinale s-a transmis greșit, nu știm care.
      • Bitul te control al parității transversale, din byte-ul notat cu “C” de la control, ne semnalizează că este o eroare pe coloana a patra, și că este o eroare și pe coloana biților de control.
    • Cum se corectează eroarea:
      • În acest caz erorile nu se pot corecta. Știm doar că eroarea este undeva pe coloana a cincea și a noua (biții de control a parității longitudinale), dar nu putem folosi ca referință biții de coloana biților de control longitudinal al erorii întrucât știm despre ei că sunt transmiți sau recepționați greșit.
    • Soluția? Blocul de date recepționat este invalidat și, ca atare, este cerut din nou.

Evident, sunt și algoritmi moderni mult mai sofisticați (acesta este chiar primul algoritm dezvoltat pentru corecția și controlul erorii) și care pot repara mult mai multe erori, doar că matematica lor nu este chiar cea mai simplă. Bine, putem vorbi despre diverși alți algoritmi de control și corecție a erorii, însă cei cu adevărat moderni se bazează pe o matematică complexă, mai ales dacă vorbim despre cazuri dificile, cum ar fi, de exemplu, transmisia wireless, în care pachetele transmise nu este neapărat să sosească în ordinea transmiterii (ba, chiar, ele sosesc intercalate de multe ori).

Ideea este că dacă ați reținut măcar cât am scris eu aici, eu sunt mulțumit. Ca și curiozitate, acest articol a fost, inițial, scris în cadrul unui articol despre modul de funcționare al unui modem, dar trebuit să le separ, întrucât primul articol devenea prea stufos.

[Adăugire ulterioară din 22 August 2010.]

Cauzele din care erorile pot să apară sunt multiple. De exemplu:

  • Prin mediul de transmisie semnalul nu se propagă perfect, acesta fiind influențat și de semnale parazite (unde radio, vibrații electro-magnetice de la transformatoare).
  • Pot apărea conflicte pe mediul de transmisie. Pe magistrala PC-ului (13), de exemplu, sau pe linia telefonică (1).
  • Stabilitatea și performanțele receptorului audio (5), ale convertorului analog – digital (6), ale convertorului digital – analog (20) și ale emițătorului audio (21) nu sunt ideale.„

De aceea, dispozitivele care au un caracter critic, esențial – serverele, de exemplu – folosesc diverse dispozitive care suportă controlul și corecția erorii. De aceea, în general memoriile RAM de la servere sunt unele speciale, ce au încorporate diverse mecanisme de control și corecție a erorii, precum memoria KVR667D2D4P5/2G.

Lasa un raspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *

Vreau să fiu părtaș la faptă. Poți, de asemenea, să fii părtaș și fără martori.

Acest sit folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.