Verificación de redundancia cíclica

Código de detección de errores para detectar cambios de datos

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. Los bloques de datos que ingresan a estos sistemas reciben un breve valor de verificación adjunto, basado en el resto de una división polinómica de su contenido. Al recuperarlos, 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 (consulte filtros de bits ). ^[1]

Los CRC se llaman 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 fáciles 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 .

Introducción

Los CRC se basan en la teoría de los códigos cíclicos de corrección de errores . El uso de códigos cíclicos sistemáticos , que codifican mensajes añadiendo un valor de verificación de longitud fija, con el fin de detectar errores en redes de comunicación, fue propuesto por primera vez por W. Wesley Peterson en 1961. ^[2] Los códigos cíclicos no sólo son fáciles de implementar, pero tienen la ventaja de ser particularmente adecuados para la detección de errores en ráfagas : 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éticos y ópticos. Normalmente, un CRC de n bits aplicado a un bloque de datos de longitud arbitraria detectará cualquier ráfaga de error de no más de n bits, y la fracción de todas las ráfagas de error más largas que detectará es aproximadamente (1 − 2 ^{− n} ) .

La especificación de un código CRC requiere la definición del llamado polinomio generador . Este polinomio se convierte en el divisor en una división larga del polinomio , que toma el mensaje como dividendo y en el que el cociente se descarta y el resto pasa a ser 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 finito de dos elementos, GF(2) . Los dos elementos suelen denominarse 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 verificació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 grado más alto 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 polinómicas eliminan MSB o LSB , ya que siempre son 1. El CRC y el polinomio asociado normalmente tienen un nombre de la forma CRC- n -XXX como se muestra en la siguiente tabla.

El sistema de detección de errores más simple, el bit de paridad , es de hecho un CRC de 1 bit: utiliza el polinomio generador  x + 1 (dos términos), ^[3] y tiene el nombre CRC-1.

Solicitud

Un dispositivo habilitado para CRC calcula una secuencia binaria corta de longitud fija, conocida como valor de verificación o CRC , para cada bloque de datos que se enviará o almacenará y la agrega a los datos, formando una palabra clave .

Cuando se recibe o lee una palabra de código, el dispositivo compara su valor de verificación con uno recién calculado a partir del bloque de datos o, de manera equivalente, realiza un CRC en toda la palabra de código y compara el valor de verificación resultante con una constante residual esperada .

Si los valores CRC no coinciden, entonces el bloque contiene un error de datos.

El dispositivo puede tomar medidas correctivas, como volver a leer el bloque o solicitar que se envíe nuevamente. De lo contrario, se supone que los datos están libres de errores (aunque, con una pequeña probabilidad, pueden contener errores no detectados; esto es inherente a la naturaleza de la verificación de errores). ^[4]

Integridad de los datos

Los CRC están diseñados específicamente para proteger contra tipos comunes de errores en los canales de comunicación, donde pueden proporcionar una garantía rápida y razonable de la integridad de los mensajes entregados. Sin embargo, no son adecuados para proteger contra la alteración intencionada de datos.

En primer lugar, como no existe autenticación, un atacante puede editar un mensaje y volver a calcular el CRC sin que se detecte la sustitución. Cuando se almacenan junto con los datos, las CRC y las funciones hash criptográficas por sí solas no protegen contra la modificación intencional de los datos. Cualquier aplicación que requiera protección contra este tipo de ataques debe utilizar mecanismos de autenticación criptográfica, como códigos de autenticación de mensajes o firmas digitales (que comúnmente se basan en funciones hash criptográficas ).

En segundo lugar, a diferencia de las funciones hash criptográficas, CRC es una función fácilmente reversible, lo que la hace inadecuada para su uso en firmas digitales. ^[5]

En tercer lugar, CRC satisface una relación similar a la de una función lineal (o más exactamente, una función afín ): ^[6]

${\displaystyle \operatorname {CRC} (x\oplus y)=\operatorname {CRC} (x)\oplus \operatorname {CRC} (y)\oplus c}$

donde depende de la longitud de y . Esto también se puede expresar de la siguiente manera, donde y tienen la misma longitud ${\displaystyle c}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$

${\displaystyle \operatorname {CRC} (x\oplus y\oplus z)=\operatorname {CRC} (x)\oplus \operatorname {CRC} (y)\oplus \operatorname {CRC} (z);}$

Como resultado, incluso si el CRC está cifrado con un cifrado de flujo que utiliza XOR como operación de combinación (o modo de cifrado de bloque que efectivamente lo convierte en un cifrado de flujo, como OFB o CFB), tanto el mensaje como el CRC asociado puede manipularse sin conocer la clave de cifrado; Este fue uno de los defectos de diseño más conocidos del protocolo Wired Equivalent Privacy (WEP). ^[7]

Cálculo

Para calcular un CRC binario de n bits, alinee los bits que representan la entrada en una fila y coloque el patrón de ( n + 1 ) bits que representa el divisor del CRC (llamado " polinomio ") debajo del extremo izquierdo de la fila.

En este ejemplo, codificaremos 14 bits de mensaje con un CRC de 3 bits, con un polinomio x ³ + x + 1 . El polinomio se escribe en binario como coeficientes; un polinomio de tercer grado tiene 4 coeficientes ( 1 x ³ + 0 x ² + 1 x + 1 ). En este caso, los coeficientes son 1, 0, 1 y 1. El resultado del cálculo tiene una longitud de 3 bits, por lo que se denomina CRC de 3 bits. Sin embargo, necesitas 4 bits para indicar explícitamente el polinomio.

