Algoritmos para calcular CRC5 CRC7 CRC8 CRC16 CRC24 CRC32

[BrunoF]

Archivo adjunto con las rutinas al final del post, para lenguajes C y ASM

Debido a la cantidad de gente que ha estado consultandome por privado y al mail cómo realizar un CRC para diversos dispositivos(como los iButtons) me decidí a realizar las rutinas para calcular los 3 CRC más comunes: 8,16 y 32.

Entiendo que muchos hayan encontrado difícil entender o lograr conseguir un algoritmo que funcione según sus necesidades, ya que en la web el CRC no está muchas veces debidamente explicado. Tampoco es mi idea aclarar ésto. Si bien podría explicar básicamente de qué se trata sólo estaría hablando más de lo mísmo. Googlen para eso. No voy a explicar el por qué éstos algoritmos que publico a continuación funcionan.
   La explicación no es sencilla si no se poseen conocimientos avanzados de sistema binario, instrucciones de uC PIC y cálculo matemático. Si me parece pertinente y necesario en el futuro lo explicaré con gusto.Sin embargo, sí voy a explicar algo que trastorna a muchos que es cómo obtener el polinomio que se utiliza en el algorítmo basandose en el polinomio dado.

¿Listos? ¡Vamos!

Para realizar el cálculo del CRC de una determinada cantidad de bytes, primero hay ciertas convenciones que debemos averiguar(en caso que estemos trabajando con un CRC impuesto) o debemos establecer(en caso que nosotros realicemos nuestro CRC propio y personal).

el algoritmo de un CRC tiene 4 variables básicas de entrada que necesitamos para determinar su correcto cálculo:

un dato de entrada(value), que es el byte(en mis ejemplos son siempre de 8 bits de longitud. Para más bits hay que modificar mis algoritmos) del cual vamos a calcular su CRC;
un polinomio: que es el divisor de "value", y requiere de ciertos conocimientos para ser elegido adecuadamente. Exísten varios polinomios populares que son los más utilizados;
un valor entrada: es un valor(de 8, 16 o 32 bits) con el cual se realiza una XOR entre el mísmo y "value" apenas comienza el cálculo del CRC;
un valor salida: es un valor(de 8, 16 o 32 bits) con el cual se realiza una XOR entre el mísmo y "value" al final del cálculo del CRC;

El dato obviamente es el djavascript:ChangeEditor(5)ividendo y es necesario, el polinomio también lo es. Los valores de entrada y salida pueden ser usados como puede que no.Eso depende del método empleado.

Si no utilizan valor de salida y/o valor de entrada, recuerden poner su/s byte/s a cero antes de realizar el cálculo del CRC.Caso contrario el CRC les va a dar...MAL(99% probable)

Por ejemplo: MAXIM en su DOW CRC utiliza un valor de entrada, pero no de salida. Averigüen bien lo siguiente:

¿Qué polinomio utiliza?
¿Se utiliza una variable de entrada?
¿Se utiliza una variable de salida?

Una vez averiguados esos datos, procederemos a ver cúal es el CRC que debemos usar. A este dato nos los da el Polinomio. el CRC que deberemos usar será el grado del polinomio -1.

Ejemplo:

P(x) = x^{16} + x^{15} + x^2 + 1

El grado del polinomio es 16. Por lo que el CRC deberá ser de GRADO(P(x)) = 16. Usaremos el algoritmo de CRC16.


Acá viene una parte misteriosa del asunto. No he encontrado web alguna que hable realmente de cómo calcular el valor de la variable polinomio partiendo de su función polinómica.
Muchos me han consultado cómo hago para calcularlo. Si comprenden bien el funcionamiento binario del cálculo del CRC, podrán apreciar que se calcula de la siguiente manera:

Utilicemos el polinomio de más arriba:

P(x) = x^{16} + x^{15} + x^2 + 1

Pasos:

1)Transformar cada término del polinomio en su equivalente binario. Realizando ésto nos queda:

b11000000000000101

Para llegar a este valor, lo que hice sencillamente ha sido:

P(2) = 2^{16} + 2^{15} + 2^2 + 1=98309= b11000000000000101

