Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza
Upload



















































Tipuri de erori si modalitatile de detectie a lor

Informatica


Tipuri de erori si modalitatile de detectie a lor

1.1 Introducere



Erorile au drept sursa principala zgomotul care afecteaza canalul de transmisiune a datelor.

Tipurile de erori care apar la transmisiunile de date sunt:

erorile simple, in cazul carora este alterata valoarea unui singur simbol;

erorile duble, pentru care se modifica valorile a 2 simboluri;

erorile triple, caz in care sunt transformate 3 simboluri;

pachete de erori, care reprezinta succesiuni de simboluri in care primul si ultimul sunt eronate, iar celelalte simboluri pot fi eronate sau nu.

Pentru detectia erorilor sunt folosite in principal patru metode:

Paritatea unidimensionala.

Paritatea bidimensionala.

Codurile simple redundante.

Codurile ciclice.

1.2 Paritatea unidimensionala

In cazul paritatii unidimensionale se adauga la mesaj un bit de paritate, care face ca numarul de biti de 1 din mesaj sa fie par sau impar.

Exemplu:

Date

Bit de paritate

Tip paritate

0110011

0

Para

0110001

1

Para

0110011

1

Impara

0110001

0

Impara

Daca un singur bit se altereaza in timpul transmisiei acesta va schimba paritatea astfel: de la para la impara sau invers. Emitatorul genereaza bitul de paritate prim sumarea modulo 2, adica prin aplicarea lui "sau exclusiv" tuturor bitilor din mesaj. Dupa aceea bitul de paritate sau complementul lui se adauga la mesaj. Receptorul poate verifica mesajul prin sumarea modulo 2 a bitilor si apoi comparand rezultatul cu bitul de paritate. O operatie echivalenta este sumarea modulo 2 atat a bitilor din mesaj cat si a bitului de paritate si apoi se verifica daca rezultatul este 0(aceasta in cazul unei paritati pare).

Aceasta tehnica de paritate se spune ca detecteaza erorile simple(modificarea valorii unui singur bit). De fapt detecteaza erorile in orice numar impar de biti(bitul 515j95f de paritate inclus), dar nu realizeaza si detectia unui numar de erori pare.

Exemplu:

Date originale

Date eronate

1001010 1

1111010 1

Datorita zgomotului bitii 2 si 3 din datele originale si-au schimbat valoarea in 1, acest lucru a trecut nedetectat intrucat paritatea nu a avut de suferit.

1.3 Paritatea bidimensionala

Paritatea bidimensionala este cunoscuta sub numele de paritate longitudinala/verticala. Informatia este dispusa pe linii formand o matrice. Acest tip de paritate foloseste atat cate un bit de paritate pentru fiecare linie a matricei dar si un cuvant de paritate reprezentat de ultima linie a matricei, in care fiecare bit reprezinta paritatea coloanei corespunzatoare. Bitul de paritate al fiecarei linii se gaseste pe ultima coloana din matrice, care poarta denumirea de VRC(Vertical Redundancy Check), in timp ce bitii de paritate pentru fiecare coloana formeaza ultima linie a matricei, numita LRC(Longitudinal Redundancy Check) sau cuvant de paritate.

Exemplu:

Date originale

VRC

1101011

1

1111111

1

0101010

1

0011001

1

LRC

0100111



0

Aceasta metoda nu detecteaza erorile de forma rectangulara pare sau de forme mai greu de descris care contin un numar par de erori in fiecare coloana si linie.

Exemplu:

Date eronate

VRC

1011011

1

1001111

1

0101010

1

0011001

1

LRC

0100111

0

1.4 Coduri simple redundante

In aceasta categorie intra coduri detectoare de erori caracterizate prin simplitate si comoditate in exploatare. Exemple de astfel de coduri: codul cu repetitie si codul cu pondere constanta.

Codul cu repetitie contine cuvinte de cod cu lungimea n=2k, k fiind numarul de simboluri de informatie. Codarea acestui cod consta in completarea secventei de informatie cu o secventa de control de aceeasi lungime. Structura secventei de control este identica cu a celei de informatie, daca ponderea acesteia este un numar par si este complementul bit cu bit al secventei de informatie daca ponderea acesteia este un numar impar. Cele doua jumatati ale cuvantului de cod sunt corelate. Absenta acestei corelatii la receptie indica prezenta erorilor.

