Verificación de redundancia cíclica

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

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 comúnmente utilizado en redes digitales y dispositivos de almacenamiento para detectar cambios accidentales en los datos digitales. Los bloques de datos que ingresan a estos sistemas obtienen un breve valor de verificación adjunto, basado en el resto de una división polinomial de sus contenidos. En la recuperación, el cálculo se repite y, en caso de que los valores de verificación no coincidan, se pueden tomar medidas correctivas contra la corrupción de datos. Los CRC se pueden utilizar para la corrección de errores (ver filtros de bits).

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

Introducción

Los CRC se basan en la teoría de los códigos de corrección de errores cíclicos. W. Wesley Peterson propuso por primera vez en 1961 el uso de códigos cíclicos sistemáticos, que codifican mensajes agregando un valor de verificación de longitud fija, con el fin de detectar errores en las redes de comunicación. Los códigos cíclicos no solo son fáciles de implementar, sino que tienen la ventaja de ser particularmente adecuados para la detección de errores de ráfaga: secuencias contiguas de símbolos de datos erróneos en los mensajes. Esto es importante porque los errores de ráfaga son errores de transmisión comunes en muchos canales de comunicación, incluidos los dispositivos de almacenamiento óptico y magnético. Por lo general, un CRC de n bits aplicado a un bloque de datos de longitud arbitraria detectará cualquier ráfaga de error única que no supere los n bits, y la fracción de todas las ráfagas de error más largas que detectará es (1 − 2⁻ⁿ).

La especificación de un código CRC requiere la definición de un llamado polinomio generador. Este polinomio se convierte en el divisor en una división larga de polinomios, que toma el mensaje como dividendo y en la que se descarta el cociente y el resto se convierte en el resultado. La advertencia importante es que los coeficientes polinómicos se calculan de acuerdo con la aritmética de un campo finito, por lo que la operación de suma siempre se puede realizar en paralelo bit a bit (no hay acarreo entre dígitos).

En la práctica, todos los CRC de uso común emplean el campo de Galois, o más simplemente un campo finito, de dos elementos, GF(2). Los dos elementos generalmente se denominan 0 y 1, y coinciden cómodamente con la arquitectura de la computadora.

Un CRC se denomina CRC de n bits cuando su valor de comprobación tiene una longitud de n bits. Para un n dado, son posibles varios CRC, cada uno con un polinomio diferente. Dicho polinomio tiene el grado más alto n, lo que significa que tiene términos n + 1. En otras palabras, el polinomio tiene una longitud de n + 1; su codificación requiere n + 1 bits. Tenga en cuenta que la mayoría de las especificaciones de polinomios eliminan el MSB o el LSB, ya que siempre son 1. El CRC y el polinomio asociado suelen tener un nombre de la forma CRC-n-XXX como se muestra en la siguiente tabla.

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), 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 lo agrega a los datos, formando una palabra clave.

Cuando se recibe o 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 manera equivalente, realiza un CRC en toda la palabra clave y compara el valor de verificación resultante con un residuo esperado constante.

Si los valores de CRC no coinciden, 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 de nuevo. 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).

Integridad de 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 la 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í mismos 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áficos, 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.

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):

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

Donde $c$ depende de la longitud $x$ y $y$ . Esto también se puede decir de la siguiente manera: $x$ , $y$ y $z$ tienen la misma longitud