El número 2 es el utilizado para el valor de x, porque estamos utilizando sistema binario(2 elementos).

2) Eliminar el bit de mayor peso,quedandonos ahora:

b1000000000000101

3) Espejar el valor binario, quedandonos:

b1010000000000001

Listo, tenemos nuestro valor polinómico para usar en el algoritmo. Lo pasamos a Hexadecimal si queremos, para que sea más legible:

b1010000000000001=10100000 00000001=1010 0000 0000 0001=A001=0xA001

Entonces, utilizaremos el valor 0xA001 en nuestra variable polinomio


Hagamos un ejemplo con un CRC8 popular, el DOW CRC8 usado por MAXIM en los IButtons:

Revisando la AN27 de Maxim, veremos que su polinomio es:

P(x) =x^8 + x^5 + x^4+ 1

Respetando los pasos que comenté haremos entonces:

1) Calcular el valor del polinimo con x=2 y pasar el resultado a binario:

P(2)=2^8 + 2^5 + 2^4 + 1=305= b100110001

2)Quitarle el bit de mayor peso:

b00110001

3)Espejarlo:

b10001100=1000 1100=0x8C

Listo. Tenemos nuestro polinomio. Ahora si leemos en la AN27, veremos que este CRC en particular utiliza un valor de entrada pero no de salida.
El valor de entrada para el primer byte del cálculo de una cadena de bytes es 0x00. Los posteriores valores corresponden al valor del CRC calculado para el byte previo.

A ver si puedo ilustrar bien esto. Supongamos que quiero calcular el CRC de la siguiente cadena de bytes: 0x55,0x34,0x24,0x11,0x01

Para calcularlo debería ir sometiendo byte per byte al CRC,pero teniendo en cuenta que la variable de entrada de un byte es el CRC calculado previo.

paso por paso:

CRC1 = calcular CRC8 con: value =0x55  poly =0x8C  enter_value=0x00 y  exit_value=0x00
CRC2 = calcular CRC8 con: value =0x34  poly =0x8C  enter_value=CRC1 y  exit_value=0x00
CRC3 = calcular CRC8 con: value =0x24  poly =0x8C  enter_value=CRC2 y  exit_value=0x00
CRC4 = calcular CRC8 con: value =0x11  poly =0x8C  enter_value=CRC3 y  exit_value=0x00
CRCF = calcular CRC8 con: value =0x01  poly =0x8C  enter_value=CRC4 y  exit_value=0x00


El CRC Final(CRCF) será el CRC buscado. Como verán, en este CRC se realiza una XOR al inicio del cálculo entre el CRC previo y el dato actual. Esto es debido a que mejora la diversificación de distintos CRC.

Espero que les haya servido la explicación. A continuación adjunto los archivos con los algorítmos correspondientes. Éxitos en su comprobación de datos.

BrunoF.


Actualización:

Corregí errores con el grado del polinomio de la explicación. Perdón por el error.

Agrego al archivo adjunto las rutinas para el cálculo de CRC5 para CCS y assmebly, así también como la de CRC24 para lenguaje assembly(gracias MigSantiago por mencionar la CRC5 del USB la cual había olvidado);

Menciono los CRC más comunes que pueden toparse al trabajar con uCs(posteen si saben de otros y los vamos agregando!):

CRC5:
USB: polinomio:

x^5+x^2+1

(0x14)

CRC7:
MMC-SD: polinomio:

x^7+x^3+1

(0x48)

CRC8:
iButton: polinomio:

x^8+x^5+x^4+1

(0x8C)

CRC16:
USB: polinomio:

x^{16}+x^{15}+x^2+1

(0xA001)
iButton: polinomio:

x^{16}+x^{15}+x^2+1

(0xA001)


Actualización:

Agregado CRC7...

Saludos.

[Nocturno]

Muy interesante, Bruno. Gracias

[migsantiago]

Qué bueno que lo explicas de forma sencilla. Tienes razón, todas las explicaciones que he intentado leer son muy difíciles de entender.

A ver si puedo aportar algo con el CRC5 usado en USB 

[BrunoF]

Gracias migsantiago, ahí agregue el CRC5.

[migsantiago]

 

