Control de redundància cíclica

De Viquipèdia
Dreceres ràpides: navegació, cerca

Els codis cíclics també s'anomenen CRC (Codis de Redundància Cíclica) o codis polinòmics. El seu ús està molt estès perquè poden implementar-se en maquinari amb molta facilitat i són molt potents.

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 x4 + x2 + x1 + x0

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: x12 + x11 + x3 + x2 + x1 + 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-CCITT: x16 + x12 + x5 + 1. Per a fluxes de 8 bits, amb 16 de redundància. Utilitzat a Europa, principalment.
  • CRC-32: x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1. Dóna una protecció extra sobre la que donen els CRC de 16 bits, que solen donar la suficient. S'utilitza pel comité d'estàndars de xarxes locals (IEEE 802) i en algunes aplicacions del Departament de Defensa d'Estats Units.

Procés de codificació[modifica | modifica el codi]

  • Suposem que volem transmetre la paraula de 4 bits P=1010, de manera que el polinomi equivalent seria P(x)=x3 + x1.
  • 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)=x2 + x + 1.
  • Es multiplica P(x) pel grau de G(x), en aquest cas P(x)*x2 obtenint M(x)=x5 + x3
  • 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 bites, els 4 primers d'informació i els 2 últims de control (paraula a tretransmetre P(x)R(x)=101010).