{displaystyle operatorname {CRC} (xoplus yoplus 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 usa XOR como su operación de combinación (o un 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 puede manipularse sin conocimiento de la clave de cifrado; este fue uno de los defectos de diseño más conocidos del protocolo de privacidad equivalente por cable (WEP).

Cálculo

Para calcular un CRC binario de n bits, alinee los bits que representan la entrada en una fila y coloque (n + Patrón de 1 bit 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 los coeficientes; un polinomio de tercer grado tiene 4 coeficientes (1x³ + 0x² + 1x + 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, necesita 4 bits para indicar explícitamente el polinomio.

Comience con el mensaje a codificar:

11010011101100

Esto se rellena primero con ceros correspondientes a la longitud de bit 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 derecho acolchado por 3 bits
1011 ---- divisor (4 bits) = x3 + x + 1
- Sí.
01100011101100 000

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 polinomial con los bits encima. Los bits que no están arriba del divisor simplemente se copian directamente debajo para ese paso. Luego, el divisor se desplaza a 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 derecho acolchado por 3 bits
1011 - Divisor
01100011101100 000 - resultado (nota los primeros cuatro bits son el XOR con el divisor debajo, el resto de los bits no se cambian)
1011 - Divisor...
00111011101100 000
1011
000
1011
00000001101100 000 --- note que el divisor se mueve para alinearse con el próximo 1 en el dividendo (ya que el cociente para ese paso era cero)
1011 (en otras palabras, no necesariamente mueve un poco por iteración)
00000000110100 000
1011
000
1011
00000001110 000
1011
00000000101 000
101 1
- Sí.
00000000000000000 100 --- resto (3 bits). El algoritmo de división se detiene aquí como 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 finaliza, 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 procesamiento posterior).

La validez de un mensaje recibido se puede verificar fácilmente realizando el cálculo anterior nuevamente, 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
1011 - Divisor
01100011101100 100
1011 - Divisor...
00111011101100 100

...

00000001110 100
1011
00000000101 100
101 1
- Sí.
00000000000000000000000000000000000000000000000000000

El siguiente código de Python describe una función que devolverá el resto CRC inicial para una entrada y un polinomio seleccionados, 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 procesar:

def crc_remainder()input_bitstring, polinomial_bitstring, inicial_filler): """Calcula la CRC permanece de una cadena de bits usando un polinomio elegido. inicial_filler debe ser '1' o '0'. " polinomial_bitstring = polinomial_bitstring.Istrip()'0') len_input = Len()input_bitstring) inicial_padding = ()Len()polinomial_bitstring) - 1) * inicial_filler input_padded_array = lista()input_bitstring + inicial_padding) mientras '1 ' dentro input_padded_array[:len_input]: cur_shift = input_padded_array.índice()'1 ') para i dentro rango()Len()polinomial_bitstring) input_padded_array[cur_shift + i] 
 = str()int()polinomial_bitstring[i] ! input_padded_array[cur_shift + i]) retorno ' '.Únase()input_padded_array[len_input:def crc_check()input_bitstring, polinomial_bitstring, check_value): """Calcular el cheque de CRC de una cadena de bits usando un polinomio elegido."" polinomial_bitstring = polinomial_bitstring.Istrip()'0') len_input = Len()input_bitstring) inicial_padding = check_value input_padded_array = lista()input_bitstring + inicial_padding) mientras '1 ' dentro input_padded_array[:len_input]: cur_shift = input_padded_array.índice()'1 ') para i dentro rango()Len()polinomial_bitstring) input_padded_array[cur_shift + i] 
 = str()int()polinomial_bitstring[i] ! input_padded_array[cur_shift + i]) retorno ()'1 ' no dentro ' '.Únase()input_padded_array[len_input:)

, titulado crc_remainder()'11010011101100 ', '1011 ', '0')'100 ', titulado crc_check()'11010011101100 ', '1011 ', '100 ')Cierto.

Algoritmo CRC-32

Este es un algoritmo práctico para la variante CRC-32 de CRC. La CRCTable es una memorización de un cálculo que tendría que repetirse para cada byte del mensaje (Cálculo de verificaciones de redundancia cíclica § Cómputo de bits múltiples).

Función CRC32
 Entrada:datos: Bytes // Array of bytes Producto:crc32: UInt32 // 32 bits sin signed CRC-32 valor
// Inicializar CRC-32 al valor inicialcrc32 ← 0xFFFF
para cada uno byte dentro datos donLookupIndex ← (crc32 xor byte) y 0x FF
crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] // CRCTable es una serie de 256 constantes de 32 bits
// Finalizar el valor CRC-32 invirtiendo todos los bitscrc32 ← crc32 xor 0xFFFF
retorno crc32

En C, el algoritmo se ve así:

#include Identificaciones.h // uint32_t, uint8_tuint32_t CRC32()const uint8_t datos[], size_t data_length) {}uint32_t crc32 = 0xFFFFFFu;para ()size_t i = 0; i . data_length; i++) {}const uint32_t LookupIndex = ()crc32 ^ datos[i]) " 0xff;crc32 = ()crc32 > 8) ^ CRCTable[LookupIndex]; // CRCTable es una serie de 256 constantes de 32 bits}// Finalizar el valor CRC-32 invirtiendo todos los bitscrc32 ^= 0xFFFFFFu;retorno crc32;}

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 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ñ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 mientras se minimizan las probabilidades generales de colisión.

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