Entonces acabas de hacerme la tarea de la escuela 

[migsantiago]

Hola Bruno

A ver si me quedó bien el cálculo siguiendo tu algoritmo:

Código: [Seleccionar]

int8 CRC5(int8 value, int8 poly, int8 init_value, int8 exit_value){

     int8 res,i;
     res=value;   
     res^=init_value;

     for(i=0;i<5;i++){
         if(res & 1){
             res>>= 1;
             res^=poly;
         }else{
             res>>= 1;
         }
     }

    res^=exit_value;
    return (int)res;
}
CRC 5 USB

Polinomio = x5 + x2 + 1
Equivale a: 100101
Borrando el bit de mayor peso: 00101
Espejeando: 10100 = 0x14

Aplicando el CRC 5 a un byte

Entrada 0xAA
Polinomio 0x14
Valor Inicial 0x00
Valor Final 0x00

Resultado XOR Valor Inicial:
10101010
00000000
------------
10101010 = Resultado

Realizar lo siguiente 5 veces (CRC 5)
 + Si el bit 0 de Resultado es 1, rotar a la derecha 1 vez y aplicar Resultado XOR Polinomio
 + Si el bit 0 de Resultado es 0, solo rotar a la derecha 1 vez

Ciclo 1
10101010 -> 01010101
Ciclo 2
01010101 -> 00101010 -> 00101010 XOR 00010100 = 00111110
Ciclo 3
00111110 -> 00011111
Ciclo 4
00011111 -> 00001111 -> 00001111 XOR 00010100 = 00011011
Ciclo 5
00011011 -> 00001101 -> 00001101 XOR 00010100 = 00011001

Calcular Resultado XOR Valor Final

00011001 XOR 00000000 = 00011001

Cálculo del CRC: 00011001 = 0x19

¿Está bien hecho? 

EDITO:
Leyendo más veces tu tutorial creo que encontré un error:

Entonces, utilizaremos el valor 0xA002 en nuestra variable polinomio

Creo que debería ser 0xA001.

Y en el adjunto de las funciones en la de CRC8 pones que calcula polinomios de 9 bits pero es de 8 

Una duda: ¿Qué significa el siguiente código?

Código: [Seleccionar]

cout << res << "\n";
Gracias Bruno.

[BrunoF]

¿Está bien hecho? 

Sí. 10 puntos.

EDITO:
Leyendo más veces tu tutorial creo que encontré un error:

Entonces, utilizaremos el valor 0xA002 en nuestra variable polinomio

Creo que debería ser 0xA001.

Si. Es un error, gracias. Lo que pasa fue que hice un ejemplo primero con un polinomio que daba 0xA002 y luego, como era tan parecido al CRC16 que se usaba para los i-buttons(0xA001), decidi cambiarlo y eso quedó del anterior.

Y en el adjunto de las funciones en la de CRC8 pones que calcula polinomios de 9 bits pero es de 8 

Sí. Lo que pasa es que si te fijas, los polinomios tienen 1 bit más que el polinomio del algorítmo.
Fijate que el polinomio del CRC5 que acabas de usar tiene 6 bits: 100101, pero luego el polinomio resultante para el algoritmo solo tiene 5 bits: 0x14 = 10100. Esto es parte de la teoría del algoritmo usado, y es bastante lógico ya que recordemos que el CRC es el resto de una división. Por definición, el resto siempre debe ser menor al divisor. Entonces, en binario, eso significa que el resto puede tener, a lo sumo, un bit menos que el divisor. Esto solo sucede en el sistema binario, ejemplo:


si hago 15 / 8 = 1 con resto=7. Fijate que como es sistema decimal, el resto tiene 1 dígito al igual que el divisor.


si ahora lo hago en binario:
1111 / 1000 = 1 con resto= 111. El resto tiene 3 bits, contra 4 que tiene el divisor. Este es el resto mas grande que puede quedar, y solo puede a lo sumo tener 1 bit menos que el divisor.

Por este motivo, se descarta el bit de mayor peso del polinomio al calcularlo(el 2do paso) ya que no aporta realmente al cálculo y en un CRC8, por ejemplo,obligaría tal vez a tener que usar 2 bytes para calcular el CRC. Similar con CRC16 y CRC32.