Codul cu pondere constanta (cunoscut si sub numele de cod M din N) are cuvinte de cod de lungime N, compuse din M valori de 1 si N-M valori de 0 aranjate aleator. Se vede de aici ca din cele 2N cuvinte de N biti, doar 2k sunt cuvinte de cod si .

1.5 Coduri ciclice

Reprezinta o metoda puternica de detectie a erorilor folosita in transmisiile digitale de date, fiind cunoscuta sub denumirea de CRC (Cyclic Redundancy Check).

Codurile ciclice sunt coduri bloc (aceeasi lungime a cuvintelor de cod) n care cele n simboluri ale cuvantului de cod sunt considerate ca fiind coeficientii unui polinom.

Numarul de polinoame diferite ce pot fi formate din combinatiile coeficientilor de mai sus este 2n. In vederea realizarii detectiei si corectiei erorilor, din aceasta multime de polinoame se aleg pentru codare numai polinoamele divizibile printr-un polinom, numit polinom generator al codului.

Principiul codurilor ciclice de detectie a erorilor presupune calcularea la emisie a restului impartirii polinomului ce contine cuvantul de cod ce trebuie emis la polinomul generator; restul acestei impartiri reprezinta suma ciclica de control. Daca in procesul de transmisiune nu s-au introdus erori, polinomul ce reprezinta cuvantul receptionat va fi divizibil prin polinomul generator, deci restul va fi zero. Existenta unui rest diferit de zero este un criteriu pentru detectia erorilor. Daca din structura restului se pot preciza pozitiile in care s-au introdus erori atunci se va putea efectua si corectia erorilor. In acest sens, deci din considerente de corectie a erorilor, se considera polinoame generatoare primitive(oreductibile si divizibile prin xn1 ).

Codurile ciclice se clasifica in coduri sistematice si nesistematice.

-                    codurile sistematice: simbolurile de informatie pot fi amplasate grupat, la inceputul sau sfarsitul cuvintelor de cod

-                    codurile nesistematice: simbolurile de informatie si cele de control sunt amestecate

1.6 Comparatie intre coduri detectoare de erori

Daca consideram doua coduri detectoare de erori, caracterizate prin: numarul simbolurilor din cuvantul de cod, numarul simbolurilor de informatie din cuvantul de cod si numarul de erori detectate, pentru comparatie se vor folosi urmatoarele criterii:

-                    eficienta detectarii cuvintelor eronate;

-                    probabilitatea deciziei corecte.

2. Calculul CRC (software si hardware)

2.1 Software

Pentru realizarea unei aplicatii software pentru calculul CRC exista mai multe metode de implementare, in functie de:

-         ipotezele de la care se porneste calculul

-         dimensiunea polinomului generator

-         dimensiunea si structura mesajului pentru care se calculeaza CRC-ul

-         timpul in care se genereaza CRC-ul

-         dimensiunea spatiului de memorie alocat

-         performantele procesorului de calcul

Metodele de implementare se pot clasifica in doua categorii:

-         algoritmi de viteza redusa




-         algoritmi de mare viteza

acestia din urma folosind pentru tabele de calcul.

In functie de tipul aplicatiilor ITU si IEEE au standardizat urmatoarele polinoame generatoare:

Nume

Polinom

Reprezentare hexazecimala directa si inversa

CRC-1

x + 1 (folosit in hardware, bit de paritate)

0x1 sau 0x1

CRC-5-USB

x5 + x2 + 1 (folosit pentru pachetele USB)

0x05 sau 0x14

CRC-7

x7 + x3 + 1 (folosit in unele sisteme de telecomunicatii)

0x09 sau 0x48

CRC-8

x8 + x2 + x + 1

0x07 sau 0xE0

CRC-12

x12 + x11 + x3 + x2 + x + 1 (folosit in unele sisteme de telecomunicatii)

0x80F sau 0xF01

CRC-16-CCITT

x16 + x12 + x5 + 1

0x1021 sau 0x8408

CRC-16-IBM

x16 +x15 + x2 + 1

0x8005 sau 0xA001

CRC-32-IEEE 802.3

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 (Ethernet)

0x04C11DB7 sau 0xEDB88320

CRC-32C (Castagnoli)

