Comprovació de redundància cíclica

La comprovació de la redundància cíclica (és a dir , la comprovació de la redundància cíclica, CRC les sigles de la qual és més freqüent) és un mètode per al càlcul de sumes de comprovació (checksum en anglès). El nom deriva del fet que les dades de sortida s’obtenen processant les dades d’entrada que es desplacen cíclicament en una xarxa lògica . La comprovació CRC és molt popular perquè la seva implementació binària és senzilla de fer, requereix coneixements matemàtics modestos per a l’estimació d’errors i és molt adequada per detectar errors de transmissió en línies afectades per un alt soroll de fons. Wesley Peterson va inventar les tècniques CRC que va publicar el seu primer treball sobre el tema el 1961 . ^[1]

Útil per identificar errors aleatoris en la transmissió de dades (a causa d’interferències, soroll de línia, distorsió), el CRC, en canvi, no és fiable per verificar la completa correcció de les dades contra intents de manipulació intencionats. Per a això, s’utilitzen algoritmes de hash com MD5 i SHA1, que són més robustos encara que computacionalment menys eficients.

Implementació

Representació del mecanisme intern del CRC-8 .

El CRC preveu la generació d’una cadena de bits de control que normalment es transmeten juntament amb les dades i el càlcul es basa en l’ aritmètica modular . Un codi CRC es defineix pel seu polinomi generador: per exemple, el codi CRC-16-CCITT, àmpliament utilitzat en telecomunicacions, el defineix el polinomi generador $x^{16}+x^{12}+x^{5}+1$ ${\ displaystyle x ^ {16} + x ^ {12} + x ^ {5} +1}$ $x ^ {{16}} + x ^ {{12}} + x ^ {5} +1$ .

El càlcul del CRC comença amb el missatge associat a un polinomi $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ de grau igual al nombre de bits del missatge menys un, grau que indicarem amb $n-1$ ${\ displaystyle n-1}$ $n-1$ .

Per exemple, el missatge 10011010 ( $n-1=7$ ${\ displaystyle n-1 = 7}$ $n-1 = 7$ ) dóna el polinomi

$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}$

Suposant que el CRC té un polinomi $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ de grau $g$ ${\ displaystyle g}$ $g$ , "desplaçem" el polinomi cap a l'esquerra $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ des de $g$ ${\ displaystyle g}$ $g$ posicions, obtenint el polinomi $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ grau ( $h=n-1+g$ ${\ displaystyle h = n-1 + g}$ $h = n-1 + g$ ).

A l'exemple, assumint un títol $g=4$ ${\ displaystyle g = 4}$ $g = 4$ obtens:

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

Ara es realitza la divisió $p(x)/g(x)$ ${\ displaystyle p (x) / g (x)}$ $p (x) / g (x)$ obtenint un quocient $q(x)$ ${\ displaystyle q (x)}$ $q (x)$ i un descans $r(x)$ ${\ displaystyle r (x)}$ $r (x)$ . Aquesta divisió es duu a terme amb la divisió llarga de l'aritmètica del mòdul 2, és a dir, no es fan transferències: recordeu que en l'aritmètica del mòdul 2 es pot realitzar la suma i la resta mitjançant la funció lògica XOR . El missatge enviat al llarg del canal està format per la unió del missatge $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ menys la resta de la divisió $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)$

Considerant això $r(x)$ ${\ displaystyle r (x)}$ $r (x)$ és la resta d'una divisió que utilitza com a divisor $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ , aquesta resta té un grau estrictament inferior al de $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ ; recordant-ho també $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ s’obté prenent el missatge que s’enviarà $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ i traduir-lo per g posicions, és a dir, pel grau del polinomi $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ , obtenim que els polinomis $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ I $r(x)$ ${\ displaystyle r (x)}$ $r (x)$ , sumats, no se superposen en termes d'igual grau i, per tant, podem suposar que el missatge $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ s'envia "inalterat".

$p(x)$ ${\ displaystyle p (x)}$ $p (x)$ també es pot definir com

$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)$

És a dir, el polinomi és igual al quocient vegades el divisor més la resta. En substituir aquesta descripció a la fórmula anterior ho obtindrem $m(x)$ ${\ displaystyle m (x)}$ $m (x)$ es converteix en:

$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)$

Per les lleis de l'àlgebra sobre camps finits , restant un polinomi de si mateix, obtenim un polinomi nul, per tant $m(x)$ ${\ displaystyle m (x)}$ $m (x)$ esdevé:

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