Comience con el mensaje a codificar:

11010011101100

Primero se rellena con ceros correspondientes a la longitud de bits n del CRC. Esto se hace para que la palabra clave resultante esté en forma sistemática . Aquí está el primer cálculo para calcular un CRC de 3 bits:

11010011101100 000 <--- entrada derecha rellenada con 3 bits1011 <--- divisor (4 bits) = x³ + x + 1------------------01100011101100 000 <--- resultado

El algoritmo actúa sobre los bits directamente encima del divisor en cada paso. El resultado de esa iteración es el XOR bit a bit del divisor polinómico con los bits encima. Los bits que no están por encima del divisor simplemente se copian directamente debajo para ese paso. Luego, el divisor se desplaza hacia la derecha para alinearse con el bit restante más alto en la entrada, y el proceso se repite hasta que el divisor alcanza el extremo derecho de la fila de entrada. Aquí está el cálculo completo:

11010011101100 000 <--- entrada derecha rellenada con 3 bits1011 <--- divisor01100011101100 000 <--- resultado (tenga en cuenta que los primeros cuatro bits son el XOR con el divisor debajo, el resto de los bits no cambian) 1011 <--- divisor...00111011101100 000 101100010111101100 000 101100000001101100 000 <--- tenga en cuenta que el divisor se mueve para alinearse con el siguiente 1 en el dividendo (ya que el cociente de ese paso era cero) 1011 (en otras palabras, no necesariamente se mueve un bit por iteración)00000000110100 000 101100000000011000 000 101100000000001110 000 101100000000000101 000 101 1-----------------00000000000000 100 <--- resto (3 bits). El algoritmo de división se detiene aquí ya que el dividendo es igual a cero.

Dado que el bit divisor más a la izquierda puso a cero cada bit de entrada que tocó, cuando este proceso termina, los únicos bits en la fila de entrada que pueden ser distintos de cero son los n bits en el extremo derecho de la fila. Estos n bits son el resto del paso de división y también serán el valor de la función CRC (a menos que la especificación CRC elegida requiera algún posprocesamiento).

La validez de un mensaje recibido se puede verificar fácilmente realizando nuevamente el cálculo anterior, esta vez agregando el valor de verificación en lugar de ceros. El resto debe ser igual a cero si no hay errores detectables.

11010011101100 100 <--- entrada con valor de verificación1011 <--- divisor01100011101100 100 <--- resultado 1011 <--- divisor...00111011101100 100......00000000001110 100 101100000000000101 100 101 1------------------00000000000000 000 <--- resto

El siguiente código Python describe una función que devolverá el resto CRC inicial para una entrada y un polinomio elegidos, con 1 o 0 como relleno inicial. Tenga en cuenta que este código funciona con entradas de cadenas en lugar de números sin formato:

def  crc_remainder ( input_bitstring ,  polynomial_bitstring ,  inicial_filler ): """Calcule el CRC restante de una cadena de bits usando un polinomio elegido.  inicial_filler debe ser '1' o '0'.  """ polynomial_bitstring = polynomial_bitstring . lstrip ( '0' ) len_input = len ( input_bitstring ) inicial_padding = ( len ( polynomial_bitstring ) - 1 ) * inicial_filler input_padded_array = lista ( input_bitstring + inicial_padding ) mientras que '1' en input_padded_array [: len_input ]: cur_shift = input_padded_array . índice ( '1' ) para i en el rango ( len ( polynomial_bitstring )): input_padded_array [ cur_shift + i ] \ = str ( int ( polynomial_bitstring [ i ] ! = input_padded_array [ cur_shift + i ])) return '' . unirse ( input_padded_array )[ len_input :]                                        def  crc_check ( input_bitstring ,  polynomial_bitstring ,  check_value ): """Calcula la verificación CRC de una cadena de bits usando un polinomio elegido.""" polynomial_bitstring = polynomial_bitstring . lstrip ( '0' ) len_input = len ( input_bitstring ) inicial_padding = check_value input_padded_array = lista ( input_bitstring + inicial_padding ) mientras que '1' en input_padded_array [: len_input ]: cur_shift = input_padded_array . índice ( '1' ) para i en el rango ( len ( polynomial_bitstring )): input_padded_array [ cur_shift + i ] \ = str ( int ( polynomial_bitstring [ i ] ! = input_padded_array [ cur_shift + i ])) return ( '1' no está en ' ' .unirse ( input_padded_array )[ len_input :])                                       

>>> crc_remainder ( '11010011101100' ,  '1011' ,  '0' ) '100' >>> crc_check ( '11010011101100' ,  '1011' ,  '100' ) Verdadero

Matemáticas

El análisis matemático de este proceso similar a una división revela cómo seleccionar un divisor que garantice buenas propiedades de detección de errores. En este análisis, los dígitos de las cadenas de bits se toman como coeficientes de un polinomio en alguna variable x , coeficientes que son elementos del campo finito GF(2) (los enteros módulo 2, es decir, un cero o un uno), en lugar de números más familiares. El conjunto de polinomios binarios es un anillo matemático .

Diseñar polinomios

La selección del polinomio generador es la parte más importante de la implementación del algoritmo CRC. El polinomio debe elegirse para maximizar las capacidades de detección de errores y al mismo tiempo minimizar las probabilidades generales de colisión.

El atributo más importante del polinomio es su longitud (mayor grado (exponente) +1 de cualquier término del polinomio), debido a su influencia directa en la longitud del valor de verificación calculado.

Las longitudes de polinomios más utilizadas son 9 bits (CRC-8), 17 bits (CRC-16), 33 bits (CRC-32) y 65 bits (CRC-64). ^[3]

Un CRC se denomina CRC de n bits cuando su valor de verificación es de n bits. Para un n dado , son posibles múltiples CRC, cada uno con un polinomio diferente. Tal polinomio tiene el grado más alto n y, por lo tanto, n + 1 términos (el polinomio tiene una longitud de n + 1 ). El resto tiene longitud n . El CRC tiene un nombre de la forma CRC- n -XXX.

El diseño del polinomio CRC depende de la longitud total máxima del bloque a proteger (datos + bits CRC), las características de protección contra errores deseadas y el tipo de recursos para implementar el CRC, así como el rendimiento deseado. Un error común es que los "mejores" polinomios CRC se derivan de polinomios irreducibles o de polinomios irreducibles multiplicados por el factor  1 + x , lo que agrega al código la capacidad de detectar todos los errores que afectan a un número impar de bits. ^[8] En realidad, todos los factores descritos anteriormente deberían entrar en la selección del polinomio y pueden conducir a un polinomio reducible. Sin embargo, elegir un polinomio reducible dará como resultado una cierta proporción de errores omitidos, debido a que el anillo de cociente tiene cero divisores .

La ventaja de elegir un polinomio primitivo como generador de un código CRC es que el código resultante tiene una longitud de bloque total máxima en el sentido de que todos los errores de 1 bit dentro de esa longitud de bloque tienen restos diferentes (también llamados síndromes ) y por lo tanto, dado que el El resto es una función lineal del bloque, el código puede detectar todos los errores de 2 bits dentro de esa longitud de bloque. Si es el grado del polinomio generador primitivo, entonces la longitud total máxima del bloque es y el código asociado puede detectar cualquier error de un solo bit o de doble bit. ^[9] Podemos mejorar esta situación. Si usamos el polinomio generador , donde es un polinomio primitivo de grado , entonces la longitud total máxima del bloque es y el código es capaz de detectar errores simples, dobles, triples y cualquier número impar. ${\displaystyle r}$ ${\displaystyle 2^{r}-1}$ ${\displaystyle g(x)=p(x)(1+x)}$ ${\displaystyle p}$ ${\displaystyle r-1}$ ${\displaystyle 2^{r-1}-1}$

Entonces se puede elegir un polinomio que admita otras factorizaciones para equilibrar la longitud total máxima del bloque con un poder de detección de errores deseado. Los códigos BCH son una clase poderosa de tales polinomios. Incluyen los dos ejemplos anteriores. Independientemente de las propiedades de reducibilidad de un polinomio generador de grado  r , si incluye el término "+1", el código podrá detectar patrones de error que están confinados a una ventana de r bits contiguos. Estos patrones se denominan "ráfagas de errores". ${\displaystyle g(x)}$

Especificación

El concepto de CRC como código de detección de errores se complica cuando un implementador o un comité de estándares lo utiliza para diseñar un sistema práctico. Estas son algunas de las complicaciones:

• A veces, una implementación antepone un patrón de bits fijo al flujo de bits que se va a verificar. Esto es útil cuando los errores de sincronización pueden insertar bits 0 delante de un mensaje, una alteración que de otro modo dejaría el valor de verificación sin cambios.
• Por lo general, pero no siempre, una implementación agrega n bits 0 ( siendo n el tamaño del CRC) al flujo de bits que se verificará antes de que ocurra la división polinómica. Dicha adición se demuestra explícitamente en el artículo Cálculo de CRC . Esto tiene la conveniencia de que el resto del flujo de bits original con el valor de verificación agregado es exactamente cero, por lo que el CRC se puede verificar simplemente realizando la división polinómica en el flujo de bits recibido y comparando el resto con cero. Debido a las propiedades asociativas y conmutativas de la operación exclusiva o, las implementaciones prácticas basadas en tablas pueden obtener un resultado numéricamente equivalente a la adición de ceros sin agregar explícitamente ningún cero, mediante el uso de un algoritmo equivalente ^[8] más rápido que combina el flujo de bits del mensaje con la corriente se desplaza fuera del registro CRC.
• A veces, una implementación OR exclusiva aplica un patrón de bits fijo al resto de la división polinómica.
• Orden de bits: algunos esquemas ven el bit de orden inferior de cada byte como "primero", que luego, durante la división polinómica, significa "más a la izquierda", lo que es contrario a nuestra comprensión habitual de "orden inferior". Esta convención tiene sentido cuando las transmisiones por puerto serie se verifican mediante CRC en el hardware, porque algunas convenciones generalizadas de transmisión por puerto serie transmiten los bytes con el bit menos significativo primero.
• Orden de los bytes : con los CRC de varios bytes, puede haber confusión sobre si el byte transmitido primero (o almacenado en el byte de memoria con la dirección más baja) es el byte menos significativo (LSB) o el byte más significativo (MSB). Por ejemplo, algunos esquemas CRC de 16 bits intercambian los bytes del valor de verificación.
• Omisión del bit de orden superior del polinomio divisor: dado que el bit de orden superior es siempre 1, y dado que un CRC de n bits debe definirse mediante un divisor de ( n + 1 ) bits que desborda un registro de n bits , algunos escritores suponen que es innecesario mencionar el bit de orden superior del divisor.
• Omisión del bit de orden inferior del polinomio divisor: dado que el bit de orden inferior es siempre 1, autores como Philip Koopman representan polinomios con su bit de orden superior intacto, pero sin el bit de orden inferior (el término o 1) . Esta convención codifica el polinomio completo con su grado en un número entero. ${\displaystyle x^{0}}$

Estas complicaciones significan que hay tres formas comunes de expresar un polinomio como un número entero: las dos primeras, que son imágenes especulares en binario, son las constantes que se encuentran en el código; el tercero es el número que se encuentra en los artículos de Koopman. En cada caso, se omite un término. Entonces el polinomio se puede transcribir como: ${\displaystyle x^{4}+x+1}$

• 0x3 = 0b0011, que representa (primer código MSB) ${\displaystyle x^{4}+(0x^{3}+0x^{2}+1x^{1}+1x^{0})}$
• 0xC = 0b1100, que representa (primer código LSB) ${\displaystyle (1x^{0}+1x^{1}+0x^{2}+0x^{3})+x^{4}}$
• 0x9 = 0b1001, que representa (notación Koopman) ${\displaystyle (1x^{4}+0x^{3}+0x^{2}+1x^{1})+x^{0}}$

En la siguiente tabla se muestran como:

Ofuscación

Los CRC en protocolos propietarios pueden ofuscarse mediante el uso de un valor inicial no trivial y un XOR final, pero estas técnicas no añaden solidez criptográfica al algoritmo y pueden someterse a ingeniería inversa utilizando métodos sencillos. ^[10]

Estándares y uso común.

Se han incorporado a las normas técnicas numerosas variedades de controles de redundancia cíclica . De ninguna manera un algoritmo, o uno de cada grado, se adapta a todos los propósitos; Koopman y Chakravarty recomiendan seleccionar un polinomio según los requisitos de la aplicación y la distribución esperada de longitudes de mensajes. ^[11] El número de CRC distintos en uso ha confundido a los desarrolladores, una situación que los autores han tratado de abordar. ^[8] Hay tres polinomios reportados para CRC-12, ^[11] veintidós definiciones contradictorias de CRC-16 y siete de CRC-32. ^[12]

Los polinomios comúnmente aplicados no son los más eficientes posibles. Desde 1993, Koopman, Castagnoli y otros han estudiado el espacio de polinomios entre 3 y 64 bits de tamaño, ^{[11] [13] [14] [15]} encontrando ejemplos que tienen un rendimiento mucho mejor (en términos de distancia de Hamming para un determinado tamaño del mensaje) que los polinomios de protocolos anteriores, y publicar los mejores de ellos con el objetivo de mejorar la capacidad de detección de errores de futuros estándares. ^[14] En particular, iSCSI y SCTP han adoptado uno de los hallazgos de esta investigación, el polinomio CRC-32C (Castagnoli).

El diseño del polinomio de 32 bits más comúnmente utilizado por los organismos de normalización, CRC-32-IEEE, fue el resultado de un esfuerzo conjunto del Laboratorio de Roma y la División de Sistemas Electrónicos de la Fuerza Aérea realizado por Joseph Hammond, James Brown y Shyan-Shiang Liu. del Instituto de Tecnología de Georgia y Kenneth Brayer de Mitre Corporation . Las primeras apariciones conocidas del polinomio de 32 bits se produjeron en sus publicaciones de 1975: Informe técnico 2956 de Brayer para Mitre, publicado en enero y lanzado para su difusión pública a través de DTIC en agosto, ^[16] y el informe de Hammond, Brown y Liu para Roma. Laboratorio, publicado en mayo. ^[17] Ambos informes contenían contribuciones del otro equipo. Durante diciembre de 1975, Brayer y Hammond presentaron su trabajo en un artículo en la Conferencia Nacional de Telecomunicaciones IEEE: el polinomio IEEE CRC-32 es el polinomio generador de un código Hamming y fue seleccionado por su rendimiento de detección de errores. ^[18] Aun así, el polinomio Castagnoli CRC-32C utilizado en iSCSI o SCTP iguala su rendimiento en mensajes de 58 bits a 131 kbits y lo supera en varios rangos de tamaño, incluidos los dos tamaños más comunes de paquetes de Internet. ^[14] El estándar ITU-T G.hn también usa CRC-32C para detectar errores en la carga útil (aunque usa CRC-16-CCITT para encabezados PHY ).

El cálculo CRC-32C se implementa en hardware como una operación ( CRC32) del conjunto de instrucciones SSE4.2 , introducido por primera vez en la microarquitectura Nehalem de los procesadores Intel . La arquitectura ARM AArch64 también proporciona aceleración de hardware para operaciones CRC-32 y CRC-32C.

Representaciones polinomiales

La siguiente tabla enumera solo los polinomios de los distintos algoritmos en uso. Las variaciones de un protocolo particular pueden imponer una preinversión, una postinversión y un orden de bits invertido como se describe anteriormente. Por ejemplo, el CRC32 usado en Gzip y Bzip2 usa el mismo polinomio, pero Gzip emplea ordenamiento de bits inverso, mientras que Bzip2 no. ^[12] Tenga en cuenta que incluso los polinomios de paridad en GF(2) con grado mayor que 1 nunca son primitivos. Incluso el polinomio de paridad marcado como primitivo en esta tabla representa un polinomio primitivo multiplicado por . El bit más significativo de un polinomio es siempre 1 y no se muestra en las representaciones hexadecimales. ${\displaystyle \left(x+1\right)}$

Implementaciones

• Implementación de CRC32 en GNU Radio hasta 3.6.1 (ca. 2012)
• Código de clase C para el cálculo de la suma de comprobación CRC con muchos CRC diferentes para elegir

catálogos CRC

• Catálogo de algoritmos CRC parametrizados
• Zoológico polinómico CRC

Ver también

• Suma de comprobación
• Cálculo de verificaciones de redundancia cíclica.
• Seguridad de información
• Lista de algoritmos de suma de comprobación
• Lista de funciones hash
• LRC
• Matemáticas de los controles de redundancia cíclica.
• Verificación de archivos sencilla

Referencias