x32 + x28 + x27 + x26 + x25 + x23 + x22 + x20 + x19 + x18 + x14 + x13 + x11 + x10 + x9 + x8 + x6 + 1

0x1EDC6F41 sau 0x82F63B78

CRC-64-ISO

x64 + x4 + x3 + x + 1

0x000000000000001B sau 0xD800000000000000

CRC-64-ECMA-182

x64 + x62 + x57 + x55 + x54 + x53 + x52 + x47 + x46 + x45 + x40 + x39 + x38 + x37 + x35 + x33 + x32 + x31 + x29 + x27 + x24 + x23 + x22 + x21 + x19 + x17 + x13 + x12 + x10 + x9 + x7 + x4 + x + 1

0x42F0E1EBA9EA3693 sau 0xC96C5795D7870F42

CRC-128

(IEEE? / ITU?)

?

Considerand modelul OSI, CRC-ul se calculeaza la nivelul 2 (Data Link) unde este incapsulat impreuna cu datele.

Cum am mai precizat, scopul tehnicilor de detectie a erorilor este ca un receptor sa poata decide daca mesajul trimis pe un canal afectat de zgomot a fost sau nu deteriorat. Pentru aceasta emitatorul construieste o valoare (numita suma de control), care este o functie de mesaj, si o adauga la sfarsitul acestuia. Receptorul foloseste aceeasi functie pentru calculul sumei de control a mesajului primit pentru a decide daca mesajul a fost receptionat corect. De exemplu, putem alege sa folosim o functie suma de control care aduna octetii mesajului si retine restul impartirii la 256; in tabelul de mai jos apar valorile zecimale:

Mesajul la emisie

6 23 4

Mesajul la emisie cu suma de control

6 23 4 33

Mesajul receptionat

6 27 4 37

Dupa cum este lesne de observat, al doilea octet din mesaj a fost afectat de zgomotul de pe canal si in loc de valoare corecta 23 a fost receptionata valoare 27. Receptorul detecteaza acest lucru prin simpla comparatie a sumei de control primite (33) cu cea calculata 37 (6+27+4). Daca insa suma de control are valoarea alterata, un mesaj transmis corect este identificat ca fiind corupt in mod eronat. Pentru a minimiza probabilitatea unei decizii incorecte se poate creste cantitatea de informatie continuta in suma de control (de exemplu se poate mari suma de control de la un octet la doi octeti).

O alta metoda de detectie presupune transformarea mesajului prin introducerea unei cantitati de informatie redundanta, dar aceasta nu se supune conventiilor de calcul pentru CRC, care presupun ca mesajul nu este alterat sub nici o forma:

<mesaj original intact><suma de control>.

Astfel putem observa cel putin doua aspecte necesare pentru obtinerea unei sume de control rezistente la erori:

lungimea: un registru de o dimensiune suficienta pentru a avea o probabilitate de eroare cat mai mica (de exemplu daca registrul sumei de control are 32 de biti atunci probabilitatea de eroare este de )

haosul: o formula de calcul care sa dea posibilitatea fiecarui bit din mesaj sa modifice oricati biti ai registrului.

Daca analizam alte directii in cautarea unei functii complexe pentru calculul sumei de control gasim diverse solutii, cum ar fi: construirea unui tabel folosind cifrele lui pi si amestecarea fiecarui octet din mesaj cu valorile continute de acesta. O solutie consumatoare de resurse ar fi folosirea on-line a unei carti mari de telefoane, si folosirea fiecarui octet din mesaj in combinatie cu octetii registrului pentru a adresa un nou numar de telefon, care ar putea fi noua valoare a registrului. Posibilitatile in acest sens sunt nelimitate.

Totusi, solutia de mai sus este exagerata; urmatorul pas este suficient. Deoarece s-a observat ca adunarea nu duce la o suma de control robusta, vom folosi operatia de impartire. Pentru aceasta vom alege impartitorul de aceeasi dimensiune cu registrul sumei de control.

Ideea care sta la baza algoritmilor pentru calculul ciclic al redundantei consta in aceea ca mesajul este vazut ca un numar binar de dimensiuni mari care se imparte la un numar binar fix, iar restul acestei operatii va fi suma de control. Dupa ce primeste mesajul, receptorul poate efectua aceeasi operatie si compara restul cu valoarea sumei de control (restul primit de la emitator).