Una duda: ¿Qué significa el siguiente código?

Código: [Seleccionar]

cout << res << "\n";
Gracias Bruno.

No se donde lo leíste. Lo que pasa es que yo programé la parte de C en el DEV-C++ y se ve que han quedado "restos". Espero que al menos esté comentado. el cout lo usaba yo para imprimir en consola el resultado del CRC cuando estaba debugueando el código que iba haciendo.

Saludos.

[migsantiago]

Ah qué bien 

El código del cout viene en la función del CRC16 y CRC32 pero ahora veo que solo hay que comentarlo.

Gracias Bruno.

[migsantiago]

Una duda gigantesca...

8.3.5  Cyclic Redundancy Checks

...

For CRC generation and checking, the shift registers in the generator and checker are seeded with an all-
ones pattern.  For each data bit sent or received, the high order bit of the current remainder is XORed with
the data bit and then the remainder is shifted left one bit and the low-order bit set to zero.  If the result of
that XOR is one, then the remainder is XORed with the generator polynomial.
When the last bit of the checked field is sent, the CRC in the generator is inverted and sent to the checker
MSb first.  When the last bit of the CRC is received by the checker and no errors have occurred, the
remainder will be equal to the polynomial residual.
A CRC error exists if the computed checksum remainder at the end of a packet reception does not match the
residual.
Bit stuffing requirements must be met for the CRC, and this includes the need to insert a zero at the end of a
CRC if the preceding six bits were all ones.

8.3.5.1 Token CRCs
A five-bit CRC field is provided for tokens and covers the ADDR and ENDP fields of IN, SETUP, and
OUT tokens or the time stamp field of an SOF token.  The PING and SPLIT special tokens also include a
five-bit CRC field.  The generator polynomial is:

G(X) = X5 + X2 + 1

The binary bit pattern that represents this polynomial is 00101B.  If all token bits are received without error,
the five-bit residual at the receiver will be 01100B.

Esa es la sección que define el cálculo del CRC5 para USB. Mi enorme duda es que al final dice que el residuo de 5 bits será de 01100 solo si no hubo errores de transmisión...

- ¿Todos los residuos deben dar 01100?
- Para el cálculo de 0xAA como dato mi residuo fue de 0x19, ¿está mal para USB?

Intenté usar un valor inicial de 0xFF pero el resultado no da 01100. También intenté aplicar el valor final 0xFF pero nada.

Bruno, ¿sabes si tu método es distinto al que usa el USB?

[migsantiago]

Quisiera agregar que el CRC 5 USB se calcula sobre 11bits (ADDR + ENDP).

[migsantiago]

Bueno, ya estudié más y no coincide el método de crc hasta donde entiendo, pero afortunadamente tengo un analizador por hardware usb y en los ejemplos vienen algunos trenes de pulsos y sus respectivos CRC5.





En el 2do ejemplo, el valor de frame tiene 11 bits que están transmitidos desde el LSb hasta el MSb. El valor es:

Frame: 0000 0111 0011 0010

Si aplico el algoritmo como en el primer ejemplo...

Frame = 0x0732
Polinomio = 0x14
Valor Inicial = 0x00
Valor final = 0x00

El CRC resultante me da 00101 pero el que sale en el analizador es 00011 (el LSb se envía primero).

Ahora realizando el mismo caso pero con...

Frame = 0x0732
Polinomio = 0x14
Valor Inicial = 0xFF
Valor final = 0x00

En este caso me da 01100, pero tampoco coincide con 00011. 

Seguiré investigando.

[BrunoF]

Hola Santi! Estoy medio enfermo y no ando mucho por la PC. Puede que los CRC que no sean 8 o 16 tengan errores en su cálculo. Estuve mirando un poco pero no encontré ninguna tabla CRC5, eso es lo mas fácil para ver si el algoritmo responde bien.

Por ahi mirando en este link lo entendés un poco mejor a  los CRC usados por el USB:

http://www.usb.org/developers/whitepapers/crcdes.pdf

Sin embargo comparto tu idea de que no están andando. Por lo que leí en ese pdf, enter_value deberia ser 0x1F y exit_value también.

[BrunoF]

- ¿Todos los residuos deben dar 01100?

No. El CRC justamente es un método que intenta siempre obtener resultados muy distintos aun cuando cambia solo 1 bit de la trama para poder comprobar posibles errores durante el envio.

Bueno, los algoritmos no están mal pero si incompletos. Pasa que los algoritmos que expuse solo arrojan el CRC(correcto) cuando la cantidad de bits de la trama a enviar coincide con la cantidad de bits del CRC que se utiliza, es decir tramas de 8 bits para CRC8, tramas de 5 bits para CRC5,etc. Esto fue por migrar de CRC8 y CRC16,a CRC no multiplos de un byte, como CRC5,CRC7 y demás.

En el pdf que te indiqué arriba vienen un par de ejemplos de CRC5:

el crc5 10101000111 es 10111
el crc5 01011100101 es 11100

y otros mas....

Te dejo la subrutina modificada del CRC5 para que funcione correctamente con tramas de 11 bits, asi también como la llamada para obtener el CRC5 correcto.

Código: C

1. char CRC5(long value, char poly, char init_value, char exit_value){
2.  
3.      char i;
4.      long res;
5.  
6.      res=value;
7.    
8.      res^=init_value;
9.                   //reacomodado para 11bits de trama
10.      for(i=0;i<11;i++){
11.          if(res & 1){
12.              res>>= 1;
13.              res^=poly;
14.          }else{
15.              res>>= 1;
16.          }
17.      }
18.      
19.      res^=exit_value;
20.                 //solo quedarse con el byte bajo(solo sirven los 5 bits de menor peso, el resto deberian ser ceros)
21.      return (int8)res;
22. }

y para el ejemplo de trama '01011100101' llamarías así:

    int8 tmp;

    tmp=CRC5(741,0x14,0x1F,0x1F);

y debería devolver el valor decimal 28(11100). Caso contrario decime que me equivoqué en algo del algoritmo de arriba.

Un saludo.

[migsantiago]

Vientos y recontra vientos 

Déjame probarlas y hacerlas a mano y te confirmo si funcionan correctamente. Ayer en clase nos estuvimos peleando con los bits y con muchas XORs intentando llegar a lo que el CRC5 de las imágenes mostraban, pero no llegamos a nada.

Gracias Sr. Bruno

[blackcat]

Hola! ...

Muchas gracias por sus aportes ... en especial a BrunoF

Un dia estaba tratando de entender esta cuestion del CRC pero igual me hice bolas, entonces lo deje tirado, ahora que estoy leyendo tu post me volví a interesar pero a lo que yo entendia de CRC me quedé mas confundido (como siempre!  )....

En toda clase hay alguien que hace una pregunta tonta que siempre aclara las dudas de muchos ... me manifiesto, esta es mi pregunta tonta:

La cosa es que voy a transmitir una trama variable que contiene como máximo 128bytes ... se hace por RS232 y va de byte en byte ... yo entendía lo siguiente:

1-) El transmisor envia la trama y al final coloca el CRC .. es decir, si transmito 100bytes, calculo el CRC de esos 100bytes y coloco el CRC al final ... si fuere CRC16 entonces se transmiten 102bytes ...

2-) El receptor ya sabe que va a recibir 100 bytes (no interesa como), y que va a recibir 2 bytes extra de CRC ... ahora según un profesor (que sabe poco de implementacion de CRC! ) me dice que hay dos formas de saber si la trama llego bien:

    A-) Volviendo a calcular el CRC de los 100bytes y comparar con el CRC recibido.
    B-) Calcular el CRC de los 102 bytes, si el CRC da un valor particular como 0x0000 o 0xFFFF quiere decir que esta bueno.

Yo vi en internet varios algoritmos de CRC, probé todos pero ninguno me hacia según la verificación que explique en la parte B.

Ahora, baje los algoritmos que BrunoF propone ... pero veo que solo calcula CRC para tramas de 8, 16 etc bits....

¿Como puedo hacer una verificacion de tramas largas y variables?
¿Existe la verificacion que explico en la parte B?

Saludos!