Comprobación de redundancia cíclica

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

Una comprobación de redundancia cíclica ( CRC ) es un código de detección de errores que se utiliza habitualmente en redes digitales y dispositivos de almacenamiento para detectar cambios accidentales en los datos digitales. ^{[1] [2]} A los bloques de datos que entran en estos sistemas se les adjunta un valor de comprobación breve , basado en el resto de una división polinómica de su contenido. Al recuperarlos, se repite el cálculo y, en caso de que los valores de comprobación no coincidan, se pueden tomar medidas correctivas contra la corrupción de los datos. Las CRC se pueden utilizar para la corrección de errores (consulte filtros de bits ). ^[3]

Los CRC se denominan así porque el valor de verificación de datos es una redundancia (expande el mensaje sin añadir información ) y el algoritmo se basa en códigos cíclicos . Los CRC son populares porque son sencillos 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 utiliza ocasionalmente como una función hash .

Introducción

Los CRC se basan en la teoría de 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 comprobació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. ^[4] Los códigos cíclicos no sólo son sencillos de implementar, sino que 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 magnético y óptico. Normalmente, un CRC de n bits aplicado a un bloque de datos de longitud arbitraria detectará cualquier ráfaga de error individual no superior a 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 de un polinomio generador . Este polinomio se convierte en el divisor de una división larga polinómica , que toma el mensaje como dividendo y en la que se descarta el cociente y el resto se convierte en el resultado. La salvedad importante es que los coeficientes polinómicos se calculan de acuerdo con la aritmética de un cuerpo 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 se denominan habitualmente 0 y 1, lo que coincide cómodamente con la arquitectura informática.

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. Un polinomio de este tipo 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 de polinomios omiten 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 en la tabla siguiente.

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), ^[5] y tiene el nombre CRC-1.

Solicitud

Un dispositivo compatible con CRC calcula una secuencia binaria corta y 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 de código .

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, equivalentemente, realiza una 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). ^[6]

Integridad de los datos

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

En primer lugar, como no hay 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, los CRC y las funciones hash criptográficas por sí solos no protegen contra la modificación intencional de los datos. Cualquier aplicación que requiera protección contra tales 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. ^[7]

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 ): ^[8]

