CRC

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 x4 + x2 + x1 + x0 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: x12 + x11 + x3 + x2 + x1 + 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: x16 + x15 + x2 + 1. Para flujos de 8 bits, con 16 de redundancia. Usado en Estados Unidos, principalmente.

CRC-CCITT: x16 + x12 + x5 + 1. Para flujos de 8 bits, con 16 de redundancia. Usado en Europa, principalmente.

CRC-32: x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + 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)=x2+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 El algoritmo utilizado por el control de redundancia cíclica es el siguiente: Se añaden r bits "0" a la derecha del mensaje (esto es, se añaden tantos ceros como grado tenga el polinomio generador). Se divide el polinomio obtenido por el polinomio generador. La división se realiza en módulo 2, que es igual que la división binaria, con dos excepciones: 1 + 1 = 0 (no hay acarreo) y 0 - 1 = 1 (no hay acarreo) Y se añade el resto de la división al polinomio original La elección del polinomio generador es esencial si queremos detectar la mayoría de los errores que ocurran. Uno de los polinomios generadores que más se suelen utilizar es el estándar CCITT: x16 + x12 + x5 + 1.

Este polinomio permite la detección de:

· 100% de errores simples.

· 100% de errores dobles.

· 100% de errores de un número impar de bits.

· 100% de errores en ráfagas (en una serie sucesiva de bits) de 16 o menos bits.

· 99.99% de errores en ráfagas de 18 o más bits.


Llevando a cabo el algoritmo de CRC en el hardware

El hardware que la aplicación de CRC se muestra en la próxima figura. La Aplicación mostrada es para un juego específico de parámetros: Mensaje M=1010001101 El modelo P=110101 FCS F=1110 (para ser calculado)
El circuito se lleva a cabo como sigue

1. El registro contiene los pedazos de n, iguale a la longitud del FCS

2. Hay de n las verjas de XOR

3. La presencia o ausencia de una verja corresponden a la presencia o ausencia de un término en el divisor P(X polinómico)

El mismo circuito se usa para creación y cheque del CRC. Al crear el FCS, el circuito acepta los pedazos del marco crudo y entonces una sucesión de ceros. La longitud de la sucesión está igual que la longitud del FCS. Los volúmenes del registro de cambio serán los FCS para añadir. Al verificar el FCS, el circuito acepta los pedazos del marco recibido (marco crudo añadido por FCS y quizás adulteró por los errores). Los volúmenes del registro de cambio deben ser cero o resto hay errores.

REGRESAR A LA PAGINA PRINCIPAL