4. Comprobación de Redundancia Cíclica.

 

¿Que es CRC?

El núcleo de la verificación CRC es implementar la operación de división sin pedir prestado.

Aritmética módulo 2

La aritmética módulo 2 hace uso de sumas binarias sin acarreo, lo cual es exactamente igual que la operación lógica exclusive-OR. La operación de resta binaria sin acarreos es también igual que la operación lógica exclusive-OR. Por ejemplo:


El siguiente es un ejemplo para ilustrar cómo implementar la verificación CRC.

Para mostrar como funciona, vamos a hacerlo en forma de Polinomio.
Para ello representamos una secuencia de 0s y 1s como un Polinomio, por ejemplo:

101101  => a5 25 + a4 24 + a3 23+ a2 22 + a1 21 + ao 20   reemplazando cada ai  por el bit que corresponde 

101101  => 1 25 + 0 24 + 1 23+ 1 22 + 0 21 + 1 20  

101101  => 1. 32 + 0 . 16+ 1. 8 + 1. 4 + 0. 2 + 1.1  

Podemos ver que no es mas que el Polinomio que permite pasar de un número binario a un número decimal.

Justificación del CRC

Esto es lo que usaremos , esta forma de presentación de un Polinomio para justificar el uso de CRC para Detección de errores en la transmisión.

T / P = Q + R/P  (1)

T : trama de n bits a transmitir.
P: Polinomio Estandar de orden k
Q: Parte Entera de la División de Polinomios, ver que el Orden del Polinomo es menor que el orden de R o sea k+1
R: Resto de la división de Polinomios. k-1

Para transmitir , se  desplaza T en un orden que permita poner al final el Resto, esto sería como concatenar el Resto a continuación de T. En forma binaria eso se hace multiplicando T por el orden n-k.

T . 2 n-k + R =M  => esto es lo que transmito

M :mensaje con k bits de datos, correspondientes con los primeros k bits de T.

En el receptor divido nuevamente por el MISMO polinómio.

M / P = (T . 2 n-k + R)/P = T/P  . 2 n-k  + R/P  por (1)

Q + R/P + R/P  = Q + R/P + R/P 

Si la  suma +   fuera una or exclusiva y si los sumandos R/P son iguales, esta suma da CERO, lo que implicaría que lo transmitido y lo recibido coinciden!!. Este es el principio del Código de Redundancia Cíclica.

Polinomios de Uso Frecuente.

Suelen usarse alguno de estos cuatro polinomios, los mismos son definidos en un Standar.


Observación: El método NO es de cifrado.

A menudo se piensa que si, cuando llega un mensaje, este y su CRC coinciden, quiere decir que el mensaje no ha podido ser alterado durante su transmisión, aunque se haya transmitido por un canal abierto.  Esta suposición es falsa porque CRC es un mal método de cifrado de datos. De hecho, el CRC no se trata realmente de un método de cifrado, lo que realmente hace es utilizarse para el control de integridad de datos, pero en algunos casos se supone que se utilizarán para el cifrado.

Librería en C que permite hacer un cálculo de CRC

Implementación Electrónica

Esto sería: