cálculo de CRC en línea y biblioteca gratuita

introducción sobre los cálculos CRC

siempre que se almacenen o interactúen datos digitales, puede producirse corrupción de datos. Desde el comienzo de la informática, la gente ha estado pensando en formas de lidiar con este tipo de problema., Para los datos en serie, se les ocurrió la solución de adjuntar un bit de paridad a cada byte enviado. Este mecanismo de detección simple funciona si un número impar de bits en un byte cambia, pero un número par de bits falsos en un byte no será detectado por la comprobación de paridad. Para superar este problema, la gente ha buscado mecanismos matemáticos de sonido para detectar múltiples bits falsos. El cálculo CRC o comprobación de redundancia cíclica fue el resultado de esto. Hoy en día los cálculos de CRC se utilizan en todo tipo de comunicaciones. Todos los paquetes enviados a través de una conexión de red se comprueban con un CRC., También cada bloque de datos en su disco duro tiene un valor CRC adjunto. El mundo informático moderno no puede prescindir de estos cálculos CRC. Así que vamos a ver por qué son tan ampliamente utilizados. La respuesta es simple, son potentes, detectan muchos tipos de errores y son extremadamente rápidos de calcular, especialmente cuando se utilizan chips de hardware dedicados.

uno podría pensar, que el uso de una suma de comprobación puede reemplazar los cálculos CRC adecuados. Ciertamente es más fácil calcular una suma de comprobación, pero las sumas de comprobación no encuentran todos los errores. Tomemos una cadena de ejemplo y calculemos una suma de verificación de un byte., La cadena de ejemplo es «Lammert» que se convierte a los valores ASCII . La suma de verificación de un byte de esta matriz se puede calcular agregando todos los valores, luego dividiéndola por 256 y manteniendo el resto. La suma de comprobación resultante es 210. Puede utilizar la calculadora anterior para comprobar este resultado.

en este ejemplo hemos utilizado una suma de verificación larga de un byte que nos da 256 valores diferentes. El uso de una suma de verificación de dos bytes dará como resultado 65,536 posibles valores de suma de verificación diferentes y cuando se usa un valor de cuatro bytes, hay más de cuatro mil millones de valores posibles., Podríamos concluir que con una suma de verificación de cuatro bytes la posibilidad de que accidentalmente no detectemos un error es menor que 1 a 4 mil millones. Parece bastante bueno, pero esto es sólo teoría. En la práctica, los TBI no cambian puramente al azar durante las comunicaciones. A menudo fallan en ráfagas o debido a picos eléctricos. Supongamos que en nuestra matriz de ejemplo se establece el bit significativo más bajo del carácter ‘L’, y el bit significativo más bajo del carácter ‘a’ se pierde durante la comunicación. El receptor verá la matriz que representa la cadena «M’mmert»., La suma de comprobación para esta nueva cadena sigue siendo 210, pero el resultado es obviamente incorrecto, solo después de cambiar dos bits. Incluso si hubiéramos utilizado una suma de verificación de cuatro bytes, no habríamos detectado este error de transmisión. Así que calcular una suma de comprobación puede ser un método simple para detectar errores, pero no da mucha más protección que el bit de paridad, independientemente de la longitud de la suma de comprobación.

la idea detrás de un cálculo de valor de verificación es simple. Utilice una función F (bval,cval) que ingrese un byte de datos y un valor de comprobación y genere un valor de comprobación recalculado., De hecho, los cálculos de suma de comprobación descritos anteriormente se pueden definir de esta manera. Nuestro ejemplo de suma de comprobación de un byte podría haberse calculado con la siguiente función (en lenguaje C) que llamamos repetidamente para cada byte en la cadena de entrada. El valor inicial para cval es 0.

int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256;}

La idea detrás de cálculo del CRC es mirar los datos como un gran número binario. Este número se divide por un cierto valor y el resto del cálculo se llama CRC., Dividir en el cálculo CRC al principio parece costar una gran cantidad de potencia de cálculo, pero se puede realizar muy rápidamente si utilizamos un método similar al aprendido en la escuela. Como ejemplo calcularemos el resto para el carácter ‘m’—que es 1101101 en notación binaria—dividiéndolo por 19 o 10011. Tenga en cuenta que 19 es un número impar. Esto es necesario, como veremos más adelante. Consulte sus libros escolares ya que el método de cálculo binario aquí no es muy diferente del método decimal que aprendió cuando era joven. Puede parecer un poco extraño., También las notaciones difieren entre países, pero el método es similar.

 1 0 1 = 5 -------------1 0 0 1 1 / 1 1 0 1 1 0 1 1 0 0 1 1 | | --------- | | 1 0 0 0 0 | 0 0 0 0 0 | --------- | 1 0 0 0 0 1 1 0 0 1 1 --------- 1 1 1 0 = 14 = remainder

Con decimales en los cálculos puede comprobar rápidamente que 109 dividido por 19 da un cociente de 5 con 14 como el resto. Pero lo que también vemos en el esquema es que cada bit extra para comprobar solo cuesta una comparación binaria y en el 50% de los casos una resta binaria., Puede aumentar fácilmente el número de bits de la cadena de datos de prueba—por ejemplo, a 56 bits si usamos nuestro valor de ejemplo «Lammert»—y el resultado se puede calcular con 56 comparaciones binarias y un promedio de 28 sustracciones binarias. Esto se puede implementar en hardware directamente con muy pocos transistores involucrados. También los Algoritmos de software pueden ser muy eficientes.

