Verificare redundanță ciclică

Verificarea redundanței ciclice (adică verificarea redundanței ciclice, CRC al cărei acronim este mai răspândit) este o metodă pentru calcularea sumelor de control (checksum în engleză). Numele derivă din faptul că datele de ieșire sunt obținute prin procesarea datelor de intrare care sunt derulate ciclic într-o rețea logică . Verificarea CRC este foarte populară, deoarece implementarea sa binară este ușor de realizat, necesită cunoștințe matematice modeste pentru estimarea erorilor și este bine potrivită pentru detectarea erorilor de transmisie pe liniile afectate de zgomot de fond ridicat. Tehnicile CRC au fost inventate de Wesley Peterson, care a publicat prima sa lucrare pe această temă în 1961 . ^[1]

Util pentru identificarea erorilor aleatorii în transmiterea datelor (datorită interferențelor, zgomotului de linie, distorsiuni), CRC, pe de altă parte, nu este fiabil pentru verificarea corectitudinii complete a datelor împotriva încercărilor de manipulare intenționată. În acest scop, se utilizează algoritmi hash precum MD5 și SHA1, care sunt mai robuși, deși din punct de vedere computerizat sunt mai puțin eficienți.

Implementare

Reprezentarea mecanismului intern al CRC-8 .

CRC asigură generarea unui șir de biți de control care este transmis în mod normal împreună cu datele, iar calculul se bazează pe aritmetica modulară . Un cod CRC este definit de polinomul generatorului său: de exemplu, codul CRC-16-CCITT, utilizat pe scară largă în telecomunicații, este definit de polinomul generatorului $x^{16}+x^{12}+x^{5}+1$ ${\ displaystyle x ^ {16} + x ^ {12} + x ^ {5} +1}$ $x ^ {{16}} + x ^ {{12}} + x ^ {5} +1$ .

Calculul CRC începe cu mesajul care este asociat cu un polinom $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ de grad egal cu numărul de biți ai mesajului minus unul, grad cu care vom indica $n-1$ ${\ displaystyle n-1}$ $n-1$ .

De exemplu, mesajul 10011010 ( $n-1=7$ ${\ displaystyle n-1 = 7}$ $n-1 = 7$ ) dă polinomul

$b(x)=x^{7}+x^{4}+x^{3}+x^{1}$ ${\ displaystyle b (x) = x ^ {7} + x ^ {4} + x ^ {3} + x ^ {1}}$ $b (x) = x ^ {7} + x ^ {4} + x ^ {3} + x ^ {1}$

Presupunând că CRC are un polinom $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ de grad $g$ ${\ displaystyle g}$ $g$ , „deplasăm” polinomul spre stânga $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ din $g$ ${\ displaystyle g}$ $g$ poziții, obținând polinomul $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ grad ( $h=n-1+g$ ${\ displaystyle h = n-1 + g}$ $h = n-1 + g$ ).

În exemplu, asumarea unui grad $g=4$ ${\ displaystyle g = 4}$ $g = 4$ primesti:

$p(x)=x^{4}*b(x)$ ${\ displaystyle p (x) = x ^ {4} * b (x)}$ ${\ displaystyle p (x) = x ^ {4} * b (x)}$

Împărțirea este acum efectuată $p(x)/g(x)$ ${\ displaystyle p (x) / g (x)}$ $p (x) / g (x)$ obținerea unui coeficient $q(x)$ ${\ displaystyle q (x)}$ $q (x)$ și o odihnă $r(x)$ ${\ displaystyle r (x)}$ $r (x)$ . Această împărțire se efectuează cu împărțirea lungă a modului 2 aritmetică, adică nu se efectuează reportări: amintiți-vă că în modulul 2 aritmetica adunarea și scăderea pot fi efectuate utilizând funcția logică XOR . Mesajul trimis de-a lungul canalului este format din unirea mesajului $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ minus restul diviziei $r(x)$ ${\ displaystyle r (x)}$ $r (x)$ .

$m(x)=p(x)-r(x)$ ${\ displaystyle m (x) = p (x) -r (x)}$ $m (x) = p (x) -r (x)$

Având în vedere că $r(x)$ ${\ displaystyle r (x)}$ $r (x)$ este restul unei diviziuni pe care o folosește ca divizor $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ , acest rest are un grad strict inferior celui de $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ ; amintindu-mi și asta $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ se obține prin preluarea mesajului de trimis $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ și traducerea acestuia prin poziții g, adică prin gradul polinomului $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ , obținem că polinoamele $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ Și $r(x)$ ${\ displaystyle r (x)}$ $r (x)$ , atunci când sunt adunate împreună, acestea nu se suprapun în termeni de grad egal și, prin urmare, putem presupune că mesajul $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ este trimis „nealterat”.

$p(x)$ ${\ displaystyle p (x)}$ $p (x)$ este de asemenea definibil ca

$p(x)=q(x)*g(x)+r(x)$ ${\ displaystyle p (x) = q (x) * g (x) + r (x)}$ $p (x) = q (x) * g (x) + r (x)$

Adică, polinomul este egal cu coeficientul de ori divizorul plus restul. Înlocuind această descriere în formula anterioară obținem acest lucru $m(x)$ ${\ displaystyle m (x)}$ $m (x)$ devine:

