Hispanopedia Wiki
Articulo de referencia

Verificación de redundancia cíclica

Una comprobació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 cambi...

Hispanopedia WikiContenido en espanolLectura gratuita

Una comprobació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 los datos digitales. A los bloques de datos que ingresan a 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 recuperar los datos, 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 datos. Las CRC se pueden utilizar para la corrección de errores (véase 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 añadir 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. Dado que el valor de verificación tiene una longitud fija, la función que lo genera se utiliza ocasionalmente como función hash .

Introducción

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 añadiendo un valor de verificación de longitud fija, para la detección de errores en redes de comunicación, fue propuesto por primera vez por W. Wesley Peterson en 1961. [ 2 ] Los códigos cíclicos no solo son sencillos de implementar, sino que tienen la ventaja de ser particularmente adecuados para la detección de errores en ráfaga : secuencias contiguas de símbolos de datos erróneos en los mensajes. Esto es importante porque los errores en 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 que no sea mayor que 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 en 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 del polinomio se calculan según 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) . Estos dos elementos suelen denominarse 0 y 1, lo que coincide con la arquitectura informática.

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. Dicho polinomio tiene un grado máximo de 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. Cabe destacar que la mayoría de las especificaciones de polinomios omiten el bit más significativo (MSb) o el bit menos significativo (LSb) , ya que siempre son 1. El CRC y el polinomio asociado suelen tener un nombre del tipo CRC- n- XXX, como se muestra 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), [ 3 ] y se denomina CRC-1. 

Solicitud

Un dispositivo con capacidad 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 va a enviar o almacenar y la agrega a los datos, formando una palabra clave .

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

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

El dispositivo puede tomar medidas correctivas, como releer el bloque o solicitar que se envíe de nuevo. De lo contrario, se asume 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 los tipos de errores más comunes en los canales de comunicación, ya que ofrecen una garantía rápida y razonable de la integridad de los mensajes transmitidos. Sin embargo, no son adecuados para proteger contra la alteración intencionada de los datos.

En primer lugar, al no existir autenticación, un atacante puede editar un mensaje y recalcular el CRC sin que se detecte la modificación. Al almacenarse junto con los datos, los CRC y las funciones hash criptográficas por sí solos no protegen contra la modificación intencionada 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 suelen basarse 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 precisamente, una función afín ): [ 6 ]

CRC⁡(incógnita⊕y)=CRC⁡(incógnita)⊕CRC⁡(y)⊕do{\displaystyle \operatorname {CRC} (x\oplus y)=\operatorname {CRC} (x)\oplus \operatorname {CRC} (y)\oplus c}

dóndedo{\displaystyle c}depende de la longitud deincógnita{\displaystyle x}yy{\displaystyle y}Esto también se puede expresar de la siguiente manera, dondeincógnita{\displaystyle x},y{\displaystyle y}yz{\displaystyle z}tienen la misma longitud

CRC⁡(incógnita⊕y⊕z)=CRC⁡(incógnita)⊕CRC⁡(y)⊕CRC⁡(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 se cifra con un cifrado de flujo que utiliza XOR como operación de combinación (o un modo de cifrado de bloques que lo convierte efectivamente en un cifrado de flujo, como OFB o CFB), tanto el mensaje como el CRC asociado pueden manipularse sin conocer la clave de cifrado; este fue uno de los fallos 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, utilizando el 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 3 bits de longitud, 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 que se va a codificar:

11010011101100

Primero se rellena con ceros que corresponden a la longitud de bits n del CRC. Esto se hace para que la palabra de código resultante tenga un formato sistemático . Aquí está el primer cálculo para obtener un CRC de 3 bits:

11010011101100 000 <--- entrada rellenada con 3 bits desde la derecha 1011 <--- divisor (4 bits) = x^3 + x + 1 ------------------ 01100011101100 000 <--- resultado

El algoritmo actúa sobre los bits situados directamente encima del 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 situados encima. Los bits que no están encima del divisor se copian directamente debajo en ese paso. A continuación, el divisor se desplaza a la derecha para alinearse con el bit 1 más significativo que queda 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 rellenada con 3 bits desde la derecha 1011 <--- divisor 01100011101100 000 <--- resultado (los primeros cuatro bits son el XOR con el divisor de abajo, el resto de los bits no cambian) 1011 <--- divisor ... 00111011101100 000 1011 00010111101100 000 1011 00000001101100 000 <--- el divisor se mueve para alinearse con el siguiente 1 en el dividendo (ya que el cociente para ese paso fue cero) 1011 (en otras palabras, no necesariamente se mueve un bit por iteración) 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 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 todos los bits de entrada con los que interactuó, al finalizar este proceso, los únicos bits de la fila de entrada que pueden ser distintos de cero son los n bits del extremo derecho de la fila. Estos n bits constituyen el resto de la 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 procesamiento posterior).

La validez de un mensaje recibido se puede verificar fácilmente repitiendo el cálculo anterior, esta vez añadiendo el valor de verificación en lugar de ceros. El resto debería ser cero si no hay errores detectables.

11010011101100 100 <--- entrada con valor de verificación 1011 <--- divisor 01100011101100 100 <--- resultado 1011 <--- divisor ... 00111011101100 100 ...... 00000000001110 100 1011 00000000000101 100 101 1 ------------------ 00000000000000 000 <--- resto

El siguiente código Python describe una función que devuelve el resto CRC inicial para una entrada y un polinomio seleccionados, con un relleno inicial de 1 o 0. Este código funciona con entradas de cadena en lugar de números sin formato:

def crc_remainder ( input_bitstring , polynomial_bitstring , initial_filler ): """Calcula el resto CRC de una cadena de bits usando un polinomio elegido.  initial_filler debe ser '1' o '0'.  """ polynomial_bitstring = polynomial_bitstring . lstrip ( "0" ) len_input = len ( input_bitstring ) initial_padding = ( len ( polynomial_bitstring ) - 1 ) * initial_filler input_padded_array = list ( input_bitstring + initial_padding ) while "1" in input_padded_array [: len_input ]: cur_shift = input_padded_array . índice ( "1" ) para i en rango ( len ( cadena_bits_polinomial )): matriz_rellenada_entrada [ desplazamiento_actual + i ] \ = str ( int ( cadena_bits_polinomial [ i ] != matriz_rellenada_entrada [ desplazamiento_actual + i ])) devolver "" . join ( matriz_rellenada_entrada )[ len_entrada :]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 ) initial_padding = check_value input_padded_array = list ( input_bitstring + initial_padding ) while "1" in input_padded_array [: len_input ]: cur_shift = input_padded_array . índice ( "1" ) para i en rango ( len ( cadena_bits_polinomial )): matriz_rellenada_entrada [ desplazamiento_actual + i ] \ = str ( int ( cadena_bits_polinomial [ i ] != matriz_rellenada_entrada [ desplazamiento_actual + i ])) devolver ( "1" no está en "" . join ( matriz_rellenada_entrada )[ len_entrada :])
>>> crc_remainder ( '11010011101100' , '1011' , '0' ) '100' >>> crc_check ( '11010011101100' , '1011' , '100' ) True

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 enteros módulo 2, es decir, cero o 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 la capacidad de detección de errores y minimizar las probabilidades de colisión.