para los cálculos de CRC, no se utiliza una resta normal, pero todos los cálculos se realizan módulo 2. En esa situación ignoras carry bits y en efecto la resta será igual a una operación or exclusiva., Esto parece extraño, el resto resultante tiene un valor diferente, pero desde un punto de vista algebraico la funcionalidad es igual. Una discusión de esto necesitaría conocimiento de nivel universitario de la teoría de campos algebraicos y supongo que la mayoría de los lectores no están interesados en esto. Por favor mire al final de este documento los libros que discuten esto en detalle.

Ahora tenemos un método de cálculo CRC que es implementable tanto en hardware como en software y también tiene una sensación más aleatoria que calcular una suma de verificación ordinaria. Pero, ¿cómo funcionará en la práctica cuando uno o más bits están mal?, Si elegimos el divisor-19 en nuestro ejemplo-para ser un número impar, no necesita matemáticas de alto nivel para ver que se detectarán todos los errores de bits. Esto se debe a que cada error de bit permitirá que el dividendo cambie con una potencia de 2. Si, por ejemplo, el bit n cambia de 0 a 1, el valor del dividendo aumentará con 2n. Por otro lado, si el bit n cambia de 1 a 0, el valor del dividendo disminuirá con 2n. Porque no se puede dividir cualquier potencia de dos por un número impar, el resto del cálculo del CRC va a cambiar y el error no pasará desapercibido.,

la segunda situación que queremos detectar es cuando dos bits individuales cambian en los datos. Esto requiere algunas matemáticas que se pueden leer en el libro de Tanenbaum mencionado a continuación. Debe seleccionar su divisor con mucho cuidado para asegurarse de que, independientemente de la distancia entre los dos bits incorrectos, siempre los detectará. Se sabe, que los valores comúnmente utilizados 0x8005 y 0x1021 de los cálculos CRC16 y CRC-CCITT funcionan muy bien en este tema., Tenga en cuenta que otros valores podrían o no, y no puede calcular fácilmente qué valor divisor es apropiado para detectar errores de dos bits y cuál no. confíe en una extensa investigación matemática sobre este tema realizada hace algunas décadas por matemáticos altamente calificados y use los valores que estas personas obtuvieron.

además, con nuestro cálculo CRC queremos detectar todos los errores donde cambia un número impar de bits. Esto se puede lograr mediante el uso de un divisor con un número par de bits establecidos. Usando Modulo 2 mathematics puedes mostrar que todos los errores con un número impar de bits son detectados., Como he dicho antes, en el módulo 2 matemáticas la función de resta es reemplazada por el or exclusivo. Hay cuatro posibles operaciones XOR.

0 XOR 0 => 0 even => even0 XOR 1 => 1 odd => odd1 XOR 0 => 1 odd => odd1 XOR 1 => 0 even => even

vemos que para todas las combinaciones de valores de los bits, la rareza de la expresión sigue siendo el mismo. Al elegir un divisor con un número par de bits, la rareza del resto es igual a la rareza del dividendo. Por lo tanto, si la rareza del dividendo cambia porque cambia un número impar de bits, el resto también cambiará., Así que todos los errores que cambian un número impar de bits serán detectados por un cálculo CRC que se realiza con un divisor tal. Es posible que haya visto que los valores de divisor comúnmente utilizados 0x8005 y 0x1021 en realidad tienen un número impar de bits, y no incluso como se indica aquí. Esto se debe a que dentro del algoritmo hay un bit extra «oculto» 216 que hace que el valor real del divisor utilizado sea 0x18005 y 0x11021 dentro del algoritmo.,

Por último, pero no menos importante, queremos detectar todos los errores de ráfaga con nuestro cálculo CRC con una longitud máxima para ser detectados, y todos los errores de ráfaga más largos para ser detectados con una alta probabilidad. Un error de ráfaga es bastante común en las comunicaciones. Es el tipo de error que ocurre debido a un rayo, conmutación de relés, etc. donde durante un período Pequeño todos los bits se establecen en uno., Para entender realmente esto, también necesita tener algún conocimiento del álgebra del módulo 2, así que acepte que con un divisor de 16 bits podrá detectar todas las ráfagas con una longitud máxima de 16 bits, y todas las ráfagas más largas con al menos 99.997% de certeza.

en un enfoque matemático puro, el cálculo CRC se escribe como cálculos polinómicos. El valor del divisor a menudo no se describe como un número binario, sino como un polinomio de cierto orden. En la vida normal algunos polinomios se utilizan con más frecuencia que otros., Los tres utilizados en el cálculo de CRC en línea en esta página son el CRC16 y CRC-CCITT de 16 bits de ancho y el CRC32 de 32 bits de ancho. Este último es probablemente el más utilizado ahora, porque entre otros es el generador de CRC para toda la verificación y validación del tráfico de red.

para los tres tipos de cálculos CRC tengo una biblioteca de software libre disponible. El programa de prueba se puede utilizar directamente para probar archivos o cadenas. También puede mirar los códigos fuente e integrar estas rutinas CRC en su propio programa., Tenga en cuenta los valores de inicialización del cálculo CRC y el posible procesamiento posterior necesario como voltear bits. Si no hace esto, puede obtener resultados diferentes a los de otras implementaciones de CRC. Todo este pre y post-procesamiento se realiza en el programa de ejemplo por lo que no debería ser difícil hacer que su propia implementación funcione. Una prueba común es calcular el valor CRC para la cadena ASCII «123456789»., Si el resultado de su rutina coincide con el resultado del programa de prueba o el resultado en este sitio web, su implementación está funcionando y es compatible con la mayoría de las demás implementaciones.

solo como referencia las funciones polinómicas para los cálculos CRC más comunes. Recuerde que el término de orden más alto del polinomio (x16 o x32) no está presente en la representación del número binario, sino implicado por el propio algoritmo.,