Las longitudes polinómicas más utilizadas son 9 bits (CRC-8), 17 bits (CRC-16), 33 bits (CRC-32) y 65 bits (CRC-64).

Un CRC se denomina CRC de n bits cuando su valor de comprobación es n bits. Para un n dado, son posibles varios CRC, cada uno con un polinomio diferente. Dicho 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 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 funciones de protección contra errores deseadas y el tipo de recursos para implementar el CRC, así como el rendimiento deseado. Un concepto erróneo común es que el "mejor" Los 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. 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 perdidos, debido a que el anillo del 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 la longitud máxima total del bloque en el sentido de que todos los errores de 1 bit dentro de esa longitud del bloque tienen diferentes restos (también llamados síndromes) y por lo tanto, ya 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 del bloque. Si $r$ es el grado del generador primitivo polinomio, entonces la longitud total del bloque maximal es $2^{r}-1$ , y el código asociado es capaz de detectar cualquier error de un solo bit o de doble bit. Podemos mejorar esta situación. Si utilizamos el polinomio del generador $g(x)=p(x)(1+x)$ , donde $p$ es un polinomio primitivo de grado $r-1$ , entonces la longitud total de bloque maximal es $2^{r-1}-1$ , y el código es capaz de detectar un número único, doble, triple y cualquier número impar de errores.

Un polinomio $g(x)$ que admite otras factorizaciones puede ser elegido entonces para equilibrar el bloqueo total máximo con un poder de detección de errores deseado. Los códigos BCH son una clase poderosa de tales polinomios. Suman los dos ejemplos anteriores. Independientemente de las propiedades de reducibilidad de un generador polinomio de grador, si incluye el término "+1", el código será capaz de detectar patrones de error que se limitan a una ventana de r bits contiguos. Estos patrones se llaman "rupciones terroristas".

Especificación

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

A veces una aplicación prefijos un patrón de bit fijo al bitstream para ser revisado. Esto es útil cuando los errores de relojería pueden insertar 0 bits delante de un mensaje, una alteración que de otra manera dejaría sin cambios el valor de verificación.
Normalmente, pero no siempre, una implementación apéndices n 0-bits ()n ser el tamaño de la CRC) en el bitstream que se revisará antes de que se produzca la división polinomio. Este gasto se demuestra explícitamente en el artículo de la Convención sobre los Derechos del Niño. Esto tiene la conveniencia de que el resto del bitstream original con el valor de verificación anexado sea exactamente cero, por lo que el CRC se puede comprobar simplemente realizando la división polinomio en el bitstream recibido y comparando el resto con cero. Debido a las propiedades asociativas y comunicativas de la operación exclusiva, las implementaciones prácticas impulsadas por tablas pueden obtener un resultado numéricamente equivalente a cero-appendiendo sin incluir explícitamente ningún cero, utilizando un algoritmo equivalente y más rápido que combina el bitstream del mensaje con el flujo que se desplaza fuera del registro de CRC.
A veces una aplicación exclusiva-ORs un patrón de bit fijo en el resto de la división polinomio.
Orden: Algunos esquemas ven el pedazo de orden bajo de cada byte como "primero", que entonces durante la división polinomio significa "izquierda", que es contraria a nuestro entendimiento consuetudinario de "bajo orden". Esta convención tiene sentido cuando las transmisiones de puerto serie son revisadas por CRC en hardware, ya que algunas convenciones de transmisión en serie transmiten bytes menos significativos primero.
Orden Byte: Con los CRC de múltiples bytes, puede haber confusión sobre si el byte transmitido primero (o almacenado en el byte de memoria más bajo abordado) es el byte menos significativo (LSB) o el byte más significativo (MSB). Por ejemplo, algunos esquemas de 16 bits de CRC intercambian los bytes del valor de verificación.
Omisión del bit de alto orden del polinomio divisor: Puesto que la parte de alto orden es siempre 1, y desde n-bit CRC debe definirse por unn + 1)-bit divisor que desborda un n- registro de bits, algunos escritores asumen que es innecesario mencionar la parte de alto orden del divisor.
Omisión del bit bajo pedido del polinomio divisor: Puesto que el bit de bajo orden es siempre 1, autores como Philip Koopman representan polinomios con su bit de alto orden intacto, pero sin el bit de bajo orden (el $x^{0}$ o 1 término). Esta convención codifica el polinomio completo con su grado en un entero.

