Cyclic redundancy check
 | Acest articol sau această secțiune are bibliografia incompletă sau inexistentă. Puteți contribui prin adăugarea de referințe în vederea susținerii bibliografice a afirmațiilor pe care le conține. |
CRC (Control Redundant Ciclic) este o metodă matematică folosită pentru a verifica integritatea datelor. Este o formă de sumă de control, ce se bazează pe teoria polinoamelor de lungime maximă. Chiar dacă metoda CRC este mai sigura decât metoda bazată pe o simplă sumă de control, nu oferă o adevarată securitate criptografică. CRC este o tehnică folosită pentru detecția erorilor de transmisie. Pentru detecția și corectarea erorilor, există un registru special în care se stochează suma de control a datelor transferate. Aceasta se compară cu suma de control calculată și se elimină astfel posibilele erori. În acest caz, tehnica CRC este folosită doar pentru a asigura integritatea datelor la transferurile pe magistrală, nu și pentru a îmbunătăți integritatea datelor stocate pe discurile hard.
CRC - Coduri ciclice
[modificare | modificare sursă]Codurile ciclice sunt coduri bloc, având aceeași lungime a cuvintelor de cod, în care cele n simboluri ale cuvântului de cod sunt coeficienții unui polinom. Din combinațiile acestor coeficienți se pot forma polinoame diferite, iar numărul acestor polinoame este 2n. Pentru a realiza detecția și corecția erorilor, se aleg astfel pentru codare doar polinoamele divizibile printr-un polinom, numit polinom generator al codului.
Principiul codurilor ciclice de detecție a erorilor constă în calcularea la emisie a restului împărțirii polinomului ce conține cuvântul de cod ce trebuie emis la polinomul generator. Acest rest al împărțiri constituie suma ciclică de control. Dacă în procesul de transmisiune nu s-au introdus erori, polinomul ce reprezintă cuvantul recepționat va fi divizibil prin polinomul generator, deci restul va fi zero. Faptul că există un rest diferit de zero, poate constitui un criteriu pentru detecția erorilor. Dacă pozițiile în care s-au introdus erorile pot fi specificate din structura restului, atunci corecția erorilor poate fi efectuată. În acest sens, se consideră polinoame generatoare primitive(ireductibile și divizibile prin xn SAU EXCLUSIV 1 ).
Codurile ciclice se clasifică în coduri sistematice și nesistematice.
- codurile sistematice: simbolurile de informație pot fi amplasate grupat, la începutul sau sfârșitul cuvintelor de cod
- codurile nesistematice: simbolurile de informație și cele de control sunt amestecate
Calculul CRC (software si hardware)
[modificare | modificare sursă]Software
[modificare | modificare sursă]Pentru a realiza o aplicație software pentru calculul CRC există mai multe metode de implementare, în funcție de:
- ipotezele de la care se pornește calculul
- dimensiunea polinomului generator
- dimensiunea și structura mesajului pentru care se calculează CRC-ul
- timpul în care se generează CRC-ul
- dimensiunea spațiului de memorie alocat
- performanțele procesorului de calcul
Metodele de implementare se pot clasifica în două categorii:
- algoritmi de viteză redusă
- algoritmi de mare viteză
Pentru implementarea software a unui algoritm CRC trebuie realizată implementarea împărțirii în binar folosite de aritmetică CRC. Instrucțiunea de împărțire a unui calculator nu poate fi folosită deoarece împărțirea CRC nu este același lucru cu împărțirea normală și datorită dimensiunii mesajului, întrucât acesta poate ajunge la dimensiuni de ordinul MB, iar procesoarele actuale nu folosesc regiștri atât de mari. Pentru implementare, trebuie să existe un registru de deplasare, având dimensiunea egală cu gradul polinomului generator în care să se afle biții mesajului. Prelucrarea mesajului se va face bit cu bit. O alta metoda de implementare presupune existența unui tabel în care se găsesc biții polinomului CRC deplasați. Pentru a micșora timpul de execuție s-a trecut la procesarea în același timp cantități mai mari de biți(prelucrare paralelă): semiocteți(4 biți), octeți(8 biți), cuvinte(16 biți) și dublu-cuvinte(32 biți).Dintre acestea, prelucrarea semiocteților este evitată deoarece calculatoarele operează cu octeți. Pentru mărirea vitezei de execuție majoritatea implementărilor operează cu octeți sau cu multipli ai acestora.
Hardware
[modificare | modificare sursă]Implementarea hardware a CRC sub forma unui sistem ce are la baza un microcontroller are următoarele avantaje:
- Permite modificarea cu ușurința a metodei de calcul
- Permite o introducere și prelucrare simplă a datelor înainte de a fi supuse calculului
- Permite comunicația cu diferite periferice
- Permite comunicația cu calculatorul prin intermediul porturilor cum ar fi cel serial
Pentru obținerea unor timpi foarte mici se folosește o implementare de tip hardware cu bistabile în varianta paralelă.
Metode de detecție și corecție a erorilor
[modificare | modificare sursă]Suma de control la nivel de bloc este un alt mecanism de detecție a erorilor de transmisie. Mai întâi, datele sunt împărțite în blocuri, apoi se însumează și se obține o sumă care va fi trunchiată, inversată și adăugată la sfârșit. La recepție, blocurile primite, care includ și suma de la sfârșit, se adună pe măsură ce sosesc. În cazul în care suma obținută nu este 0, înseamnă că datele sunt eronate și atunci secvența trebuie retransmisă. Corecția erorii nu este posibilă. În cazul metodei CRC se calculează suma de control prin împărțire aritmetică. Secvența de biți este împărțită cu un număr special ales. Împărțirea se face în modulo 2, adică folosind operatorul XOR. Restul împărțirii este de fapt semnătura care va fi adăugată la sfârșit, după biții utili. Folosind algoritmul de la codurile Hamming se obține divizorul. La recepție, se recalculează restul împărțirii. Dacă acesta nu coincide cu restul primit, atunci secvența este eronată.
Performanțele acestei metode sunt impresionante. Un CRC care generează un rest de 16 biți poate detecta:
- toate erorile în rafală de maxim 16 biți
- toate numerele impare de biți din eroare
- 99.998 % din toate erorile de orice lungime
CRC-ul poate fi calculat mai ușor prin metode hardware, folosind registre cu deplasare și porți logice XOR. Controlul fluxului de date - metode hardware și software; acesta este necesar pentru a preveni erorile de depășire, când receptorul nu poate prelucra datele care vin cu viteză prea mare. De asemenea, și protocoalele pot detecta alterarea datelor cu ajutorul sumelor de control (check sums). Acestea sunt calculate în Internet prin împărțirea datelor în blocuri de 16 biți. Programul, care calculează sumele tratează fiecare bloc ca pe un număr întreg. Valorile binare ale tuturor blocurilor sunt însemnate, iar rezultatul (suma de control) se transmite împreună cu datele din aceste blocuri. Aceste sume sunt calculate la emițător și recalculate la receptor. O nepotrivire indică o eroare. Codurilor redundante ciclice (CRC) necesită calcule mai complexe și de aceea sunt în general implementate hardware. În cazul rețelelor de calculatoare, suma de control este un cod de dispersie pe 32 de biți a datelor. Reprezintă de fapt un număr rezultat dintr-un calcul matematic efectuat cu datele din pachet la calculatorul sursă. Pachetele reprezintă unitatea de bază a comunicațiilor în rețea. Atunci când pachetul ajunge la destinație, se reface calculul. Dacă rezultatele sunt identice, înseamnă că datele din pachet au rămas intacte. Dacă rezultatul de la destinație diferă de rezultatul de la sursă, înseamnă că datele au fost alterate (s-au modificat pe parcursul transmisiei datorită zgomotului de pe cablu). În acest caz, trebuie semnalizat calculatorului sursă faptul că trebuie să retransmită datele.
Modalități de calcul a sumei de control
[modificare | modificare sursă]Există trei modalități importante de a calcula această sumă de control:
- cyclic redundancy check (CRC) – se fac calcule polinomiale asupra datelor
- paritate bidimensională – se adună un bit care face ca o secvență de 8 biți să aibă un număr par sau impar de valori 1
- Internet checksum – se adună valoarea tuturor biților dată
Algoritmul de calcul CRC
[modificare | modificare sursă]Codurile polinomiale sunt bazate pe tratarea șirurilor de biți ca reprezentări de polinoame cu coeficienți 0 și 1. Ex.: 110001 = x5+x4+x0 Se va folosi aritmetica polinomială de tipul modulo 2, în care nu există transport la adunare și nici împrumut la scădere. Se va folosi, de asemenea, un polinom generator G(x). Acest polinom are atât bitul cel mai semnificativ cât și cel mai puțin semnificativ 1. Se dorește sa se adauge un număr de biți la sfărșitul unui cadru,ce are un polinom notat M(x)astfel încât M(x) divide G(x). Algoritmul pentru calculul sumei de control
- Fie r gradul lui G(x). Se adaugă r biți de 0 la capătul mai puțin semnificativ al cadrului astfel încât acesta
va corespunde polinomului xr M(x).
- Se împarte șirul de biți ce corespund lui G(x) într-un șir de biți corespunzător lui xr M(x), utilizând
împărțirea modulo 2.
- Se scade restul (care are întotdeauna r sau mai puțini biți) din șirul de biți corepunzător lui xr M(x),
utilizând scăderea modulo 2. Rezultatul este cadrul cu suma de control ce va fi transmis (acesta este divizibil modulo 2 cu G(x)).
- Exemplu:
- Cadru: 1101011011
- Generator: 10011
- Mesaj după adăugarea a 4 biți de 0: 1 1 0 1 0 1 1 0 1 10 0 0 0
- Cadru transmis: 1 1 0 1 0 1 1 01 1 1 1 1 0
- Anumite polinoame au devenit standarde internaționale. Cel folosit de IEEE 802 este: x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1