1. "Un algoritmo para corregir errores en las comprobaciones de redundancia cíclica". drdobbs.com . Archivado desde el original el 20 de julio de 2017 . Consultado el 28 de junio de 2017 .
2. Peterson, WW; Brown, DT (enero de 1961). "Códigos cíclicos para la detección de errores". Actas del IRE . 49 (1): 228–235. doi :10.1109/JRPROC.1961.287814. S2CID  51666741.
3. Ergen, Mustafa (21 de enero de 2008). "2.3.3 Codificación de detección de errores". Banda ancha móvil . Saltador . págs. 29 y 30. doi :10.1007/978-0-387-68192-4_2. ISBN 978-0-387-68192-4.
4. Ritter, Terry (febrero de 1986). "El gran misterio de la CDN". Diario del Dr. Dobb . 11 (2): 26–34, 76–83. Archivado desde el original el 16 de abril de 2009 . Consultado el 21 de mayo de 2009 .
5. Stigge, Martín; Plötz, Henryk; Müller, Lobo; Redlich, Jens-Peter (mayo de 2006). "Revertir la CRC: teoría y práctica" (PDF) . Universidad Humboldt de Berlín. pag. 17. SAR-PR-2006-05. Archivado desde el original (PDF) el 19 de julio de 2011 . Consultado el 4 de febrero de 2011 . Los métodos presentados ofrecen una manera muy fácil y eficiente de modificar sus datos para que se calculen según el CRC que desea o al menos conoce de antemano.
6. "diseño de algoritmos: ¿por qué se dice que CRC es lineal?". Intercambio de pila de criptografía . Consultado el 5 de mayo de 2019 .
7. Cam-Winget, Nancy; Housley, Russ; Wagner, David; Walker, Jesse (mayo de 2003). "Defectos de seguridad en los protocolos de enlace de datos 802.11" (PDF) . Comunicaciones de la ACM . 46 (5): 35–39. CiteSeerX 10.1.1.14.8775 . doi :10.1145/769800.769823. S2CID  3132937. Archivado (PDF) desde el original el 26 de mayo de 2013 . Consultado el 1 de noviembre de 2017 . 
8. Williams, Ross N. (24 de septiembre de 1996). "Una guía sencilla para los algoritmos de detección de errores CRC V3.0". Archivado desde el original el 2 de abril de 2018 . Consultado el 23 de mayo de 2019 .
9. Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 22.4 Redundancia cíclica y otras sumas de verificación". Recetas numéricas: el arte de la informática científica (3ª ed.). Prensa de la Universidad de Cambridge. ISBN 978-0-521-88068-8. Archivado desde el original el 11 de agosto de 2011 . Consultado el 18 de agosto de 2011 .
10. Ewing, Gregory C. (marzo de 2010). "Ingeniería inversa de un algoritmo CRC". Christchurch: Universidad de Canterbury. Archivado desde el original el 7 de agosto de 2011 . Consultado el 26 de julio de 2011 .
11. Koopman, Felipe; Chakravarty, Tridib (junio de 2004). "Selección de polinomio de código de redundancia cíclica (CRC) para redes integradas". Conferencia internacional sobre sistemas y redes confiables, 2004 (PDF) . págs. 145-154. CiteSeerX 10.1.1.648.9080 . doi :10.1109/DSN.2004.1311885. ISBN  978-0-7695-2052-0. S2CID  793862. Archivado (PDF) desde el original el 11 de septiembre de 2011 . Consultado el 14 de enero de 2011 .
12. Cook, Greg (15 de agosto de 2020). "Catálogo de algoritmos CRC parametrizados". Archivado desde el original el 1 de agosto de 2020 . Consultado el 18 de septiembre de 2020 .
13. Castagnoli, G.; Bräuer, S.; Herrmann, M. (junio de 1993). "Optimización de códigos de verificación de redundancia cíclica con 24 y 32 bits de paridad". Transacciones IEEE sobre Comunicaciones . 41 (6): 883–892. doi : 10.1109/26.231911.
14. Koopman, Philip (julio de 2002). "Códigos de redundancia cíclica de 32 bits para aplicaciones de Internet". Actas de la Conferencia internacional sobre sistemas y redes confiables (PDF) . págs. 459–468. CiteSeerX 10.1.1.11.8323 . doi :10.1109/DSN.2002.1028931. ISBN  978-0-7695-1597-7. S2CID  14775606. Archivado (PDF) desde el original el 16 de septiembre de 2012 . Consultado el 14 de enero de 2011 .
15. Koopman, Philip (21 de enero de 2016). "Mejores polinomios CRC". Universidad de Carnegie mellon. Archivado desde el original el 20 de enero de 2016 . Consultado el 26 de enero de 2016 .
16. Brayer, Kenneth (agosto de 1975). Evaluación de polinomios de 32 grados en la detección de errores en los patrones de error SATIN IV Autovon (Reporte). Servicio Nacional de Información Técnica . ADA014825. Archivado desde el original el 31 de diciembre de 2021 . Consultado el 31 de diciembre de 2021 .
17. Hammond, Joseph L. Jr.; Marrón, James E.; Liu, Shyan-Shiang (1975). "Desarrollo de un modelo de error de transmisión y un modelo de control de errores". Informe técnico N de Sti/Recon de la NASA (publicado en mayo de 1975). 76 : 15344. Código bibliográfico : 1975STIN...7615344H. ADA013939. Archivado desde el original el 31 de diciembre de 2021 . Consultado el 31 de diciembre de 2021 .
18. Brayer, Kenneth; Hammond, Joseph L. Jr. (diciembre de 1975). Evaluación del desempeño del polinomio de detección de errores en el canal AUTOVON. NTC 75: Conferencia Nacional de Telecomunicaciones, 1 al 3 de diciembre de 1975, Nueva Orleans, Luisiana. vol. 1. Instituto de Ingenieros Eléctricos y Electrónicos. págs. 8-21-5. Código Bib : 1975ntc.....1....8B. OCLC  32688603. 75 CH 1015-7 CSCB.
19. Los CRC con paridad par detectan cualquier número impar de errores de bits, a expensas de una distancia de martillo más baja para cargas útiles largas. Tenga en cuenta que la paridad se calcula sobre todo el polinomio generador, incluido el 1 implícito al principio o al final. Por ejemplo, la representación completa de CRC-1 es 0x3, que tiene dos bits 1. Por tanto, su paridad es pareja.
20. "Zoológico CRC de 32 bits". usuarios.ece.cmu.edu . Archivado desde el original el 19 de marzo de 2018 . Consultado el 5 de noviembre de 2017 .
21. Carga útil significa longitud exclusiva del campo CRC. Una distancia de Hamming de d significa que  se pueden detectar errores de d − 1 bit y  se pueden corregir errores de ⌊( d − 1)/2⌋ bits.
22. siempre se logra para mensajes arbitrariamente largos
23. ETSI TS 100 909 (PDF) . V8.9.0. Sophia Antipolis, Francia: Instituto Europeo de Normas de Telecomunicaciones. Enero de 2005. Archivado (PDF) desde el original el 17 de abril de 2018 . Consultado el 21 de octubre de 2016 .
24. "Zoológico CRC de 3 bits". usuarios.ece.cmu.edu . Archivado desde el original el 7 de abril de 2018 . Consultado el 19 de enero de 2018 .
25. Protocolo RFID UHF Clase 1 Generación 2 (PDF) . 1.2.0. EPCglobal . 23 de octubre de 2008. p. 35. Archivado (PDF) desde el original el 19 de marzo de 2012 . Consultado el 4 de julio de 2012 .(Tabla 6.12)
26. Estándar de capa física para sistemas de espectro ensanchado cdma2000 (PDF) . Revisión D versión 2.0. Proyecto de asociación de tercera generación 2. Octubre de 2005. págs. 2–89–2–92. Archivado desde el original (PDF) el 16 de noviembre de 2013 . Consultado el 14 de octubre de 2013 .
27. "11. Estrategia de corrección de errores". ETSI EN 300 751 (PDF) . V1.2.1. Sophia Antipolis, Francia: Instituto Europeo de Normas de Telecomunicaciones. Enero de 2003. págs. 67–8. Archivado (PDF) desde el original el 28 de diciembre de 2015 . Consultado el 26 de enero de 2016 .
28. "Zoológico CRC de 6 bits". usuarios.ece.cmu.edu . Archivado desde el original el 7 de abril de 2018 . Consultado el 19 de enero de 2018 .
29. Chakravarty, Tridib (diciembre de 2001). Rendimiento de códigos de redundancia cíclica para redes integradas (PDF) (Tesis). Philip Koopman, asesor. Universidad de Carnegie mellon. págs.5, 18. Archivado (PDF) desde el original el 1 de enero de 2014 . Consultado el 8 de julio de 2013 .
30. "5.1.4 Codificador CRC-8 (solo para transmisiones en paquetes)". EN 302 307 (PDF) . V1.3.1. Sophia Antipolis, Francia: Instituto Europeo de Normas de Telecomunicaciones. Marzo de 2013. p. 17. Archivado (PDF) desde el original el 30 de agosto de 2017 . Consultado el 29 de julio de 2016 .
31. "Zoológico CRC de 8 bits". usuarios.ece.cmu.edu . Archivado desde el original el 7 de abril de 2018 . Consultado el 19 de enero de 2018 .
32. "7.2.1.2 Cálculo de CRC polinómico 0x2F de 8 bits". Especificación de Rutinas CRC (PDF) . 4.2.2. Múnich: AUTOSAR. 22 de julio de 2015. p. 24. Archivado desde el original (PDF) el 24 de julio de 2016 . Consultado el 24 de julio de 2016 .
33. "5.1.1.8 Campo de verificación de redundancia cíclica (CRC-8 / CRC-16)". Especificación del perfil de seguridad de openSAFETY: Propuesta preliminar de trabajo 304 de EPSG. 1.4.0. Berlín: Grupo de estandarización Ethernet POWERLINK. 13 de marzo de 2013. p. 42. Archivado desde el original el 12 de agosto de 2017 . Consultado el 22 de julio de 2016 .
34. "B.7.1.1 Generación HEC". Especificación del sistema Bluetooth. vol. 2. SEÑAL Bluetooth. 2 de diciembre de 2014. págs. 144–5. Archivado desde el original el 26 de marzo de 2015 . Consultado el 20 de octubre de 2014 .
35. Whitfield, Harry (24 de abril de 2001). "XFCN para cálculos de verificación de redundancia cíclica". Archivado desde el original el 25 de mayo de 2005.
36. Richardson, Andrew (17 de marzo de 2005). Manual de WCDMA. Prensa de la Universidad de Cambridge. pag. 223.ISBN _ 978-0-521-82815-4.
37. Especificación del protocolo FlexRay . 3.0.1. Consorcio Flexray. Octubre de 2010. p. 114.(4.2.8 CRC de encabezado (11 bits))
38. Pérez, A. (1983). "Cálculos CRC por bytes". Micro IEEE . 3 (3): 40–50. doi :10.1109/MM.1983.291120. S2CID  206471618.
39. Ramabadrán, TV; Gaitonde, SS (1988). "Un tutorial sobre cálculos CRC". Micro IEEE . 8 (4): 62–75. doi :10.1109/40.7773. S2CID  10216862.
40. "Decodificación de datos de radio de onda larga utilizando HC11 y un MC3371" (PDF) . Semiconductores de escala libre. 2004. AN1597/D. Archivado desde el original (PDF) el 24 de septiembre de 2015.
41. Ely, SR; Wright, DT (marzo de 1982). LF Radio-Data: especificación de transmisiones experimentales de la BBC 1982 (PDF) . Departamento de Investigación, División de Ingeniería, The British Broadcasting Corporation. pag. 9. Archivado (PDF) desde el original el 12 de octubre de 2013 . Consultado el 11 de octubre de 2013 .
42. Comprobación de redundancia cíclica (CRC): hoja de datos del componente PSoC Creator ™. Semiconductor de ciprés. 20 de febrero de 2013. p. 4. Archivado desde el original el 2 de febrero de 2016 . Consultado el 26 de enero de 2016 .
43. "Comprobación de redundancia cíclica (CRC) en tramas CAN". CAN en Automatización . Archivado desde el original el 1 de febrero de 2016 . Consultado el 26 de enero de 2016 .
44. "3.2.3 Codificación y comprobación de errores". Un estándar de señalización para sistemas de radio móviles terrestres privados troncalizados (MPT 1327) (PDF) (3ª ed.). Ofcom . Junio ​​de 1997. pág. 3. Archivado (PDF) desde el original el 14 de julio de 2012 . Consultado el 16 de julio de 2012 .
45. Rehmann, Alberto; Mestre, José D. (febrero de 1995). "Informe de prueba preliminar del sistema de informes y comunicaciones de aerolíneas VHF de enlace de datos aire-tierra (ACARS)" (PDF) . Centro Técnico de la Autoridad Federal de Aviación. pag. 5. Archivado desde el original (PDF) el 2 de agosto de 2012 . Consultado el 7 de julio de 2012 .
46. "6.2.5 Control de errores". ETSI EN 300 175-3 (PDF) . V2.5.1. Sophia Antipolis, Francia: Instituto Europeo de Normas de Telecomunicaciones. Agosto de 2013. págs. 99, 101. Archivado (PDF) desde el original el 1 de julio de 2015 . Consultado el 26 de enero de 2016 .
47. Thaler, Pat (28 de agosto de 2003). "Selección de polinomio CRC de 16 bits" (PDF) . INCITS T10. Archivado (PDF) desde el original el 28 de julio de 2011 . Consultado el 11 de agosto de 2009 .
48. "8.8.4 Comprobar octeto (FCS)". Piezas normativas de especificación PROFIBUS (PDF) . 1.0. vol. 9. Profibus Internacional. Marzo de 1998. p. 906. Archivado desde el original (PDF) el 16 de noviembre de 2008 . Consultado el 9 de julio de 2016 .
49. CAN con especificación de velocidad de datos flexible (PDF) . 1.0. Robert Bosch GmbH. 17 de abril de 2012. pág. 13. Archivado desde el original (PDF) el 22 de agosto de 2013.(3.2.1 MARCO DE DATOS)
50. "Manual del programador del sistema operativo OS-9". roug.org . Archivado desde el original el 17 de julio de 2018 . Consultado el 17 de julio de 2018 .
51. Koopman, Philip P. (20 de mayo de 2018). "Zoológico CRC de 24 bits". usuarios.ece.cmu.edu . Archivado desde el original el 7 de abril de 2018 . Consultado el 19 de enero de 2018 .
52. "cksum". pubs.opengroup.org . Archivado desde el original el 18 de julio de 2018 . Consultado el 27 de junio de 2017 .
53. Boutell, Thomas; Randers-Pehrson, Glenn; et al. (14 de julio de 1998). "Especificación PNG (Gráficos de red portátiles), versión 1.2". Libpng.org. Archivado desde el original el 3 de septiembre de 2011 . Consultado el 3 de febrero de 2011 .
54. Introducción a AIXM (PDF) . 4.5. Organización Europea para la Seguridad de la Navegación Aérea . 20 de marzo de 2006. Archivado (PDF) desde el original el 20 de noviembre de 2018 . Consultado el 3 de febrero de 2019 .
55. ETSI TS 100909 Archivado el 17 de abril de 2018 en Wayback Machine versión 8.9.0 (enero de 2005), Sección 4.1.2 a
56. Gammel, Berndt M. (31 de octubre de 2005). Documentación de Matpack: Cripto – Códigos. Matpack.de. Archivado desde el original el 25 de agosto de 2013 . Consultado el 21 de abril de 2013 .(Nota: MpCRC.html se incluye con el código fuente del software comprimido Matpack, en /html/LibDoc/Crypto)
57. Geremia, Patrick (abril de 1999). "Cálculo de verificación de redundancia cíclica: una implementación que utiliza TMS320C54x" (PDF) . Instrumentos Texas. pag. 5. Archivado (PDF) desde el original el 14 de junio de 2012 . Consultado el 4 de julio de 2012 .
58. Jones, David T. "Una verificación mejorada de redundancia cíclica de 64 bits para secuencias de proteínas" (PDF) . University College de Londres. Archivado (PDF) desde el original el 7 de junio de 2011 . Consultado el 15 de diciembre de 2009 .