Estas complicaciones significan que hay tres formas comunes de expresar un polinomio como un entero: los dos primeros, que son imágenes espejo en binario, son las constantes encontradas en código; el tercero es el número encontrado en los papeles de Koopman. En cada caso, se omite un término. Así que el polinomio $x^{4}+x+1$ puede ser transcrito como:

0x3 = 0b0011, que representa ${displaystyle x^{4}+(0x^{3}+0x^{2}+1x^{1}+1x^{0})}$ (MSB-primer código)
0xC = 0b1100, representación ${displaystyle (1x^{0}+1x^{1}+0x^{2}+0x^{3})+x^{4}}$ (LB-primer código)
0x9 = 0b1001, que representa ${displaystyle (1x^{4}+0x^{3}+0x^{2}+1x^{1})+x^{0}}$ (Notación Koopman)

En la siguiente tabla se muestran como:

Ejemplos de representaciones de la CRC
Nombre	Normal	Inversa	Reciprocalidad inversa
CRC-4	0x3	0xC	0x9

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 agregan fuerza criptográfica al algoritmo y se pueden aplicar ingeniería inversa utilizando métodos sencillos.

Estándares y uso común

Se han incorporado numerosas variedades de comprobaciones de redundancia cíclica en las normas técnicas. De ninguna manera un algoritmo, o uno de cada grado, sirve para 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 la longitud de los mensajes. La cantidad de CRC distintos en uso ha confundido a los desarrolladores, una situación que los autores han tratado de abordar. Hay tres polinomios informados para CRC-12, veintidós definiciones contradictorias de CRC-16 y siete de CRC-32.

Los polinomios comúnmente aplicados no son los más eficientes posibles. Desde 1993, Koopman, Castagnoli y otros han investigado el espacio de polinomios entre 3 y 64 bits de tamaño, 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 la mejor de ellas con el objetivo de mejorar la capacidad de detección de errores de los futuros estándares. 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 utilizado por los organismos de estándares, 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 por parte de 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 fueron en sus publicaciones de 1975: Technical Report 2956 de Brayer para Mitre, publicado en enero y publicado para difusión pública a través de DTIC en agosto, y el informe de Hammond, Brown y Liu para el Laboratorio de Roma, publicado en mayo. Ambos informes contenían contribuciones del otro equipo. Durante diciembre de 1975, Brayer y Hammond presentaron su trabajo en un documento en la Conferencia Nacional de Telecomunicaciones de IEEE: el polinomio IEEE CRC-32 es el polinomio generador de un código de Hamming y fue seleccionado por su rendimiento de detección de errores. 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. 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 el hardware como una operación ( CRC32) del conjunto de instrucciones SSE4.2, introducido por primera vez en los procesadores Intel' Microarquitectura Nehalem. La arquitectura ARM AArch64 también proporciona aceleración de hardware para las operaciones CRC-32 y CRC-32C.

Representaciones polinómicas de comprobaciones de redundancia cíclica

La tabla siguiente lista sólo los polinomios de los diversos algoritmos en uso. Las variaciones de un protocolo particular pueden imponer pre-inversión, post-inversión y pedidos de bits revertidos como se describe anteriormente. Por ejemplo, el CRC32 utilizado en Gzip y Bzip2 utiliza el mismo polinomio, pero Gzip emplea el pedido de bits invertidos, mientras que Bzip2 no. Tenga en cuenta que incluso los polinomios de paridad en GF(2) con grado mayor a 1 nunca son primitivos. Incluso el polinomio de paridad marcado como primitivo en esta tabla representa un polinomio primitivo multiplicado por ${displaystyle left(x+1right)}$ . El pedazo más significativo de un polinomio es siempre 1, y no se muestra en las representaciones hexagonales.

