Una verificación de redundancia cíclica ( CRC ) es un código de detección de errores comúnmente utilizado en redes digitales y dispositivos de almacenamiento para detectar cambios accidentales en datos digitales. A los bloques de datos que ingresan a estos sistemas se les asigna un breve valor de verificación , basado en el resto de una división polinomial de sus contenidos. 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 llaman así porque el valor de verificación (verificación de datos) es una redundancia (amplía 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 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 una función hash .
Los CRC se basan en la teoría de los códigos de corrección de errores cíclicos . W. Wesley Peterson propuso por primera vez en 1961 el uso de códigos cíclicos sistemáticos , que codifican mensajes agregando un valor de verificación de longitud fija, con el fin de detectar errores en las redes de comunicación. [2] Los códigos cíclicos no solo son fáciles de implementar 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 los 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 óptico y magnético. Típicamente una nEl CRC de -bit 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 llamado polinomio generador . Este polinomio se convierte en el divisor en una división larga de polinomios , que toma el mensaje como dividendo y en la que se descarta el cociente y el resto se convierte en el resultado. La advertencia importante es que los coeficientes polinómicos 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 bit a bit (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, y coinciden cómodamente con la arquitectura de la computadora.
Un CRC se denomina CRC de n bits cuando su valor de comprobación tiene una longitud de n bits. Para un n dado , son posibles múltiples CRC, cada uno con un polinomio diferente. Tal polinomio tiene el mayor grado n , 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 de polinomios eliminan el MSB o el LSB , ya que siempre son 1. El CRC y el polinomio asociado suelen tener un nombre de la forma CRC- n -XXX como se muestra en la siguiente tabla .