Control de redundància cíclica

El CRC és un tipus de checksum basat en un codi cíclic. La linealitat dels codis cíclics en permet la representació polinòmica. El seu ús està molt estès perquè poden implementar-se en maquinari amb pocs components lògics i assoleixen una velocitat de càlcul admirable.

Aquests codis es basen en l'ús d'un polinomi generador G(X) de grau r, i en el principi que n bits de dades binàries es poden considerar com els coeficients d'un polinomi d'ordre n-1.

Per exemple, les dades 10111 poden tractar-se com el polinomi x⁴ + x² + x¹ + x⁰

A aquests bits de dades s'afegeixen r bits de redundància de manera que el polinomi resultant sigui divisible pel polinomi generador. El receptor verificarà si el polinomi rebut és divisible per G(X). Si no ho és, hi haurà un error en la transmissió.

Els bits de dades es divideixen en blocs (també anomenats trames o frames en anglès), i a cada bloc se li calcula r, que s'anomena seqüència de comprovació de bloc (Frame Check Sequence, FCS, en anglès).

Els polinomis generadors més utilitzats són:

CRC-12: x¹² + x¹¹ + x³ + x² + x¹ + 1. Utilitzat per a transmetre fluxos de 6 bits, junt amb uns altres 12 de redundància. És a dir, utilitza blocs de 6 bits, als que els uneix un FCS que genera de 12 bits.

CRC-16: x¹⁶ + x¹⁵ + x² + 1. Per a fluxos de 8 bits, amb 16 de redundància. Utilitzat als Estats Units, principalment.

CRC-CCITT: x¹⁶ + x¹² + x⁵ + 1. Per a fluxes de 8 bits, amb 16 de redundància. Utilitzat a Europa, principalment.

CRC-32: x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1. Dona una protecció extra sobre la que donen els CRC de 16 bits, que solen donar la suficient. És usat pel comitè d'estàndards de xarxes locals (IEEE 802) i en algunes aplicacions del Departament de Defensa dels Estats Units.

Procés de codificació

Suposem que volem transmetre la paraula de 4 bits P=1010, de manera que el polinomi equivalent seria P(x)=x³ + x¹.
Per a la codificació necessitem el polinomi generador (que serà el mateix en el receptor que en el emisor), en aquest cas utilitzarem G(x)=x² + x + 1.
Es multiplica P(x) pel grau de G(x), en aquest cas P(x)*x² obtenint M(x)=x⁵ + x³
Es divideix M(x)/G(x) i sobté un residu R(x), en aquest cas R(x)=x+1
La paraula a retransmetre està formada per la paraula original P(x) seguida de R(x), en aquest es formaria una paraula de 6 bits, els 4 primers d'informació i els 2 últims de control (paraula a retransmetre P(x)R(x)=101011).