${\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 su operación de combinación (o modo de cifrado de bloque que lo convierte efectivamente en un cifrado de flujo, como OFB o CFB), tanto el mensaje como el CRC asociado pueden manipularse sin conocimiento de la clave de cifrado; este fue uno de los fallos de diseño bien conocidos del protocolo Wired Equivalent Privacy (WEP). ^[9]

Cálculo

Para calcular un CRC binario de n bits, alinee los bits que representan la entrada en una fila y posicione 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, se necesitan 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 de código 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 sobre el divisor en cada paso. El resultado de esa iteración es la operación XOR bit a bit del divisor polinómico con los bits que están sobre él. Los bits que no están sobre el 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 llega al 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 para 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í porque el dividendo es igual a cero.

Dado que el bit divisor más a la izquierda puso a cero todos los bits 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 con el valor de verificación agregado 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 del 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 cadena en lugar de números sin formato:

def  crc_remainder ( entrada_bitstring ,  polinomio_bitstring ,  relleno_inicial ): """Calcula el resto de CRC de una cadena de bits utilizando un polinomio elegido.  relleno_inicial debe ser '1' o '0'.  """ cadena_bitstring_polinomio = cadena_bitstring_polinomio . lstrip ( '0' ) len_input = len ( entrada_bitstring ) relleno_inicial = ( len ( polinomio_bitstring ) - 1 ) * relleno_inicial matriz_rellenada_entrada = lista ( entrada_bitstring + relleno_inicial ) mientras '1' en matriz_rellenada_entrada [: len_input ]: cur_shift = matriz_rellenada_entrada . índice ( '1' ) para i en rango ( len ( cadena_de_bits_polinomiales )): matriz_rellenada_de_entrada [ cur_shift + i ] \ = str ( int ( cadena_de_bits_polinomiales [ i ] != matriz_rellenada_de_entrada [ cur_shift + i ])) devolver '' . join ( matriz_rellenada_de_entrada )[ len_input :]                                        def  crc_check ( entrada_bitstring ,  polinomio_bitstring ,  valor_comprobación ): """Calcula la comprobación CRC de una cadena de bits utilizando un polinomio elegido.""" polinomio_bitstring = polinomio_bitstring.lstrip ( ' 0 ' ) len_input = len ( entrada_bitstring ) relleno_inicial = valor_comprobación matriz_acolchada_entrada = lista ( entrada_bitstring + relleno_inicial ) mientras '1' en matriz_acolchada_entrada [: len_input ]: cur_shift = matriz_acolchada_entrada . índice ( '1' ) para i en rango ( len ( cadena_de_bits_polinomiales )): matriz_rellenada_de_entrada [ cur_shift + i ] \ = str ( int ( cadena_de_bits_polinomiales [ i ] != matriz_rellenada_de_entrada [ cur_shift + i ])) return ( '1' no está en '' . join ( matriz_rellenada_de_entrada )[ 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 los coeficientes de un polinomio en alguna variable x —coeficientes que son elementos del cuerpo finito GF(2) (los números 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ño de 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 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 polinomiales más utilizadas son 9 bits (CRC-8), 17 bits (CRC-16), 33 bits (CRC-32) y 65 bits (CRC-64). ^[5]

Un CRC se denomina CRC de n bits cuando su valor de comprobación es de n bits. Para un valor n dado , son posibles múltiples CRC, cada uno con un polinomio diferente. Un polinomio de este tipo 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 una 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 pensar que los "mejores" polinomios CRC se derivan de polinomios irreducibles o de polinomios irreducibles multiplicados por el factor  1 + x , lo que añade al código la capacidad de detectar todos los errores que afecten a un número impar de bits. ^[10] 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, la elección de un polinomio reducible dará como resultado una cierta proporción de errores omitidos, debido a que el anillo de cocientes tiene divisores de cero .

La ventaja de elegir un polinomio primitivo como generador para 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 diferentes residuos (también llamados síndromes ) y, por lo tanto, dado que el residuo 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 de bloque total máxima es , y el código asociado puede detectar cualquier error de un solo bit o de dos bits. ^[11] Podemos mejorar esta situación. Si usamos el polinomio generador , donde es un polinomio primitivo de grado , entonces la longitud de bloque total máxima es , y el código puede detectar errores simples, dobles, triples y cualquier número impar de errores. ${\displaystyle r}$ ${\displaystyle 2^{r}-1}$ ${\displaystyle g(x)=p(x)(1+x)}$ ${\displaystyle p}$ ${\displaystyle r-1}$ ${\displaystyle 2^{r-1}-1}$

Se puede elegir entonces un polinomio que admita otras factorizaciones para equilibrar la longitud de bloque total máxima con una potencia de detección de errores deseada. Los códigos BCH son una clase poderosa de tales polinomios. Engloban 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 error". ${\displaystyle g(x)}$

Especificación

El concepto del CRC como código de detección de errores se complica cuando un implementador o un comité de normas lo utiliza para diseñar un sistema práctico. A continuación se enumeran 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 resulta útil cuando los errores de sincronización pueden insertar bits 0 delante de un mensaje, una alteración que, de lo contrario, dejaría el valor de verificación sin cambios.
• Generalmente, pero no siempre, una implementación añade n bits 0 ( siendo n el tamaño del CRC) al flujo de bits que se va a comprobar antes de que se produzca la división polinómica. Dicha adición se demuestra explícitamente en el artículo Cálculo del CRC . Esto tiene la ventaja de que el resto del flujo de bits original con el valor de comprobación añadido es exactamente cero, por lo que el CRC se puede comprobar 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 o exclusiva, las implementaciones prácticas controladas por tablas pueden obtener un resultado numéricamente equivalente a la adición de ceros sin añadir explícitamente ningún cero, utilizando un algoritmo equivalente ^[10] más rápido que combina el flujo de bits del mensaje con el flujo que se desplaza fuera del registro CRC.
• A veces, una implementación realiza una operación OR exclusiva con un patrón de bits fijo en el resto de la división polinomial.
• Orden de bits: algunos esquemas consideran que el bit de orden inferior de cada byte es el "primero", que luego, durante la división polinómica, significa el "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 del puerto serie se verifican mediante CRC en el hardware, porque algunas convenciones de transmisión del puerto serie generalizadas transmiten los bytes con el bit menos significativo primero.
• Orden de 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 de 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 siempre es 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 no es necesario 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 siempre es 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 entero. ${\displaystyle x^{0}}$

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

• 0x3 = 0b0011, que representa (código MSB-first) ${\displaystyle x^{4}+(0x^{3}+0x^{2}+1x^{1}+1x^{0})}$
• 0xC = 0b1100, que representa (código LSB primero) ${\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 se pueden ofuscar mediante el uso de un valor inicial no trivial y un XOR final, pero estas técnicas no agregan fuerza criptográfica al algoritmo y se pueden aplicar ingeniería inversa utilizando métodos sencillos. ^[12]

Normas y uso común

Se han incorporado numerosas variedades de comprobaciones de redundancia cíclica a las normas técnicas . 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. ^[13] La cantidad de CRC distintos en uso ha confundido a los desarrolladores, una situación que los autores han tratado de abordar. ^[10] Hay tres polinomios informados para CRC-12, ^[13] veintidós definiciones conflictivas de CRC-16 y siete de CRC-32. ^[14]

Los polinomios que se aplican habitualmente no son los más eficientes posibles. Desde 1993, Koopman, Castagnoli y otros han estudiado el espacio de polinomios de entre 3 y 64 bits de tamaño, ^{[13] [15] [16] [17]} encontrando ejemplos que tienen un rendimiento mucho mejor (en términos de distancia de Hamming para un tamaño de mensaje dado) que los polinomios de protocolos anteriores, y publicando los mejores de ellos con el objetivo de mejorar la capacidad de detección de errores de futuros estándares. ^[16] 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 para el Laboratorio de Roma y la División de Sistemas Electrónicos de la Fuerza Aérea por Joseph Hammond, James Brown y Shyan-Shiang Liu del Instituto de Tecnología de Georgia y Kenneth Brayer de la Corporación Mitre . Las primeras apariciones conocidas del polinomio de 32 bits fueron 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, ^[18] y el informe de Hammond, Brown y Liu para el Laboratorio de Roma, publicado en mayo. ^[19] 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. ^[20] 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. ^[16] El estándar ITU-T G.hn también utiliza CRC-32C para detectar errores en la carga útil (aunque utiliza CRC-16-CCITT para los 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 polinómicas

La tabla siguiente enumera solo los polinomios de los diversos algoritmos en uso. Las variaciones de un protocolo particular pueden imponer una ordenación de bits previa, posterior y inversa como se describió anteriormente. Por ejemplo, el CRC32 utilizado en Gzip y Bzip2 utiliza el mismo polinomio, pero Gzip emplea una ordenación de bits inversa, mientras que Bzip2 no. ^[14] Tenga en cuenta que los polinomios de paridad par en GF(2) con grado mayor que 1 nunca son primitivos. Los polinomios de paridad par marcados como primitivos en esta tabla representan un polinomio primitivo multiplicado por . El bit más significativo de un polinomio siempre es 1 y no se muestra en las representaciones hexadecimales. ${\displaystyle \left(x+1\right)}$

Implementaciones

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

Catálogos del CRC

• Catálogo de algoritmos CRC parametrizados
• Zoológico de polinomios CRC

Véase también

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

Referencias

1. Pundir, Meena; Sandhu, Jasminder Kaur (2021). "Una revisión sistemática de la calidad del servicio en redes de sensores inalámbricos mediante aprendizaje automático: tendencia reciente y visión futura". Journal of Network and Computer Applications . 188 : 103084. doi :10.1016/j.jnca.2021.103084. El mecanismo de verificación de redundancia cíclica (CRC) se utiliza para proteger los datos y brindar protección de integridad contra bits de error cuando los datos se transmiten del remitente al receptor.
2. Schiller, Frank; Mattes, Tina (2007). "Análisis de polinomios CRC para comunicación crítica de seguridad mediante autómatas deterministas y estocásticos". Detección de fallas, supervisión y seguridad de procesos técnicos 2006. Elsevier. págs. 944–949. doi :10.1016/b978-008044485-7/50159-7. ISBN . 978-0-08-044485-7La verificación de redundancia cíclica (CRC) es un método eficiente para garantizar una baja probabilidad de errores no detectados en la transmisión de datos utilizando una suma de comprobación como resultado de una división polinomial.
3. "Un algoritmo para corregir errores en comprobaciones de redundancia cíclica". drdobbs.com . Archivado desde el original el 20 de julio de 2017 . Consultado el 28 de junio de 2017 .
4. 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.
5. Ergen, Mustafa (21 de enero de 2008). "2.3.3 Codificación de detección de errores". Banda ancha móvil . Springer . págs. 29-30. doi :10.1007/978-0-387-68192-4_2. ISBN 978-0-387-68192-4.
6. Ritter, Terry (febrero de 1986). "El gran misterio de la CRC". 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 .
7. Stigge, Martin; Plötz, Henryk; Müller, Wolf; Redlich, Jens-Peter (mayo de 2006). "Reversing CRC – Theory and Practice" (PDF) . Universidad Humboldt de Berlín. pág. 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 calculen el CRC que desea o al menos conoce de antemano.
8. "diseño de algoritmos: ¿por qué se dice que el CRC es lineal?". Cryptography Stack Exchange . Consultado el 5 de mayo de 2019 .
9. Cam-Winget, Nancy; Housley, Russ; Wagner, David; Walker, Jesse (mayo de 2003). «Security Flaws in 802.11 Data Link Protocols» (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 . 
10. Williams, Ross N. (24 de septiembre de 1996). "A Painless Guide to CRC Error Detection Algorithms V3.0". Archivado desde el original el 2 de abril de 2018. Consultado el 23 de mayo de 2019 .
11. Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 22.4 Redundancia cíclica y otras sumas de comprobación". Recetas numéricas: el arte de la computación científica (3.ª ed.). Cambridge University Press. ISBN 978-0-521-88068-8Archivado desde el original el 13 de julio de 2024 . Consultado el 20 de agosto de 2024 .
12. 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 .
13. Koopman, Philip; Chakravarty, Tridib (junio de 2004). "Selección polinómica de código de redundancia cíclica (CRC) para redes integradas". Conferencia internacional sobre sistemas y redes confiables, 2004 (PDF) . pp. 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 .
14. 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 .
15. Castagnoli, G.; Bräuer, S.; Herrmann, M. (junio de 1993). "Optimización de códigos de comprobación de redundancia cíclica con 24 y 32 bits de paridad". IEEE Transactions on Communications . 41 (6): 883–892. doi :10.1109/26.231911.
16. 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) . pp. 459–468. CiteSeerX 10.1.1.11.8323 . doi :10.1109/DSN.2002.1028931. ISBN.  978-0-7695-1597-7. S2CID  14775606. Archivado (PDF) del original el 16 de septiembre de 2012 . Consultado el 14 de enero de 2011 .
17. Koopman, Philip (21 de enero de 2016). «Best CRC Polynomials». Universidad Carnegie Mellon. Archivado desde el original el 20 de enero de 2016. Consultado el 26 de enero de 2016 .
18. Brayer, Kenneth (agosto de 1975). Evaluación de polinomios de 32 grados en la detección de errores en los patrones de error de SATIN IV Autovon (informe). 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 .
19. Hammond, Joseph L. Jr.; Brown, James E.; Liu, Shyan-Shiang (1975). "Desarrollo de un modelo de error de transmisión y un modelo de control de errores". NASA Sti/Recon Technical Report N . 76 (publicado en mayo de 1975): 15344. Bibcode :1975STIN...7615344H. ADA013939. Archivado desde el original el 31 de diciembre de 2021 . Consultado el 31 de diciembre de 2021 .
20. Brayer, Kenneth; Hammond, Joseph L. Jr. (diciembre de 1975). Evaluación del rendimiento polinomial de detección de errores en el canal AUTOVON. NTC 75: Conferencia Nacional de Telecomunicaciones, 1–3 de diciembre de 1975, Nueva Orleans, Luisiana. Vol. 1. Instituto de Ingenieros Eléctricos y Electrónicos. págs. 8–21–5. Bibcode :1975ntc.....1....8B. OCLC  32688603. 75 CH 1015-7 CSCB.
21. Los CRC con paridad par detectan cualquier número impar de errores de bit, a expensas de una distancia de Hamming menor para cargas útiles largas. Nótese 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 lo tanto, su paridad es par.
22. "32 Bit CRC Zoo". users.ece.cmu.edu . Archivado desde el original el 19 de marzo de 2018 . Consultado el 5 de noviembre de 2017 .
23. La carga útil significa longitud sin incluir el 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⌋ bit
24. siempre se logra para mensajes arbitrariamente largos
25. 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 .
26. "3 Bit CRC Zoo". users.ece.cmu.edu . Archivado desde el original el 7 de abril de 2018 . Consultado el 19 de enero de 2018 .
27. Protocolo RFID UHF de 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 .(Cuadro 6.12)
28. 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 .
29. «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 .
30. "6 Bit CRC Zoo". users.ece.cmu.edu . Archivado desde el original el 7 de abril de 2018 . Consultado el 19 de enero de 2018 .
31. Chakravarty, Tridib (diciembre de 2001). Performance of Cyclic Redundancy Codes for Embedded Networks (PDF) (Tesis). Philip Koopman, asesor. Carnegie Mellon University. pp. 5, 18. Archivado (PDF) desde el original el 1 de enero de 2014. Consultado el 8 de julio de 2013 .
32. "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 .
33. "8 Bit CRC Zoo". users.ece.cmu.edu . Archivado desde el original el 7 de abril de 2018 . Consultado el 19 de enero de 2018 .
34. "7.2.1.2 Cálculo de CRC polinomial 0x2F de 8 bits". Especificación de rutinas de CRC (PDF) . 4.2.2. Múnich: AUTOSAR. 22 de julio de 2015. pág. 24. Archivado desde el original (PDF) el 24 de julio de 2016 . Consultado el 24 de julio de 2016 .
35. «5.1.1.8 Campo de comprobación de redundancia cíclica (CRC-8/CRC-16)». Especificación de perfil de seguridad de openSAFETY: Propuesta de borrador de trabajo de EPSG 304. 1.4.0. Berlín: Ethernet POWERLINK Standardisation Group. 13 de marzo de 2013. pág. 42. Archivado desde el original el 12 de agosto de 2017. Consultado el 22 de julio de 2016 .
36. "B.7.1.1 Generación de HEC". Especificación del sistema Bluetooth. Vol. 2. Bluetooth SIG. 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 .
37. Whitfield, Harry (24 de abril de 2001). "XFCN para cálculos de comprobación de redundancia cíclica". Archivado desde el original el 25 de mayo de 2005.
38. Richardson, Andrew (17 de marzo de 2005). WCDMA Handbook. Cambridge University Press. pág. 223. ISBN 978-0-521-82815-4.
39. Especificación del protocolo FlexRay . 3.0.1. Consorcio Flexray. Octubre de 2010. pág. 114.(4.2.8 CRC de encabezado (11 bits))
40. Pérez, A. (1983). "Cálculos CRC byte a byte". IEEE Micro . 3 (3): 40–50. doi :10.1109/MM.1983.291120. S2CID  206471618.
41. Ramabadran, TV; Gaitonde, SS (1988). "Un tutorial sobre cálculos CRC". IEEE Micro . 8 (4): 62–75. doi :10.1109/40.7773. S2CID  10216862.
42. "Decodificación de datos de radio de onda larga utilizando un HC11 y un MC3371" (PDF) . Freescale Semiconductor. 2004. AN1597/D. Archivado desde el original (PDF) el 24 de septiembre de 2015.
43. Ely, SR; Wright, DT (marzo de 1982). LF Radio-Data: especificación de las transmisiones experimentales de la BBC 1982 (PDF) . Departamento de Investigación, División de Ingeniería, The British Broadcasting Corporation. p. 9. Archivado (PDF) desde el original el 12 de octubre de 2013 . Consultado el 11 de octubre de 2013 .
44. Cyclic Redundancy Check (CRC): PSoC Creator™ Component Datasheet. Cypress Semiconductor. 20 de febrero de 2013. pág. 4. Archivado desde el original el 2 de febrero de 2016. Consultado el 26 de enero de 2016 .
45. "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 .
46. "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 .
47. Rehmann, Albert; Mestre, José D. (febrero de 1995). "Informe preliminar de prueba del sistema de comunicaciones y reportes de aerolíneas VHF Air Ground Data Link (ACARS)" (PDF) . Centro Técnico de la Autoridad Federal de Aviación. pág. 5. Archivado desde el original (PDF) el 2 de agosto de 2012 . Consultado el 7 de julio de 2012 .
48. "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. pp. 99, 101. Archivado (PDF) desde el original el 1 de julio de 2015. Consultado el 26 de enero de 2016 .
49. Thaler, Pat (28 de agosto de 2003). "Selección polinomial 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 .
50. "8.8.4 Octeto de comprobación (FCS)". Partes normativas de la especificación PROFIBUS (PDF) . 1.0. Vol. 9. Profibus International. Marzo de 1998. pág. 906. Archivado desde el original (PDF) el 16 de noviembre de 2008. Consultado el 9 de julio de 2016 .
51. 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)
52. "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 .
53. Koopman, Philip P. (20 de mayo de 2018). «24 Bit CRC Zoo». users.ece.cmu.edu . Archivado desde el original el 7 de abril de 2018. Consultado el 19 de enero de 2018 .
54. "cksum". pubs.opengroup.org . Archivado desde el original el 18 de julio de 2018 . Consultado el 27 de junio de 2017 .
55. Boutell, Thomas; Randers-Pehrson, Glenn; et al. (14 de julio de 1998). «PNG (Portable Network Graphics) Specification, Version 1.2» (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 .
56. Manual básico de la 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 .
57. ETSI TS 100 909 Archivado el 17 de abril de 2018 en Wayback Machine versión 8.9.0 (enero de 2005), Sección 4.1.2 a
58. Gammel, Berndt M. (31 de octubre de 2005). Documentación de Matpack: Crypto – Codes. Matpack.de. Archivado desde el original el 25 de agosto de 2013. Consultado el 21 de abril de 2013 .(Nota: MpCRC.html está incluido con el código fuente del software comprimido Matpack, en /html/LibDoc/Crypto)
59. Geremia, Patrick (abril de 1999). «Cálculo de comprobación de redundancia cíclica: una implementación utilizando el TMS320C54x» (PDF) . Texas Instruments. pág. 5. Archivado (PDF) desde el original el 14 de junio de 2012. Consultado el 4 de julio de 2012 .
60. Jones, David T. "An Improved 64-bit Cyclic Redundancy Check for Protein Sequences" (PDF) . University College London. Archivado (PDF) desde el original el 7 de junio de 2011. Consultado el 15 de diciembre de 2009 .

Lectura adicional

• Warren Jr., Henry S. (2013). "14. Cyclic Redundancy Check". Hacker's Delight (2.ª ed.). Addison Wesley . págs. 319–330. ISBN 978-0-321-84268-8.
• Koopman, Philip (2024). Comprensión de las sumas de comprobación y las comprobaciones de redundancia cíclica . ASIN  B0CVXWDZ99.

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 algoritmos de detección de errores de CRC". Archivado desde el original el 3 de septiembre de 2011 . Consultado el 15 de agosto de 2011 .
• Black, Richard (1994). "Fast CRC32 in Software". The Blue Book . Grupo de investigación de sistemas, Laboratorio de computación, Universidad de Cambridge.El algoritmo 4 se utilizó en Linux y Bzip2.
• Kounavis, M.; Berry, F. (2005). "Un enfoque sistemático para construir generadores de CRC basados ​​en software y de alto rendimiento" (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). "CRC Cyclic Redundancy Check Analysing and Correcting Errors" (PDF) . Universität 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. "Cyclic Redundancy Check" (PDF) . Hacker's Delight . 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
• Cook, 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: Suma de comprobación y CRC Central".— incluye enlaces a archivos PDF que proporcionan distancias de Hamming CRC de 16 y 32 bits
  • — (Abril de 2023). "Por qué las redes críticas para la vida 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 comprobación de redundancia cíclica (vía 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