Exemplu:



Consideram mesajul folosit anterior, format din doi octeti: 6, 23. In hexazecimal mesajul va avea forma: 0617, iar in binar: 0000-0110-0001-0111. Presupunem ca registrul sumei de control are dimensiunea de un octet si drept divizor folosim valoarea fixa: 1001, atunci suma de control va fi valoarea restului rezultat in urma impartirii lui 0000-0110-0001-0111 la 1001. In timp ce in acest caz putem folosi registri de 32 de biti, in general, din cauza dimensiunilor mari ale mesajelor, acest lucru este mai greu de realizat.

Exemplu de calcul a CRC-32 (Ethernet):

Mesaj original

01100001

Polinom CRC 32

100000100110000010001110110110111

Mesaj inversat

10000110

Mesaj extins cu 24 de zerouri

10000110000000000000000000000000

Mesaj FFFFFFFF

01111001111111111111111111111111

Mesaj extins cu 8 zerouri

0111100111111111111111111111111100000000

Pentru calculul CRC se transpune atat mesajul cat si polinomul CRC in polinoame de necunoscuta x:

Polinom mesaj original

Polinom CRC 32

Polinom mesaj prelucrat

In urma impartirii polinomului mesajului prelucrat la polinomul CRC 32 s-a obtinut:

=

Rest

00111101100000100001001011101000

=

Rest in binar

00010111010010000100000110111100

=

Rest inversat in binar

11101000101101111011111001000011

=

Rest FFFFFFFF

E8B7BE43

=

CRC 32

Pentru implementarea software a unui algoritm CRC trebuie realizata in principal implementarea impartirii in binar folosite de aritmetica CRC. Sunt doua motive pentru care nu se poate folosi instructiunea de impartire a unui calculator: primul este dat de faptul ca impartirea CRC nu este acelasi lucru cu impartirea normala, si al doilea este dat de dimensiunea mesajului, care poate ajunge la dimensiuni de ordinul MB, iar procesoarele actuale nu folosesc registri atat de mari.

O prima metoda de implementare presupune existenta unui registru de deplasare cu dimensiunea egala cu gradul polinomului generator in care sa se afle bitii mesajului. In acest caz prelucrarea mesajului se va face bit cu bit.

O metoda performanta de implementare are la baza existenta unui tabel in care se gasesc bitii polinomului CRC deplasati. Pentru a micsora timpul de executie s-a trecut la procesarea in acelasi timp cantitati mai mari de biti(prelucrare paralela): semiocteti(4 biti), octeti(8 biti), cuvinte(16 biti) si dublu-cuvinte(32 biti), si de ce nu chiar cuvinte mai mari. Dintre acestea, prelucrarea semioctetilor este evitata deoarece calculatoarele opereaza cu octeti. Astfel pentru marirea vitezei de executie majoritatea implementarilor opereaza cel mai uzual cu octeti sau cu multipli ai acestora.

Implementarea hardware a CRC se poate face in principal prin doua metode:

Folosind circuite de calcul cu registri de deplasare cu reactie implementate cu bistabile de tip D sau JK. Aceste circuite pot fi la randul lor circuite seriale sau circuite paralele, in functie de numarul de biti prelucrati la un moment dat. Trebuie facuta precizarea ca pentru o viteza ridicata de calcul se foloseste varianta de calcul pe baza de circuit paralel.

Cea de-a doua metoda consta intr-un sistem ce are la baza o unitate aritmetico-logica de calcul - microcontroller sau DSP.

2.2 Hardware

Implementarea hardware a CRC sub forma unui sistem ce are la baza un microcontroller are urmatoarele avantaje:

-         Permite modificarea cu usurinta a metodei de calcul

-         Permite o introducere si prelucrare simpla a datelor inainte de a fi supuse calculului

-         Permite comunicatia cu diferite periferice

-         Permite comunicatia cu calculatorul prin intermediul porturilor cum ar fi cel serial

Pentru obtinerea unor timpi foarte mici se foloseste o implementare de tip hardware cu bistabile in varianta paralela.













Document Info


Accesari: 5510
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.




Coduri - Postale, caen, cor

Politica de confidentialitate

Copyright Contact (SCRIGROUP Int. 2019 )