Scopul metodelor de detectare a erorilor este acela de a permite celui care primeste
un mesaj transmis printr-un mediu cu zgomot, sa recunoasca daca mesajul a fost sau nu corupt.
Ratele erorilor sunt semnificative in cazul comunicatiei fara fir, cu citeva ordine de marime mai frecvente decat pe trunchiurile de fibra optica. Erorile dintr-un mediu de transmisie tind sa apara mai degraba in rafale decat izolate. Avantajul este acela ca, in rafale, numarul blocurilor afectate este mai mic. Dezavantajul este dat de faptul ca sunt mult mai greu detectate.
Avem astfel doua tipuri de coduri:
Ne vom ocupa de coduri detectoare de erori si in special de CRC.
Coduri detectoare de erori
Transmitatorul construieste o valoare (checksum) care depinde de continutul mesajului si o adauga acestuia. Receptorul va utiliza aceeasi functie pentru a calcula suma de control, valoare pe care o va compara cu cea receptionata. Avem doua cazuri:
Receptorul nu poate face deosebire intre aceste doua cazuri si va cere retransmisia blocului.
Exemplu:
Sa luam ca functie suma octetilor din mesaj modulo 256. Mesaj : 4 26 5 Mesaj transmis : 4 26 5 35 Mesaj receptionat : 6 26 5 35
Pot apare insa si erori care sa modifice mesajul astfel ca suma de control calculata sa fie aceeasi, dar mesajul sa fie incorect. Pentru a minimiza aparitia acestor situatii tot ce se poate face este sa se reduca probabilitatea de aparitie a lor.
Aceasta se poate face extinzind valoarea sumei de control de la un octet la doi octeti.
Algoritmul general
Idea algoritmului CRC este de a considera mesajul ca un singur numar binar pe care sa-l impartim repetat cu o alta valoare fixata, suma de control fiind restul impartirii.
Sirul de biti este interpretat ca un polinom cu coeficienti cu 1 si 0. Un cadru de k biti este vazut ca o lista de coeficienti pentru un polinom de grad k-1. Bitul cel mai semnificativ este coeficientul lui x^(k-1).
Exemplu:
23=17(hexa)=10111(binar):
1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0 = x^4 + x^2 + x^1 + x^0
Aritmetica polinomiala mod 2 este aritmetica binara mod 2 fara transport. Adunarile si scaderile sunt identice cu "sau exclusiv" - XOR.
10011011 +11001010 ========= 01010001
Inmultirea este foarte simpla:
1101
x 1011
----
1101
1101.
0000..
1101...
-------
1111111
Impartirea este putin mai complicata deoarece trebuie sa stim cind un numar este mai mic ca altul: X este mai mare sau egal cu Y daca pozitia bitului 1 cel mai din stinga al lui X este aceeasi sau mai mare ca pozitia bitului 1 cel mai din stinga al lui Y.
1100001010
_______________
10011 ) 11010110110000
10011,,.,,....
-----,,.,,....
10011,.,,....
10011,.,,....
-----,.,,....
00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Restul
Pentru a calcula CRC, emitatorul si receptorul stabilesc un impartitor: acesta se mai numeste si polinom generator. Bitul cel mai semnificativ cit si cel mai putin semnificativ trebuie sa fie 1.
Algoritmul pentru calculul CRC este:
Receptorul poate alege una din urmatoarele metode:
Alegerea unui polinom
Alegerea unui polinom generator nu este o treaba simpla. Trei polinoame sunt mai utilizate:
CRC-12 = x^12+x^11+x^3+x^2+x^1+1 (lungimea caracterului are 6 biti)
CRC-16 = x^16+x^15+x^2+1
CRC-CCITT = x^16+x^12+x^5+1 (detecteaza toate erorile singulare, duble, cu numar impar
de biti, toate erorile in rafala de lungime 16 sau mai
mica...)
Ethernet = x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+1
Algoritmul
Sa exemplificam acum algoritmul printr-un model de calcul. Vom considera polinomul generator=10111. Pentru impartire vom folosi un registru format din 4 biti:
3 2 1 0 Bits
+---+---+---+---+
Out <-- | | | | | <----- Mesajul
+---+---+---+---+
1 0 1 1 1 = Polinomul
Impartirea se va face astfel:
registru=0
Adaugam 4 biti de valoare 0 la sfirsitul mesajului.
While (mai exista biti in mesaj)
Begin
Shiftam registrul la stinga cu un bit si citim urmatorul bit al mesajului pe pozitia 0.
If (bitul 1 a fost eliminat la pasul anterior prin shiftare)
registru = registru XOR Polinom.
End
La sfirsitul calculului in registru se va afla valoarea cautata.
Iata un alt exemplu dar folosind valori precalculate, iar calculul se face pe 32 de biti:
unsigned char *p;
unsigned long r;
int len;
r=0;
while (len--)
{
byte t = (r >> 24) & 0xFF;
r = (r << 8) | *p++;
r^=table[t];
}
Suma de control Fletcher
La sfirsitul anilor '70 s-a pus la punct o tehnica de transmitere a datelor cu rezultate similare cu CRC dar necesitind un timp de calcul mai redus, cunoscuta sub numele de Suma de control Fletcher.
Cimpul de verificare in algoritm se compune din doua variabile pe 8 biti.Pe masura ce fiecare octet din blocul de date este procesat, valoarea acestuia este adunata la prima variabila, iar restul impartirii acesteia cu 255 devine noua valoare a variabilei. A doua variabila este restul impartirii la 255 a sumei dintre valoarea precedenta si valoarea curenta a primei variabile.
Se pot adauga doi noi octeti care adaugati la sfirsitul blocului de date sa duca la o suma de control 0 la verificarea de catre primitor. Primul octet calculat este 255 minus restul impartirii la 255 a sumei celor doua variabile de control. Al doilea octet este 255 minus restul impartirii la 255 a sumei dintre primul octet si prima variabila de control.
integer i;
byte sum1, sum2;
sum1=0;
sum2=0;
for i=1 to block_length do
sum1=(sum1+Block[i]) mod 255;
sum2=(sum1+sum2) mod 255;
endfor
check1=255-(sum1+sum2) mod 255;
check2=255-(sum1+check1) mod 255;
Algoritmul Fletcher permite o detectare a erorilor comparabila cu cea a algoritmului CRC, dar la un nivel de calcul cu un ordin mai mic, fiind recomandat implementarii pe procesoare mai lente.