Una verificación de redundancia cíclica ( CRC ) es un código de detección de errores que se usa comúnmente en redes digitales y dispositivos de almacenamiento para detectar cambios accidentales en los datos sin procesar. Los bloques de datos que ingresan a estos sistemas obtienen un valor de verificación breve adjunto, basado en el resto de una división polinómica de su contenido. En la recuperación, el cálculo se repite y, en caso de que los valores de verificación no coincidan, se pueden tomar medidas correctivas contra la corrupción de datos. Los CRC se pueden utilizar para la corrección de errores (ver filtros de bits ). [1]
Los CRC se denominan así porque el valor de verificación (verificación de datos) es una redundancia (expande el mensaje sin agregar información ) y el algoritmo se basa en códigos cíclicos . Los CRC son populares porque son simples de implementar en hardware binario , fáciles de analizar matemáticamente y particularmente buenos para detectar errores comunes causados por el ruido en los canales de transmisión. Debido a que el valor de verificación tiene una longitud fija, la función que lo genera se usa ocasionalmente como función hash .
Los CRC se basan en la teoría de los códigos de corrección de errores cíclicos . El uso de códigos cíclicos sistemáticos , que codifican mensajes agregando un valor de verificación de longitud fija, con el propósito de detectar errores en las redes de comunicación, fue propuesto por primera vez por W. Wesley Peterson en 1961. [2] Los códigos cíclicos no solo son simples de implementan, pero tienen la ventaja de ser especialmente adecuados para la detección de errores de ráfaga : secuencias contiguas de símbolos de datos erróneos en mensajes. Esto es importante porque los errores de ráfaga son errores de transmisión comunes en muchos canales de comunicación , incluidos los dispositivos de almacenamiento magnético y óptico. Normalmente una n-bit CRC aplicado a un bloque de datos de longitud arbitraria detectará cualquier ráfaga de error única que no supere los n bits, y la fracción de todas las ráfagas de error más largas que detectará es (1 - 2 - n ) .
La especificación de un código CRC requiere la definición de un polinomio generador . Este polinomio se convierte en el divisor de un polinomio de división larga , que toma el mensaje como dividendo y en el que se descarta el cociente y el resto se convierte en el resultado. La advertencia importante es que los coeficientes polinomiales se calculan de acuerdo con la aritmética de un campo finito , por lo que la operación de suma siempre se puede realizar en paralelo a los bits (no hay acarreo entre dígitos).
En la práctica, todos los CRC de uso común emplean el campo de Galois , o más simplemente un campo finito, de dos elementos, GF (2) . Los dos elementos generalmente se denominan 0 y 1, que coinciden cómodamente con la arquitectura de la computadora.
A CRC se denomina n bits CRC cuando su valor de comprobación es n bits de longitud. Para un n dado , son posibles múltiples CRC, cada uno con un polinomio diferente. Dicho polinomio tiene el grado n más alto , lo que significa que tiene n + 1 términos. En otras palabras, el polinomio tiene una longitud de n + 1 ; su codificación requiere n + 1 bits. Tenga en cuenta que la mayoría de las especificaciones polinomiales eliminan MSB o LSB , ya que siempre son 1. El CRC y el polinomio asociado generalmente tienen un nombre de la forma CRC- n -XXX como en la tabla siguiente.