Control de redundancia cíclica

De Wikipedia, la enciclopedia libre

Los códigos cíclicos también se llaman CRC (Códigos de Redundancia Cíclica) o códigos polinómicos. Su uso está muy extendido porque pueden implementarse en hardware con mucha facilidad y son muy potentes.

Estos códigos se basan en el uso de un polinomio generador G(X) de grado r, y en el principio de que n bits de datos binarios se pueden considerar como los coeficientes de un polinomio de orden n-1.

Por ejemplo, los datos 10111 pueden tratarse como el polinomio x⁴ + x² + x¹ + x⁰

A estos bits de datos se le añaden r bits de redundancia de forma que el polinomio resultante sea divisible por el polinomio generador. El receptor verificará si el polinomio recibido es divisible por G(X). Si no lo es, habrá un error en la transmisión.

Los bits de datos se dividen en bloques (llamados frames en inglés), y a cada bloque se le calcula r, que se denomina secuencia de comprobación de bloque (Frame Check Sequence, FCS, en inglés)

Los polinomios generadores más usados son:

CRC-12: x¹² + x¹¹ + x³ + x² + x¹ + 1. Usado para transmitir flujos de 6 bits, junto a otros 12 de redundancia. Es decir, usa bloques de 6 bits, a los que les une un FCS que genera de 12 bits.

CRC-16: x¹⁶ + x¹⁵ + x² + 1. Para flujos de 8 bits, con 16 de redundancia. Usado en Estados Unidos, principalmente.

CRC-CCITT: x¹⁶ + x¹² + x⁵ + 1. Para flujos de 8 bits, con 16 de redundancia. Usado en Europa, principalmente.

CRC-32: x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1. Da una protección extra sobre la que dan los CRC de 16 bits, que suelen dar la suficiente. Se emplea por el comité de estándares de redes locales (IEEE 802) y en algunas aplicaciones del Departamento de Defensa de Estados Unidos.

Si tenemos un polinomio generador tal que G(x)=x²+1 podremos obtener a partir de él que el CRC es capaz de detectar todos los errores impares,genera una redundancia de 2 bits y no será capaz de detectar todos los errores dobles, por ejemplo una secuencia error-válido pasaría siempre inadvertida.