Control de redundància cíclica

De Viquipèdia

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 hardware 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 binaries 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 a 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. 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.