El atributo más importante del polinomio es su longitud (grado mayor (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 polinomio 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. Dicho polinomio tiene un grado máximo de n y, por lo tanto, n + 1 términos (el polinomio tiene una longitud de n + 1 ). El resto tiene una longitud de n . El CRC se nombra con el formato 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 de errores deseadas y el tipo de recursos para implementar el CRC, así como el rendimiento deseado. Una idea errónea común es que los "mejores" polinomios CRC se derivan de polinomios irreducibles o 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 deben entrar en la selección del polinomio y pueden conducir a un polinomio reducible. Sin embargo, elegir un polinomio reducible resultará en una cierta proporción de errores no detectados, debido a que el anillo cociente tiene divisores 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 restos diferentes (también llamados síndromes ) y, por lo tanto, dado que 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.r{\displaystyle r}es el grado del polinomio generador primitivo, entonces la longitud máxima total del bloque es2r−1{\displaystyle 2^{r}-1}y el código asociado es capaz de detectar cualquier error de un bit o de dos bits. [ 9 ] Sin embargo, si usamos el polinomio generadorgramo(incógnita)=pag(incógnita)(1+incógnita){\displaystyle g(x)=p(x)(1+x)}, dóndepag{\displaystyle p}es un polinomio primitivo de grador−1{\displaystyle r-1}, entonces la longitud total máxima del bloque es2r−1−1{\displaystyle 2^{r-1}-1}y el código es capaz de detectar errores simples, dobles, triples y cualquier número impar de errores.

Un polinomiogramo(incógnita){\displaystyle g(x)}que admite otras factorizaciones que se pueden elegir para equilibrar la longitud máxima total del bloque con la potencia de detección de errores deseada. Los códigos BCH son una clase potente de dichos 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 confinados a una ventana de r bits contiguos. Estos patrones se denominan "ráfagas de error". 

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:

  • En ocasiones, una implementación antepone un patrón de bits fijo al flujo de bits que se va a comprobar. Esto resulta ú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 comprobación sin cambios.
  • Por lo general, aunque no siempre, una implementación agrega n bits 0 ( siendo n el tamaño del CRC) al flujo de bits que se va a verificar antes de que ocurra la división polinómica. Esta 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 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 OR exclusiva, 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, utilizando un algoritmo equivalente, [ 8 ] 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 aplica una operación OR exclusiva a un patrón de bits fijo en el resto de la división polinómica.
  • Orden de bits: Algunos esquemas consideran el bit menos significativo de cada byte como el "primero", lo que durante la división polinómica significa "el de más a la izquierda", lo cual contradice nuestra comprensión habitual de "orden inferior". Esta convención tiene sentido cuando las transmisiones de puerto serie se verifican mediante CRC en hardware, ya que algunas convenciones de transmisión de puerto serie muy extendidas transmiten los bytes con el bit menos significativo primero.
  • Orden de bytes : Con las CRC multibyte, puede haber confusión sobre si el byte transmitido primero (o almacenado en el byte de memoria con menor dirección) 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 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 autores asumen 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 (elincógnita0{\displaystyle x^{0}}o 1 término). Esta convención codifica el polinomio completo con su grado en un número entero.

Estas complicaciones implican que existen 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; la tercera es el número que aparece en los artículos de Koopman. En cada caso, se omite un término. Por lo tanto, el polinomioincógnita4+incógnita+1{\displaystyle x^{4}+x+1}puede transcribirse como:

  • 0x3 = 0b0011, que representaincógnita4+(0incógnita3+0incógnita2+1incógnita1+1incógnita0){\displaystyle x^{4}+(0x^{3}+0x^{2}+1x^{1}+1x^{0})}(Código con el bit más significativo primero)
  • 0xC = 0b1100, que representa(1incógnita0+1incógnita1+0incógnita2+0incógnita3)+incógnita4{\displaystyle (1x^{0}+1x^{1}+0x^{2}+0x^{3})+x^{4}}(Código LSB primero)
  • 0x9 = 0b1001, que representa(1incógnita4+0incógnita3+0incógnita2+1incógnita1)+incógnita0{\displaystyle (1x^{4}+0x^{3}+0x^{2}+1x^{1})+x^{0}}(Notación de Koopman)

En la tabla siguiente se muestran como:

Ofuscación

Los CRC en protocolos propietarios podrían ser ofuscados mediante el uso de un valor inicial no trivial y una operación XOR final, pero estas técnicas no introducen robustez criptográfica en el algoritmo y pueden ser objeto de ingeniería inversa utilizando métodos directos. [ 10 ]

Normas y uso común

Se han incorporado numerosas variedades de comprobaciones de redundancia cíclica en los estándares técnicos . De ninguna manera un algoritmo, o uno de cada grado, se adapta a todos los propósitos; Koopman y Chakravarty recomiendan seleccionar un polinomio de acuerdo con los requisitos de la aplicación y la distribución esperada de longitudes de mensajes. [ 11 ] La cantidad 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 explorado el espacio de polinomios de 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 tamaño de mensaje dado) que los polinomios de protocolos anteriores, y publicando los mejores de estos con el objetivo de mejorar la capacidad de detección de errores de los estándares futuros. [ 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 estandarizació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 Tecnológico 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: el 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 el Laboratorio de Roma, 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 del IEEE: el polinomio IEEE CRC-32 es el polinomio generador de un código Hamming y fue seleccionado por su rendimiento en la 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 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 CRC32del 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 por hardware para las operaciones CRC-32 y CRC-32C.

Representaciones polinómicas

La tabla siguiente enumera únicamente los polinomios de los diversos algoritmos en uso. Las variaciones de un protocolo particular pueden imponer preinversión, postinversión y ordenación de bits invertida, como se describió anteriormente. Por ejemplo, el CRC-32 utilizado en Gzip y Bzip2 utiliza el mismo polinomio, pero Gzip emplea ordenación de bits invertida, mientras que Bzip2 no. [ 12 ] Nótese 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(incógnita+1){\displaystyle \left(x+1\right)}El bit más significativo de un polinomio siempre es 1, y no se muestra en las representaciones hexadecimales.

Implementaciones

  • Implementación de CRC32 en GNU Radio hasta la versión 3.6.1 (aprox. 2012)
  • Código de clase C para el cálculo de la suma de verificación CRC con muchas CRC diferentes para elegir.
  • CRC-32 - Código Rosetta

Catálogos CRC

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

Véase también

Referencias

  1. ↑ "Un algoritmo para la corrección de errores en comprobaciones de redundancia cíclica" . drdobbs.com . Archivado del 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. Bibcode : 1961PIRE...49..228P . doi : 10.1109/JRPROC.1961.287814 . S2CID 51666741 . 
  3. 1 2 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.
  4. ↑ Ritter, Terry (febrero de 1986). "El gran misterio de la CRC" . Dr. Dobb's Journal . 11 (2): 26–34 , 76–83 . Archivado del original el 16 de abril de 2009. Recuperado el 21 de mayo de 2009 .
  5. ↑ 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 del original (PDF) el 19 de julio de 2011. Recuperado el 4 de febrero de 2011. Los métodos presentados ofrecen una forma muy sencilla y eficiente de modificar sus datos para que se calculen en un CRC que usted desee o al menos conozca de antemano. 
  6. ↑ "Diseño de algoritmos: ¿Por qué se dice que CRC es lineal?" . Cryptography Stack Exchange . Consultado el 5 de mayo de 2019 .
  7. ↑ Cam-Winget, Nancy; Housley, Russ; Wagner, David; Walker, Jesse (mayo de 2003). "Fallos de seguridad en los protocolos de enlace de datos 802.11" ( PDF) . Communications of the ACM . 46 (5): 35–39 . CiteSeerX 10.1.1.14.8775 . doi : 10.1145/769800.769823 . S2CID 3132937. Archivado (PDF) del original el 26 de mayo de 2013. Recuperado el 1 de noviembre de 2017 .  
  8. 1 2 3 Williams, Ross N. (24 de septiembre de 1996). "Una guía sencilla para los algoritmos de detección de errores CRC V3.0" . Archivado del original el 2 de abril de 2018. Recuperado el 23 de mayo de 2019 .
  9. ↑ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Sección 22.4 Redundancia cíclica y otras sumas de verificación» . Numerical Recipes: The Art of Scientific Computing (3.ª ed.). Cambridge University Press. ISBN  978-0-521-88068-8Archivado del original el 13 de julio de 2024. Consultado el 20 de agosto de 2024 .
  10. ↑ Ewing, Gregory C. (marzo de 2010). "Ingeniería inversa de un algoritmo CRC" . Christchurch: Universidad de Canterbury. Archivado del original el 7 de agosto de 2011. Recuperado el 26 de julio de 2011 .
  11. 1 2 3 4 5 6 7 8 9 10 Koopman, Philip; Chakravarty, Tridib (junio de 2004). "Selección de polinomios de código de redundancia cíclica (CRC) para redes embebidas". 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) del original el 11 de septiembre de 2011 . Recuperado el 14 de enero de 2011 . 
  12. 1 2 Cook, Greg (15 de agosto de 2020). "Catálogo de algoritmos CRC parametrizados" . Archivado del original el 1 de agosto de 2020. Recuperado 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". IEEE Transactions on Communications . 41 (6): 883– 892. Bibcode : 1993ITCom..41..883C . doi : 10.1109/26.231911 .
  14. 1 2 3 4 5 6 7 8 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) del original el 16 de septiembre de 2012 . Recuperado el 14 de enero de 2011 . 
  15. ↑ Koopman, Philip (21 de enero de 2016). "Los mejores polinomios CRC" . Universidad Carnegie Mellon. Archivado del original el 20 de enero de 2016. Recuperado el 26 de enero de 2016 .
  16. ↑ Brayer, Kenneth (agosto de 1975). Evaluación de polinomios de grado 32 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 del original el 31 de diciembre de 2021. Recuperado el 31 de diciembre de 2021 .
  17. ↑ 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" . Informe técnico NASA Sti/Recon N.º 76 ( publicado en mayo de 1975): 15344. Bibcode : 1975STIN...7615344H . ADA013939. Archivado del original el 31 de diciembre de 2021. Recuperado el 31 de diciembre de 2021 .
  18. ↑ Brayer, Kenneth; Hammond, Joseph L. Jr. (diciembre de 1975). Evaluación del rendimiento del polinomio 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.    
  19. ↑ Los CRC con paridad par detectan cualquier número impar de errores de bits, a costa de una menor distancia de Hamming para cargas útiles largas. Cabe destacar que la paridad se calcula sobre todo el polinomio generador, incluyendo 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.
  20. 1 2 "Zoológico CRC de 32 bits" . users.ece.cmu.edu . Archivado del original el 19 de marzo de 2018. Recuperado el 5 de noviembre de 2017 .
  21. ↑ La carga útil se refiere a la longitud sin incluir el campo CRC. Una distancia de Hamming de d significa quese pueden detectar d  −corregir ⌊( d −   
  22. ↑ siempre se logra para mensajes de longitud arbitraria.
  23. 1 2 3 4 5 6 ETSI TS 100 909 (PDF) . V8.9.0. Sophia Antipolis, Francia: Instituto Europeo de Normas de Telecomunicaciones. Enero de 2005. Archivado (PDF) del original el 17 de abril de 2018. Recuperado el 21 de octubre de 2016 .
  24. ↑ "3 Bit CRC Zoo" . users.ece.cmu.edu . Archivado del original el 7 de abril de 2018. Consultado el 19 de enero de 2018 .
  25. ↑ Protocolo RFID UHF de Clase 1 Generación 2 (PDF) . 1.2.0. EPCglobal . 23 de octubre de 2008. pág. 35. Archivado (PDF) del original el 19 de marzo de 2012. Recuperado el 4 de julio de 2012 . (Tabla 6.12)
  26. 1 2 3 4 5 6 Estándar de capa física para sistemas de espectro ensanchado cdma2000 (PDF) . Revisión D versión 2.0. 3rd Generation Partnership Project 2. Octubre de 2005. págs. 2–89–2–92. Archivado del original (PDF) el 16 de noviembre de 2013. Recuperado el 14 de octubre de 2013 . 
  27. 1 2 3 "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) del original el 28 de diciembre de 2015. Recuperado el 26 de enero de 2016 . 
  28. ↑ "6 Bit CRC Zoo" . users.ece.cmu.edu . Archivado del original el 7 de abril de 2018. Consultado el 19 de enero de 2018 .
  29. 1 2 Chakravarty, Tridib (diciembre de 2001). Rendimiento de códigos de redundancia cíclica para redes embebidas (PDF) (Tesis). Philip Koopman, director. Universidad Carnegie Mellon. págs. 5, 18. Archivado (PDF) del original el 1 de enero de 2014. Recuperado el 8 de julio de 2013 . 
  30. ↑ "5.1.4 Codificador CRC-8 (solo para flujos empaquetados)". EN 302 307 (PDF) . V1.3.1. Sophia Antipolis, Francia: Instituto Europeo de Normas de Telecomunicaciones. Marzo de 2013. pág. 17. Archivado (PDF) del original el 30 de agosto de 2017. Recuperado el 29 de julio de 2016 . 
  31. 1 2 "8 Bit CRC Zoo" . users.ece.cmu.edu . Archivado del original el 7 de abril de 2018. Recuperado el 19 de enero de 2018 .
  32. ↑ "7.2.1.2 Cálculo CRC polinomial de 8 bits 0x2F". Especificación de rutinas CRC (PDF) . 4.2.2. Múnich: AUTOSAR. 22 de julio de 2015. pág. 24. Archivado del original (PDF) el 24 de julio de 2016. Recuperado el 24 de julio de 2016 . 
  33. 1 2 3 "5.1.1.8 Campo de comprobación de redundancia cíclica (CRC-8 / CRC-16)". Especificación del perfil de seguridad de openSAFETY: Propuesta de borrador de trabajo EPSG 304. 1.4.0. Berlín: Grupo de estandarización Ethernet POWERLINK. 13 de marzo de 2013. pág. 42. Archivado del original el 12 de agosto de 2017. Recuperado el 22 de julio de 2016 . 
  34. ↑ "B.7.1.1 Generación HEC". Especificación del sistema Bluetooth . Vol. 2. Bluetooth SIG. 2 de diciembre de 2014. págs. 144–145 . Archivado del original el 26 de marzo de 2015. Recuperado el 20 de octubre de 2014 .  
  35. ↑ Whitfield, Harry (24 de abril de 2001). "XFCNs para cálculos de verificación de redundancia cíclica" . Archivado del original el 25 de mayo de 2005.
  36. ↑ Richardson, Andrew (17 de marzo de 2005). Manual de la WCDMA . Cambridge University Press. pág. 223. ISBN  978-0-521-82815-4.
  37. 1 2 Especificación del protocolo FlexRay . 3.0.1. Consorcio Flexray. Octubre de 2010. pág. 114. (4.2.8 CRC de encabezado (11 bits))
  38. ↑ Pérez, A. (1983). "Cálculos CRC byte-wise". IEEE Micro . 3 (3): 40– 50. Bibcode : 1983IMicr...3c..40P . doi : 10.1109/MM.1983.291120 . S2CID 206471618 . 
  39. ↑ Ramabadran, TV; Gaitonde, SS (1988). "Un tutorial sobre cálculos CRC". IEEE Micro . 8 (4): 62– 75. Bibcode : 1988IMicr...8d..62R . doi : 10.1109/40.7773 . S2CID 10216862 . 
  40. ↑ "Decodificación de datos de radio de onda larga mediante HC11 y MC3371" (PDF) . Freescale Semiconductor. 2004. AN1597/D. Archivado del original (PDF) el 24 de septiembre de 2015.
  41. ↑ Ely, SR; Wright, DT (marzo de 1982). LF Radio-Data: especificación de las transmisiones experimentales de la BBC de 1982 (PDF) . Departamento de Investigación, División de Ingeniería, British Broadcasting Corporation. pág. 9. Archivado (PDF) del original el 12 de octubre de 2013. Recuperado el 11 de octubre de 2013 . 
  42. ↑ Verificación de redundancia cíclica (CRC): Hoja de datos del componente PSoC Creator . Cypress Semiconductor. 20 de febrero de 2013. pág. 4. Archivado del original el 2 de febrero de 2016. Consultado el 26 de enero de 2016 . 
  43. ↑ "Verificación de redundancia cíclica (CRC) en tramas CAN" . CAN en automatización . Archivado del 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". Norma de señalización para sistemas de radiocomunicación móvil terrestre privados troncalizados (MPT 1327) (PDF) (3.ª ed.). Ofcom . Junio ​​de 1997. pág. 3. Archivado (PDF) del original el 14 de julio de 2012. Consultado el 16 de julio de 2012 .  
  45. ↑ Rehmann, Albert; Mestre, José D. (febrero de 1995). "Informe preliminar de prueba del sistema de comunicaciones e informes de aerolíneas VHF de enlace de datos aire-tierra (ACARS)" (PDF) . Centro Técnico de la Autoridad Federal de Aviación. pág. 5. Archivado del original (PDF) el 2 de agosto de 2012. Recuperado 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) del original el 1 de julio de 2015. Recuperado el 26 de enero de 2016 . 
  47. 1 2 3 Especificación del conjunto de comandos de NVM Express (TM)
  48. ↑ Thaler, Pat (28 de agosto de 2003). "Selección polinómica CRC de 16 bits" (PDF) . INCITS T10. Archivado (PDF) del original el 28 de julio de 2011. Recuperado el 11 de agosto de 2009 .
  49. ↑ "8.8.4 Comprobación de octeto (FCS)". Partes normativas de la especificación PROFIBUS (PDF) . 1.0. Vol. 9. Profibus International. Marzo de 1998. pág. 906. Archivado del original (PDF) el 16 de noviembre de 2008. Consultado el 9 de julio de 2016 .  
  50. 1 2 CAN con especificación de velocidad de datos flexible (PDF) . 1.0. Robert Bosch GmbH. 17 de abril de 2012. pág. 13. Archivado del original (PDF) el 22 de agosto de 2013. (3.2.1 MARCO DE DATOS)
  51. ↑ "Manual del programador del sistema operativo OS-9" . roug.org . Archivado del original el 17 de julio de 2018. Consultado el 17 de julio de 2018 .
  52. ↑ Koopman, Philip P. (20 de mayo de 2018). "24 Bit CRC Zoo" . users.ece.cmu.edu . Archivado del original el 7 de abril de 2018. Recuperado el 19 de enero de 2018 .
  53. ↑ "cksum" . pubs.opengroup.org . Archivado del original el 18 de julio de 2018. Consultado el 27 de junio de 2017 .
  54. ↑ Boutell, Thomas; Randers-Pehrson, Glenn; et al. (14 de julio de 1998). "Especificación PNG (Portable Network Graphics), versión 1.2" . Libpng.org. Archivado del original el 3 de septiembre de 2011. Recuperado el 3 de febrero de 2011 . 
  55. ↑ "Flujos de integridad de ReFS" .
  56. ↑ " [ MS-VHDX ] : Estructuras" .
  57. ↑ AIXM Primer (PDF) . 4.5. Organización Europea para la Seguridad de la Navegación Aérea . 20 de marzo de 2006. Archivado (PDF) del original el 20 de noviembre de 2018. Consultado el 3 de febrero de 2019 .
  58. ↑ 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
  59. ↑ Gammel, Berndt M. (31 de octubre de 2005). Documentación de Matpack: Crypto – Codes . Matpack.de. Archivado del original el 25 de agosto de 2013. Recuperado el 21 de abril de 2013 .(Nota: MpCRC.html se incluye con el código fuente del software comprimido Matpack, en /html/LibDoc/Crypto)
  60. ↑ Geremia, Patrick (abril de 1999). "Cálculo de verificación de redundancia cíclica: una implementación con el TMS320C54x" (PDF) . Texas Instruments. pág. 5. Archivado (PDF) del original el 14 de junio de 2012. Recuperado el 4 de julio de 2012 . 
  61. ↑ Jones, David T. "Una comprobación de redundancia cíclica de 64 bits mejorada para secuencias de proteínas" (PDF) . University College London. Archivado (PDF) del original el 7 de junio de 2011. Recuperado el 15 de diciembre de 2009 .