Nombre	Usos	Representaciones polinómicas				Paridad	Primitivo	Montones máximos de carga por distancia Hamming
Nombre	Usos	Normal	Inversa	Reciprocal	Reciprocalidad inversa	Paridad	Primitivo	≥ 16	15	14	13	12	11	10	9	8	7	6	5	4	3	2
CRC-1	más hardware; también conocido como Parity bit	0x1	0x1	0x1	0x1	incluso
CRC-1	más hardware; también conocido como Parity bit	$x+1$				incluso
CRC-3-GSM	redes móviles	0x3	0x6	0x5	0x5	extraño	Sí.	–	–	–	–	–	–	–	–	–	–	–	–	–	4	JUEGO
CRC-3-GSM	redes móviles	$x^{3}+x+1$				extraño	Sí.	–	–	–	–	–	–	–	–	–	–	–	–	–	4	JUEGO
CRC-4-ITU	UIT-T G.704, pág. 12	0x3	0xC	0x9	0x9	extraño
CRC-4-ITU	UIT-T G.704, pág. 12	$x^{4}+x+1$				extraño
CRC-5-EPC	Gen 2 RFID	0x09	0x12	0x05	0x14	extraño
CRC-5-EPC	Gen 2 RFID	$x^{5}+x^{3}+1$				extraño
CRC-5-ITU	UIT-T G.704, pág. 9	0x15	0x15	0x0B	0x1A	incluso
CRC-5-ITU	UIT-T G.704, pág. 9	$x^{5}+x^{4}+x^{2}+1$				incluso
CRC-5-USB	Paquetes de token USB	0x05	0x14	0x09	0x12	extraño
CRC-5-USB	Paquetes de token USB	$x^{5}+x^{2}+1$				extraño
CRC-6-CDMA2000-A	redes móviles	0x27	0x39	0x33	0x33	extraño
CRC-6-CDMA2000-B	redes móviles	0x07	0x38	0x31	0x23	incluso
CRC-6-DARC	Canal de radio de datos	0x19	0x26	0x0D	0x2C	incluso
CRC-6-GSM	redes móviles	0x2F	0x3D	0x3B	0x37	incluso	Sí.	–	–	–	–	–	–	–	–	–	–	1	1	25	25	JUEGO
CRC-6-GSM	redes móviles	${displaystyle x^{6}+x^{5}+x^{3}+x^{2}+x+1}$				incluso	Sí.	–	–	–	–	–	–	–	–	–	–	1	1	25	25	JUEGO
CRC-6-ITU	UIT-T G.704, pág. 3	0x03	0x30	0x21	0x21	extraño
CRC-6-ITU	UIT-T G.704, pág. 3	$x^{6}+x+1$				extraño
CRC-7	sistemas de telecomunicaciones, UIT-T G.707, UIT-T G.832, MMC, SD	0x09	0x48	0x11	0x44	extraño
CRC-7		$x^{7}+x^{3}+1$				extraño
CRC-7-MVB	Train Communication Network, IEC 60870-5	0x65	0x53	0x27	0x72	extraño
CRC-8	DVB-S2	0xD5	0xAB	0x57	0xEA	incluso	no	–	–	–	–	–	–	–	–	–	–	2	2	85	85	JUEGO
CRC-8	DVB-S2	$x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+1$				incluso	no	–	–	–	–	–	–	–	–	–	–	2	2	85	85	JUEGO
CRC-8-AUTOSAR	integración automotriz, OpenSafety	0x2F	0xF4	0xE9	0x97	incluso	Sí.	–	–	–	–	–	–	–	–	–	–	3	3	119	119	JUEGO
CRC-8-AUTOSAR	integración automotriz, OpenSafety	${displaystyle x^{8}+x^{5}+x^{3}+x^{2}+x+1}$				incluso	Sí.	–	–	–	–	–	–	–	–	–	–	3	3	119	119	JUEGO
CRC-8-Bluetooth	conectividad inalámbrica	0xA7	0xE5	0xCB	0xD3	incluso
CRC-8-Bluetooth	conectividad inalámbrica	${displaystyle x^{8}+x^{7}+x^{5}+x^{2}+x+1}$				incluso
CRC-8-CCITT	ITU-T I.432.1 (02/99); ATM HEC, ISDN HEC y delineación celular, SMBus PEC	0x07	0xE0	0xC1	0x83	incluso
CRC-8-CCITT		$x^{8}+x^{2}+x+1$				incluso
CRC-8-Dallas/Maxim	Autobús de 1-Wire	0x31	0x8C	0x19	0x98	incluso
CRC-8-Dallas/Maxim	Autobús de 1-Wire	$x^{8}+x^{5}+x^{4}+1$				incluso
CRC-8-DARC	Canal de radio de datos	0x39	0x9C	0x39	0x9C	extraño
CRC-8-DARC	Canal de radio de datos	${displaystyle x^{8}+x^{5}+x^{4}+x^{3}+1}$				extraño
CRC-8-GSM-B	redes móviles	0x49	0x92	0x25	0xA4	incluso
CRC-8-GSM-B	redes móviles	${displaystyle x^{8}+x^{6}+x^{3}+1}$				incluso
CRC-8-SAE J1850	AES3; OBD	0x1D	0xB8	0x71	0x8E	extraño
CRC-8-SAE J1850	AES3; OBD	$x^{8}+x^{4}+x^{3}+x^{2}+1$				extraño
CRC-8-WCDMA	redes móviles	0x9B	0xD9	0xB3	0xCD	incluso
CRC-8-WCDMA	redes móviles	$x^{8}+x^{7}+x^{4}+x^{3}+x+1$				incluso
CRC-10	ATM; ITU-T I.610	0x233	0x331	0x263	0x319	incluso
CRC-10	ATM; ITU-T I.610	$x^{{10}}+x^{9}+x^{5}+x^{4}+x+1$				incluso
CRC-10-CDMA2000	redes móviles	0x3D9	0x26F	0x0DF	0x3EC	incluso
CRC-10-GSM	redes móviles	0x175	0x2BA	0x175	0x2BA	extraño
CRC-11	FlexRay	0x385	0x50E	0x21D	0x5C2	incluso
CRC-11	FlexRay	$x^{{11}}+x^{9}+x^{8}+x^{7}+x^{2}+1$				incluso
CRC-12	sistemas de telecomunicaciones	0x80F	0xF01	0xE03	0xC07	incluso
CRC-12	sistemas de telecomunicaciones	$x^{{12}}+x^{{11}}+x^{3}+x^{2}+x+1$				incluso
CRC-12-CDMA2000	redes móviles	0xF13	0xC8F	0x91F	0xF89	incluso
CRC-12-GSM	redes móviles	0xD31	0x8CB	0x197	0xE98	extraño
CRC-13-BBC	Hora de la señal, Radio Teleswitch	0x1CF5	0x15E7	0x0BCF	0x1E7A	incluso
CRC-13-BBC	Hora de la señal, Radio Teleswitch	$x^{{13}}+x^{{12}}+x^{{11}}+x^{{10}}+x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+1$				incluso
CRC-14-DARC	Canal de radio de datos	0x0805	0x2804	0x1009	0x2402	incluso
CRC-14-GSM	redes móviles	0x202D	0x2D01	0x1A03	0x3016	incluso
CRC-15-CAN		0xC599	0x4CD1	0x19A3	0x62CC	incluso
CRC-15-CAN		$x^{{15}}+x^{{14}}+x^{{10}}+x^{8}+x^{7}+x^{4}+x^{3}+1$				incluso
CRC-15-MPT1327		0x6815	0x540B	0x2817	0x740A	extraño
CRC-16-Chakravarty	Optimal for payloads ≤64 bits	0x2F15	0xA8F4	0x51E9	0x978A	extraño
CRC-16-ARINC	Aplicaciones ACARS	0xA02B	0xD405	0xA80B	0xD015	extraño
CRC-16-CCITT	X.25, V.41, HDLC FCS, XMODEM, Bluetooth, PACTOR, SD, DigRF, muchos otros; conocido como CRC-CCITT	0x1021	0x8408	0x811	0x8810	incluso
CRC-16-CCITT		$x^{16} + x^{12} + x^5 + 1$				incluso
CRC-16-CDMA2000	redes móviles	0xC867	0xE613	0xCC27	0xE433	extraño
CRC-16-DECT	Teléfonos inalámbricos	0x0589	0x91A0	0x2341	0x82C4	incluso
CRC-16-DECT	Teléfonos inalámbricos	$x^{{16}}+x^{{10}}+x^{8}+x^{7}+x^{3}+1$				incluso
CRC-16-T10-DIF	SCSI DIF	0xBB87	0xEDD1	0xDBA3	0xC5DB	extraño
CRC-16-T10-DIF	SCSI DIF	$x^{{16}}+x^{{15}}+x^{{11}}+x^{{9}}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$				extraño
CRC-16-DNP	DNP, IEC 870, M-Bus	0x3D65	0xA6BC	0x4D79	0x9EB2	incluso
CRC-16-DNP	DNP, IEC 870, M-Bus	$x^{{16}}+x^{{13}}+x^{{12}}+x^{{11}}+x^{{10}}+x^{8}+x^{6}+x^{5}+x^{2}+1$				incluso
CRC-16-IBM	Bisync, Modbus, USB, ANSI X3.28, SIA DC-07, muchos otros; también conocido como CRC-16 y CRC-16-ANSI	0x8005	0xA001	0x4003	0xC002	incluso
CRC-16-IBM		$x^{16} + x^{15} + x^2 + 1$				incluso
CRC-16-OpenSafety-A	campo de seguridad	0x5935	0xAC9A	0x5935	0xAC9A	extraño
CRC-16-OpenSafety-B	campo de seguridad	0x755B	0xDAAE	0xB55D	0xBAAD	extraño
CRC-16-Profibus	redes de empleo	0x1DCF	0xF3B8	0xE771	0x8EE7	extraño
Fletcher-16	Se utiliza en los cheques Adler-32 A & B	A menudo confundido para ser un CRC, pero en realidad un chequesum; vea la suma de comprobación de Fletcher
CRC-17-CAN	CAN FD	0x1685B	0x1B42D	0x1685B	0x1B42D	incluso
CRC-21-CAN	CAN FD	0x102899	0x132281	0x064503	0x18144C	incluso
CRC-24	FlexRay	0x5D6DCB	0xD3B6BA	0xA76D75	0xAEB6E5	incluso
CRC-24	FlexRay	$x^{{24}}+x^{{22}}+x^{{20}}+x^{{19}}+x^{{18}}+x^{{16}}+x^{{14}}+x^{{13}}+x^{{11}}+x^{{10}}+x^{8}+x^{7}+x^{6}+x^{3}+x+1$				incluso
CRC-24-Radix-64	OpenPGP, RTCM104v3	0x864CFB	0xDF3261	0xBE64C3	0xC3267D	incluso
CRC-24-Radix-64	OpenPGP, RTCM104v3	$x^{{24}}+x^{{23}}+x^{{18}}+x^{{17}}+x^{{14}}+x^{{11}}+x^{{10}}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x+1$				incluso
CRC-24-WCDMA	Usado en OS-9 RTOS. Residuo = 0x800FE3.	0x800063	0xC60001	0x8C0003	0xC00031	incluso	Sí.	–	–	–	–	–	–	–	–	–	–	4	4	8388583	8388583	JUEGO
CRC-24-WCDMA	Usado en OS-9 RTOS. Residuo = 0x800FE3.	${displaystyle x^{24}+x^{23}+x^{6}+x^{5}+x+1}$				incluso	Sí.	–	–	–	–	–	–	–	–	–	–	4	4	8388583	8388583	JUEGO
CRC-30	CDMA	0x2030B9C7	0x38E74301	0x31CE8603	0x30185CE3	incluso
CRC-30	CDMA	$x^{{30}}+x^{{29}}+x^{{21}}+x^{{20}}+x^{{15}}+x^{{13}}+x^{{12}}+x^{{11}}+x^{{8}}+x^{{7}}+x^{{6}}+x^{{2}}+x+1$				incluso
CRC-32	ISO 3309 (HDLC), ANSI X3.66 (ADCCP), FIPS PUB 71, FED-STD-1003, ITU-T V.42, ISO/IEC/IEEE 802-3 (Ethernet), SATA, MPEG-2, PKZIP, Gzip, Bzip2, POSIX cksum, PNG, ZMODEM, muchos otros	0x04C11DB7	0xEDB88320	0xDB710641	0x82608EDB	extraño	Sí.	–	10	–	–	12	21	34	57	91	171	268	2974	91607	4294967263	JUEGO
CRC-32		$x^{{32}}+x^{{26}}+x^{{23}}+x^{{22}}+x^{{16}}+x^{{12}}+x^{{11}}+x^{{10}}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$				extraño	Sí.	–	10	–	–	12	21	34	57	91	171	268	2974	91607	4294967263	JUEGO
CRC-32C (Castagnoli)	iSCSI, SCTP, G.hn payload, SSE4.2, Btrfs, ext4, Ceph	0x1EDC6F41	0x82F63B78	0x05EC76F1	0x8F6E37A0	incluso	Sí.	6	–	8	–	20	–	47	–	177	–	5243	–	2147483615	–	JUEGO
CRC-32C (Castagnoli)	iSCSI, SCTP, G.hn payload, SSE4.2, Btrfs, ext4, Ceph	$x^{{32}}+x^{{28}}+x^{{27}}+x^{{26}}+x^{{25}}+x^{{23}}+x^{{22}}+x^{{20}}+x^{{19}}+x^{{18}}+x^{{14}}+x^{{13}}+x^{{11}}+x^{{10}}+x^{9}+x^{8}+x^{6}+1$				incluso	Sí.	6	–	8	–	20	–	47	–	177	–	5243	–	2147483615	–	JUEGO
CRC-32K (Koopman {1,3,28})	Excelente en la longitud del marco Ethernet, mal rendimiento con archivos largos	0x741B8CD7	0xEB31D82E	0xD663B05D	0xBA0DC66B	incluso	no	2	–	4	–	16	–	18	–	152	–	16360	–	114663	–	JUEGO
CRC-32K (Koopman {1,3,28})		$x^{{32}}+x^{{30}}+x^{{29}}+x^{{28}}+x^{{26}}+x^{{20}}+x^{{19}}+x^{{17}}+x^{{16}}+x^{{15}}+x^{{11}}+x^{{10}}+x^{{7}}+x^{{6}}+x^{{4}}+x^{{2}}+x+1$				incluso	no	2	–	4	–	16	–	18	–	152	–	16360	–	114663	–	JUEGO
CRC-32K₂ (Koopman {1,1,30})	Excelente en la longitud del marco Ethernet, mal rendimiento con archivos largos	0x32583499	0x992C1A4C	0x32583499	0x992C1A4C	incluso	no	–	–	3	–	16	–	26	–	134	–	32738	–	65506	–	JUEGO
CRC-32Q	aviación; AIXM	0x8141AB	0xD5828281	0xAB050503	0xC0A0A0D5	incluso
CRC-32Q	aviación; AIXM	$x^{{32}}+x^{{31}}+x^{{24}}+x^{{22}}+x^{{16}}+x^{{14}}+x^{{8}}+x^{{7}}+x^{{5}}+x^{{3}}+x+1$				incluso
Adler-32		A menudo confundido para ser un CRC, pero en realidad un chequesum; ver Adler-32
CRC-40-GSM	Canal de control GSM	0x0004820009	0x9000412000	0x2000824001	0x8002410004	incluso
CRC-40-GSM	Canal de control GSM	${displaystyle x^{40}+x^{26}+x^{23}+x^{17}+x^{3}+1=(x^{23}+1)(x^{17}+x^{3}+1)}$				incluso
CRC-64-ECMA	ECMA-182 p. 51, XZ Utils	0x42F0E1EBA9EA3693	0xC96C5795D7870F42	0x92D8AF2BAF0E1E85	0xA17870F5D4F51B49	incluso
CRC-64-ECMA	ECMA-182 p. 51, XZ Utils	$x^{{64}}+x^{{62}}+x^{{57}}+x^{{55}}+x^{{54}}+x^{{53}}+x^{{52}}+x^{{47}}+x^{{46}}+x^{{45}}+x^{{40}}+x^{{39}}+x^{{38}}+x^{{37}}+x^{{35}}+x^{{33}}+$ $x^{{32}}+x^{{31}}+x^{{29}}+x^{{27}}+x^{{24}}+x^{{23}}+x^{{22}}+x^{{21}}+x^{{19}}+x^{{17}}+x^{{13}}+x^{{12}}+x^{{10}}+x^{9}+x^{7}+x^{4}+x+1$				incluso
CRC-64-ISO	ISO 3309 (HDLC), Swiss-Prot/TrEMBL; considerado débil para la piratería	0x000000000001B	0xD800000000000000000	0xB000000000001	0x800000000000000D	extraño
CRC-64-ISO		$x^{{64}}+x^{4}+x^{3}+x+1$				extraño

Implementaciones

Implementación de CRC32 en Radio GNU 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 parametrizados de CRC
CRC Polynomial Zoo

Contenido relacionado

Más resultados...