Otras lecturas

• Warren Jr., Henry S. (2013). "14. Verificación de redundancia cíclica". El placer del hacker (2ª ed.). Addison Wesley . págs. 319–330. ISBN 978-0-321-84268-8.

enlaces externos

• Mitra, Jubin; Nayak, Tapan (enero de 2017). "Arquitectura de diseño VLSI (FPGA) reconfigurable de muy alto rendimiento y baja latencia de CRC 32". Integración, la Revista VLSI . 56 : 1–14. doi :10.1016/j.vlsi.2016.09.005.
• Comprobaciones de redundancia cíclica, MathPages, descripción general de la detección de errores de diferentes polinomios
• Williams, Ross (1993). "Una guía sencilla para los algoritmos de detección de errores CRC". Archivado desde el original el 3 de septiembre de 2011 . Consultado el 15 de agosto de 2011 .
• Negro, Richard (1994). "CRC32 rápido en software". El Libro Azul . Grupo de Investigación de Sistemas, Laboratorio de Computación, Universidad de Cambridge.El algoritmo 4 se utilizó en Linux y Bzip2.
• Kounavis, M.; Baya, F. (2005). "Un enfoque sistemático para la construcción de generadores CRC de alto rendimiento basados ​​en software" (PDF) . Intel. Archivado (PDF) desde el original el 16 de diciembre de 2006 . Consultado el 4 de febrero de 2007 ., Algoritmos de corte por 4 y corte por 8
• Kowalk, W. (agosto de 2006). "Comprobación de redundancia cíclica CRC, análisis y corrección de errores" (PDF) . Universidad de Oldenburg. Archivado (PDF) desde el original el 11 de junio de 2007 . Consultado el 1 de septiembre de 2006 .— Filtros de bits
• Warren, Henry S. Jr. "Verificación de redundancia cíclica" (PDF) . El deleite del hacker . Archivado desde el original (PDF) el 3 de mayo de 2015.— teoría, práctica, hardware y software con énfasis en CRC-32.
• Ingeniería inversa de un algoritmo CRC Archivado el 7 de agosto de 2011 en Wayback Machine.
• Cocinero, Greg. "Catálogo de algoritmos CRC parametrizados". CRC RevEng . Archivado desde el original el 1 de agosto de 2020 . Consultado el 18 de septiembre de 2020 .
• Koopman, Phil. "Blog: Checksum y CRC Central".— incluye enlaces a archivos PDF que indican distancias CRC Hamming de 16 y 32 bits
  • - (abril de 2023). "Por qué las redes vitales tienden a proporcionar HD = 6".
• Koopman, Philip; Driscoll, Kevin; Hall, Brendan (marzo de 2015). "Código de redundancia cíclica y algoritmos de suma de comprobación para garantizar la integridad de los datos críticos" (PDF) . Administración Federal de Aviación. DOT/FAA/TC-14/49. Archivado (PDF) desde el original el 18 de mayo de 2015 . Consultado el 9 de mayo de 2015 .
• Koopman, Philip (enero de 2023). Mecánica de los cálculos de verificación de redundancia cíclica, a través de YouTube.

• ISO/IEC 13239:2002: Tecnología de la información - Telecomunicaciones e intercambio de información entre sistemas - Procedimientos de control de enlace de datos de alto nivel (HDLC)
• Biblioteca Linux CRC32-Castagnoli