$m(x)=q(x)*g(x)+r(x)-r(x)$ ${\ displaystyle m (x) = q (x) * g (x) + r (x) -r (x)}$ $m (x) = q (x) * g (x) + r (x) -r (x)$

Prin legile algebrei pe câmpuri finite , scăzând din sine un polinom, obținem un polinom nul, deci $m(x)$ ${\ displaystyle m (x)}$ $m (x)$ devine:

$m(x)=q(x)*g(x)$ ${\ displaystyle m (x) = q (x) * g (x)}$ $m (x) = q (x) * g (x)$

Observăm că mesajul este deci divizibil cu polinomul generator cu restul zero. Detectarea erorilor folosește această proprietate, de fapt receptorul primește $m(x)$ ${\ displaystyle m (x)}$ $m (x)$ și îl împarte la polinom $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ care este definit mai sus. Dacă mesajul a fost primit nealterat, diviziunea nu produce nicio modificare, în timp ce dacă au apărut erori de transmisie, diviziunea va produce o modificare. Prezența mai multor erori ar putea produce în continuare o împărțire fără restul într-un mesaj eronat. Probabilitatea ca acest lucru să se întâmple depinde de polinom și de gradul său (este demonstrabil), dar acest lucru se întâmplă rar.

Dacă mesajul oferă zero rest, traduceți $m(x)$ ${\ displaystyle m (x)}$ $m (x)$ în dreapta unui grad g pentru a primi mesajul $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ de plecare.

Exemplu

Iată o implementare simplă în Python . Luați în considerare două dispozitive A și B, unde A este emițătorul și B receptorul.

Să presupunem că vrem să transmitem de la A la B o dată de naștere în format zz-ll-aaaa unde, fiecare cifră a datei corespunde unui octet.

Prin urmare, mesajul care va fi transmis va avea 64 de biți (cu excepția liniuțelor).

 '' '
Extrageți divizorii din polinom
'' '
def gets Divizorii polinomiali ( polinom ):
polinom Bin = bin ( polinom )
divizori = []
pentru idx , b în enumerate ( polinomBin [ 2 :], start = 1 ):
dacă b == '1' :
separatoare . append ( 1 << (( len ( polynomialBin [ 2 :]) - idx )))
separatoare de retur
'' '
Găsiți restul diviziunilor fiecărui divizor extrapolat din polinom.
Dacă restul diviziunii cu ultimul divizor este 0 atunci este corect
'' '
def isCorrect ( mesaj primit , divizori ):
temp = mesaj primit
pentru idx , valoarea în enumerare ( divizori ):
temp % = valoare
dacă temp == 0 și idx < len ( divizori ) - 1 :
temp = - 1
pauză
revenire temp

#codarea unui șablon al mesajului care trebuie transmis în format binar (de exemplu: 01-01-2000)
message = int ( '0000000000000001000000000000000100000010000000000000000000000000' , 2 )
print ( "Valoarea mesajului: % d " % mesaj )
#transformează polinomul ales în reprezentarea sa binară (x ^ 5 + x ^ 2 + 1)
polinom = int ( '100101' , 2 )
print ( "Valoare polinomială: % d " % polinom )
#mutați mesajul spre stânga cu 5 poziții, deoarece polinomul este de gradul cinci
mesaj = mesaj << 5
print ( "Valoarea mesajului: % d " % mesaj )
# Calculez crc care se dovedește a fi restul diviziunii dintre mesaj și polinom
crc = mesaj % polinom
print ( "valoarea CRC: % s " % bin ( crc ))
#coding mesajul care trebuie transmis în format binar (Ex: 08-12-1988)
messageToTransmit = int ( '0000000000001000000000010000000000000000100001001000010000000001000' , 2 )
#accesează crc la secvența de biți de transmis
messageTransmitting = (( messageTransmitting << 5 ) | crc )
print ( „Valoarea mesajului de transmis: % d ” % messageToTransmit )
#Primiți separatoare pentru diviziuni polinomiale
divizori = getPolinomialDivisors ( polinom )
print ( "Divizoare:" , divizoare )
# Verifică rezultatul
result = isCorrect ( mesajDaTrasmettere , separatoare)
x = Adevărat dacă rezultat == 0 altfel Fals
print ( „Rezultat: % r ” % x )

'' '
Ieșire:
Valoarea mesajului: 281479305232384
Valoare polinomială: 37
Valoarea mesajului: 18014675534872576
Valoare CRC: 0b11001
Valoarea mesajului de transmis: 72093053843734809
Divizoare: [32, 4, 1]
Rezultat: Adevărat
'' '

Notă

^ Peterson, W. Wκ. și Brown, DT, Coduri ciclice pentru detectarea erorilor , în Proceedings of the IRE , ianuarie 1961, DOI : 10.1109 / JRPROC.1961.287814 , ISSN 0096-8390 ( WC ACNP ) . - Hârtia originală pe CRC-uri

Elemente conexe

Stratul de legătură de date

linkuri externe

Portal IT

Portalul de matematică

Portal telematic

[1] Peterson, W. Wκ. și Brown, DT, Coduri ciclice pentru detectarea erorilor , în Proceedings of the IRE , ianuarie 1961, DOI : 10.1109 / JRPROC.1961.287814 , ISSN 0096-8390 ( WC ACNP ) . - Hârtia originală pe CRC-uri

[1]