Observem que, per tant, el missatge és divisible pel polinomi generador amb zero residus. La detecció d'errors utilitza aquesta propietat, de fet el receptor rep $m(x)$ ${\ displaystyle m (x)}$ $m (x)$ i el divideix pel polinomi $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ que es defineix més amunt. Si el missatge s'ha rebut sense canvis, la divisió no produeix cap canvi, mentre que si s'han produït errors de transmissió, la divisió produirà un canvi. La presència de múltiples errors encara podria produir una divisió sense cap resta en un missatge erroni. La probabilitat que això passi depèn del polinomi i del seu grau (és demostrable), però rarament passa això.

Si el missatge dóna zero residus, només cal traduir $m(x)$ ${\ displaystyle m (x)}$ $m (x)$ a la dreta d'un grau g per obtenir el missatge $b(x)$ ${\ displaystyle b (x)}$ $b (x)$ de sortida.

Exemple

Aquí hi ha una implementació senzilla a Python . Penseu en dos dispositius A i B, on A és el transmissor i B el receptor.

Suposem que volem transmetre de A a B una data de naixement en el format dd-mm-aaaa on, cada dígit de la data correspon a un byte.

Per tant, el missatge a transmetre tindrà una longitud de 64 bits (sense guions).

 '' '
Extraieu els divisors del polinomi
'' '
def obté Divisors polinomials ( polinomi ):
polinomi Bin = bin ( polinomi )
divisors = []
per a idx , b a enumerar ( polinomi Bin [ 2 :], inici = 1 ):
si b == '1' :
separadors . append ( 1 << (( len ( polynomialBin [ 2 :]) - idx )))
divisors de retorn
'' '
Trobeu la resta de les divisions de cada divisor extrapolades del polinomi.
Si la resta de la divisió amb l'últim divisor és 0, llavors és correcte
'' '
def isCorrect ( missatge rebut , divisors ):
temp = missatge rebut
per a idx , valor en enumerar ( divisors ):
temp % = valor
si temp == 0 i idx < len ( divisors ) - 1 :
temp = - 1
trencar
temperatura de retorn

#coding una plantilla del missatge que es transmetrà en format binari (per exemple: 01-01-2000)
message = int ( "0000000000000001000000000000000100000010000000000000000000000000" , 2 )
print ( "Valor del missatge: % d " % missatge )
# transforma el polinomi escollit en la seva representació binària (x ^ 5 + x ^ 2 + 1)
polinomi = int ( '100101' , 2 )
print ( "Valor polinòmic: % d " % polinomi )
#modeu el missatge cap a l'esquerra en 5 posicions perquè el polinomi és de cinquè grau
missatge = missatge << 5
print ( "Valor del missatge: % d " % missatge )
# Calculo el crc que resulta ser la resta de la divisió entre el missatge i el polinomi
crc = missatge % polinomi
print ( "valor CRC: % s " % bin ( crc ))
#coding del missatge a transmetre en format binari (Ex: 08-12-1988)
messageToTransmit = int ( '0000000000001000000000000000000000000000000001001000010000000001000' , 2 )
#accendiu el crc a la seqüència de bits a transmetre
messageTransmitting = (( messageTransmitting << 5 ) | crc )
print ( "Valor del missatge a transmetre: % d " % messageToTransmit )
# Rebre divisors per a divisions polinòmiques
divisors = getPolinomialDivisors ( polinomi )
print ( "Divisors" , divisors )
#Comproveu el resultat
result = isCorrect (messaggioDaTrasmettere, divisors)
x = True si result == 0 else False
print ( "Resultat: % r " % x )

'' '
Sortida:
Valor del missatge: 281479305232384
Valor polinòmic: 37
Valor del missatge: 18014675534872576
Valor CRC: 0b11001
Valor del missatge a transmetre: 72093053843734809
Divisors: [32, 4, 1]
Resultat: cert
'' '

Nota

↑ Peterson, W. Wκ. i Brown, DT, Codis cíclics per a la detecció d’errors , a Proceedings of the IRE , gener de 1961, DOI : 10.1109 / JRPROC.1961.287814 , ISSN 0096-8390 ( WC ACNP ) . - El document original sobre CRC

Articles relacionats

Capa d'enllaç de dades

Enllaços externs

Portal informàtic

Portal de Matemàtiques

Portal Telemàtic

[1] Peterson, W. Wκ. i Brown, DT, Codis cíclics per a la detecció d’errors , a Proceedings of the IRE , gener de 1961, DOI : 10.1109 / JRPROC.1961.287814 , ISSN 0096-8390 ( WC ACNP ) . - El document original sobre CRC

[1]