Lecturas adicionales

  • Warren Jr., Henry S. (2013). "14. Verificación de redundancia cíclica" . 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 verificación y las comprobaciones de redundancia cíclica . ASIN B0CVXWDZ99 . 
  • Mitra, Jubin; Nayak, Tapan (enero de 2017). "Arquitectura de diseño VLSI (FPGA) reconfigurable de muy alto rendimiento y baja latencia de CRC 32". Integration, the VLSI Journal . 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 en diferentes polinomios
  • Williams, Ross (1993). "Una guía sencilla para algoritmos de detección de errores CRC" . Archivado del original el 3 de septiembre de 2011. Recuperado el 15 de agosto de 2011 .
  • Black, 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.; Berry, F. (2005). "Un enfoque sistemático para la creación de generadores CRC de alto rendimiento basados ​​en software" (PDF) . Intel. Archivado (PDF) del original el 16 de diciembre de 2006. Recuperado el 4 de febrero de 2007 .Algoritmos de segmentación por 4 y por 8
  • Kowalk, W. (agosto de 2006). "CRC Cyclic Redundancy Check Analysing and Correcting Errors" (PDF) . Universidad de Oldenburg. Archivado (PDF) del original el 11 de junio de 2007. Recuperado el 1 de septiembre de 2006 .— Filtros de bits
  • Warren, Henry S. Jr. "Verificación de redundancia cíclica" (PDF) . Hacker's Delight . Archivado del 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 del original el 1 de agosto de 2020. Consultado el 18 de septiembre de 2020 .
  • Koopman, Phil. "Blog: Checksum and CRC Central" .— Incluye enlaces a archivos PDF que proporcionan distancias 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 verificación para garantizar la integridad de los datos críticos" (PDF) . Administración Federal de Aviación. DOT/FAA/TC-14/49. Archivado (PDF) del original el 18 de mayo de 2015. Recuperado el 9 de mayo de 2015 .
  • Koopman, Philip (enero de 2023). Mecánica de los cálculos de verificació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