El cálculo de una verificación de redundancia cíclica se deriva de las matemáticas de la división de polinomios, módulo dos . En la práctica, se asemeja a una división larga de la cadena de mensajes binarios , con un número fijo de ceros añadidos, por la cadena del "polinomio generador", excepto que las operaciones exclusivas o reemplazan a las sustracciones. La división de este tipo se realiza de manera eficiente en hardware mediante un registro de desplazamiento modificado , [1] y en software mediante una serie de algoritmos equivalentes , comenzando con un código simple cercano a las matemáticas y volviéndose más rápido (y posiblemente más confuso [2] ) a través de bytes.paralelismo en sentido común y compensaciones entre el espacio y el tiempo .
Varios estándares CRC amplían el algoritmo de división de polinomios especificando un valor de registro de desplazamiento inicial, un paso OR exclusivo final y, lo que es más crítico, un orden de bits ( endianidad ). Como resultado, el código visto en la práctica se desvía de manera confusa de la división "pura", [2] y el registro puede desplazarse hacia la izquierda o hacia la derecha.
Ejemplo
Como ejemplo de implementación de la división polinomial en hardware, suponga que estamos tratando de calcular un CRC de 8 bits de un mensaje de 8 bits compuesto por el carácter ASCII "W", que es binario 01010111 2 , decimal 87 10 o hexadecimal 57 16 . A modo de ilustración, usaremos el polinomio CRC-8-ATM ( HEC ). Escribiendo el primer bit transmitido (el coeficiente de la mayor potencia de) a la izquierda, corresponde a la cadena de 9 bits "100000111".
El valor del byte 57 16 se puede transmitir en dos órdenes diferentes, dependiendo de la convención de ordenación de bits utilizada. Cada uno genera un polinomio de mensaje diferente. Msbit-first, esto es = 01010111, mientras que lsbit-first, es = 11101010. Estos se pueden multiplicar por para producir dos polinomios de mensajes de 16 bits .
Calcular el resto luego consiste en restar múltiplos del polinomio generador . Esto es como una división larga decimal, pero aún más simple porque los únicos múltiplos posibles en cada paso son 0 y 1, y las restas toman prestado "del infinito" en lugar de reducir los dígitos superiores. Como no nos importa el cociente, no es necesario registrarlo.
El bit más significativo primero | El bit menos significativo primero | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
Observe que después de cada resta, los bits se dividen en tres grupos: al principio, un grupo que es todo cero; al final, un grupo que no ha cambiado del original; y un grupo sombreado de azul en el medio que es "interesante". El grupo "interesante" tiene 8 bits de longitud, coincidiendo con el grado del polinomio. En cada paso, el múltiplo apropiado del polinomio se resta para hacer que el grupo cero sea un bit más largo, y el grupo sin cambios se acorta un poco, hasta que solo queda el resto final.
En el ejemplo de msbit-first, el polinomio restante es . Convertir a un número hexadecimal usando la convención de que la mayor potencia de x es el msbit; esto es A2 16 . En lsbit-first, el resto es. Convirtiendo a hexadecimal usando la convención de que la potencia más alta de x es el lsbit, esto es 19 16 .
Implementación
Escribir el mensaje completo en cada paso, como se hizo en el ejemplo anterior, es muy tedioso. Las implementaciones eficientes utilizan un-registro de desplazamiento de bits para contener solo los bits interesantes. Multiplicando el polinomio por equivale a desplazar el registro un lugar, ya que los coeficientes no cambian de valor, sino que solo se mueven hacia el siguiente término del polinomio.
Aquí hay un primer borrador de un pseudocódigo para calcular un CRC de n bits. Utiliza un tipo de datos compuesto artificial para polinomios, donde x
no es una variable entera, sino un constructor que genera un objeto Polynomial que se puede sumar, multiplicar y exponenciar. A dos polinomios hay que sumarlos, módulo dos; es decir, a OR exclusivo a los coeficientes de cada término coincidente de ambos polinomios.xor
función crc ( matriz de bits cadena de bits [1..len], int len) {restPolynomial : = polynomialForm (bitString [1..n]) // Los primeros n bits del mensaje // Una variante popular complementa el restoPolinomio aquí; ver § Preestablecido a −1 a continuación para i de 1 a len {restoPolinomio : = restoPolinomio * x + bitString [i + n] * x 0 // Defina bitString [k] = 0 para k> len si el coeficiente de x n del restoPolinomio = 1 { restoPolinomio: = restoPolinomio xor generadorPolinomio } } // Una variante popular complementa restantePolinomio aquí; ver § Post-invertir debajo de devolver restoPolinomio}
- Fragmento de código 1: División polinomial simple
Tenga en cuenta que este código de ejemplo evita la necesidad de especificar una convención de ordenación de bits al no utilizar bytes; la entrada bitString
ya está en forma de matriz de bits y remainderPolynomial
se manipula en términos de operaciones polinómicas; la multiplicación porpodría ser un desplazamiento hacia la izquierda o hacia la derecha, y la adición de bitString[i+n]
se hace al coeficiente, que podría ser el extremo derecho o izquierdo del registro.
Este código tiene dos desventajas. Primero, en realidad requiere un registro de n + 1 bit para mantener remainderPolynomial
elEl coeficiente se puede probar. Más significativamente, requiere bitString
que se rellene con n bits cero.
El primer problema se puede resolver probando el coeficiente del remainderPolynomial
antes se multiplica por.
El segundo problema podría resolverse haciendo las últimas n iteraciones de manera diferente, pero hay una optimización más sutil que se usa universalmente, tanto en implementaciones de hardware como de software.
Debido a que la operación XOR utilizada para restar el polinomio generador del mensaje es conmutativa y asociativa , no importa en qué orden se combinan las diversas entradas en el remainderPolynomial
. Y en concreto, un bit determinado de la bitString
no necesita ser añadido a la remainderPolynomial
hasta el último instante en que se prueba para determinar si se debe xor
a la generatorPolynomial
.
Esto elimina también la necesidad de precargar el remainderPolynomial
con los primeros n bits del mensaje:
función crc ( matriz de bits cadena de bits [1..len], int len) { restoPolinomio: = 0 // Una variante popular complementa restantePolinomio aquí; ver § Preestablecido a −1 a continuación para i de 1 a len {restoPolinomio : = restoPolinomio xor (cadena de bits [i] * x n − 1 ) if (coeficiente de x n − 1 del restoPolinomio) = 1 { restoPolinomio: = (restoPolinomio * x ) xor generadorPolinomio } más { restoPolinomio: = (restoPolinomio * x ) } } // Una variante popular complementa restantePolinomio aquí; ver § Post-invertir debajo de devolver restoPolinomio}
- Fragmento de código 2: División polinomial con mensaje diferido XORing
Ésta es la implementación estándar de CRC de hardware bit-a-a-time, y es digno de estudio; una vez que comprenda por qué esto calcula exactamente el mismo resultado que la primera versión, las optimizaciones restantes son bastante sencillas. Si remainderPolynomial
solo tiene n bits de longitud, entonces ellos coeficientes de ella y de generatorPolynomial
simplemente se descartan. Esta es la razón por la que normalmente verá polinomios CRC escritos en binario con el coeficiente principal omitido.
En el software, es conveniente tener en cuenta que si bien se puede retrasar la ejecución xor
de cada bit hasta el último momento, también es posible hacerlo antes. Por lo general, es conveniente realizar xor
un byte a la vez, incluso en una implementación de bit a bit como esta:
función crc ( cadena de matriz de bytes [1..len], int len) { restoPolinomio: = 0 // Una variante popular complementa restantePolinomio aquí; ver § Preestablecido a −1 a continuación para i de 1 a len { restoPolinomio: = restoPolinomio xor polinomioForm (cadena [i]) * x n − 8 para j de 1 a 8 { // Suponiendo 8 bits por byte si el coeficiente de x n − 1 del restoPolinomio = 1 { restoPolinomio: = (restoPolinomio * x ) xor generadorPolinomio } más { restoPolinomio: = (restoPolinomio * x ) } } } // Una variante popular complementa restantePolinomio aquí; ver § Post-invertir debajo de devolver restoPolinomio}
- Fragmento de código 3: División polinomial con mensaje XORing bytewise
Esta suele ser la implementación de software más compacta, utilizada en microcontroladores cuando el espacio es más escaso que la velocidad.
Orden de bits (endianidad)
Cuando se implementa en hardware de serie de bits , el polinomio generador describe de forma única la asignación de bits; el primer bit transmitido es siempre el coeficiente de la mayor potencia de, y el último los bits transmitidos son el resto de CRC , comenzando con el coeficiente de y terminando con el coeficiente de , también conocido como el coeficiente de 1.
Sin embargo, cuando los bits se procesan un byte a la vez, como cuando se usa transmisión en paralelo , entramado de bytes como en la codificación 8B / 10B o comunicación serial asíncrona estilo RS-232 , o cuando se implementa un CRC en software , es necesario especificar el orden de bits (endianidad) de los datos; qué bit en cada byte se considera "primero" y será el coeficiente de la mayor potencia de.
Si los datos están destinados a la comunicación en serie , es mejor utilizar el orden de bits en el que finalmente se enviarán los datos. Esto se debe a que la capacidad de un CRC para detectar errores de ráfaga se basa en la proximidad en el polinomio del mensaje.; si los términos polinomiales adyacentes no se transmiten secuencialmente, una ráfaga de error físico de una longitud puede verse como una ráfaga más larga debido a la reordenación de bits.
Por ejemplo, los estándares IEEE 802 ( ethernet ) y RS-232 ( puerto serie ) especifican la transmisión del bit menos significativo primero (little-endian), por lo que una implementación de software CRC para proteger los datos enviados a través de dicho enlace debe asignar los bits menos significativos. en cada byte a los coeficientes de las mayores potencias de. Por otro lado, los disquetes y la mayoría de los discos duros escriben primero el bit más significativo de cada byte.
El CRC de lsbit-first es un poco más simple de implementar en software, por lo que es algo más común, pero muchos programadores encuentran que el orden de bits de msbit-first es más fácil de seguir. Así, por ejemplo, el XMODEM extensión -CRc, un uso temprano de CRCs en software, utiliza un CRC MSbit-primero.
Hasta ahora, el pseudocódigo ha evitado especificar el orden de los bits dentro de los bytes al describir los cambios en el pseudocódigo como multiplicaciones por y escribir conversiones explícitas de forma binaria a polinomial. En la práctica, el CRC se mantiene en un registro binario estándar usando una convención particular de orden de bits. En la forma msbit-first, los bits binarios más significativos se enviarán primero y, por lo tanto, contienen los coeficientes polinomiales de orden superior, mientras que en la forma lsbit-first, los bits binarios menos significativos contienen los coeficientes de orden superior. El pseudocódigo anterior se puede escribir en ambas formas. Para concreción, se utiliza el polinomio CRC-16- CCITT de 16 bits:
// El bit más significativo primero (big-endian) // x ^ 16 + x ^ 12 + x ^ 5 + 1 = (1) 0001 0000 0010 0001 = 0x1021 function crc ( byte array string [1..len], int len) { rem: = 0 // Una variante popular complementa a rem aquí para i de 1 a len { rem: = rem xor (string [i] leftShift (n-8)) // n = 16 en este ejemplo para j de 1 a 8 { // Suponiendo 8 bits por byte si rem y 0x8000 { // si está más a la izquierda (la mayoría significativo) el bit se establece rem: = (rem leftShift 1) xor 0x1021 } más { rem: = rem left Shift 1 } rem: = rem y 0xffff // Recorta el resto a 16 bits } } // Una variante popular complementa a rem aquí return rem}
- Fragmento de código 4: División basada en registro de desplazamiento, MSB primero
// El bit menos significativo primero (little-endian) // x ^ 16 + x ^ 12 + x ^ 5 + 1 = 1000 0100 0000 1000 (1) = 0x8408 function crc ( byte array string [1..len], int len) { rem: = 0 // Una variante popular complementa a rem aquí para i de 1 a len { rem: = rem xor cadena [i] para j de 1 a 8 { // Suponiendo 8 bits por byte si rem y 0x0001 { // si se establece el bit más a la derecha (más significativo) rem: = (rem rightShift 1) xor 0x8408 } más { rem: = rem rightShift 1 } } } // Una variante popular complementa a rem aquí return rem}
- Fragmento de código 5: División basada en registro de desplazamiento, LSB primero
Tenga en cuenta que la forma lsbit-first evita la necesidad de cambiar string[i]
antes de xor
. En cualquier caso, asegúrese de transmitir los bytes del CRC en el orden que coincida con la convención de orden de bits elegida.
Cálculo de varios bits
Algoritmo de Sarwate (tabla de búsqueda única)
Otra optimización común utiliza una tabla de búsqueda indexada por coeficientes de orden más alto rem
para procesar más de un bit de dividendo por iteración. [3] Más comúnmente, se usa una tabla de búsqueda de 256 entradas, reemplazando el bucle interno por j
:
// Msbit-primerorem = (rem leftShift 8) xor big_endian_table [cadena [i] xor ((los 8 bits más a la izquierda de rem) rightShift (n-8))]// Lsbit-primerorem = (rem rightShift 8) xor little_endian_table [string [i] xor (8 bits más a la derecha de rem)]
- Fragmento de código 6: Núcleos de división basada en tablas
Uno de los algoritmos CRC más comunes se conoce como CRC-32 , utilizado por (entre otros) Ethernet , FDDI , ZIP y otros formatos de archivo , y formato de imagen PNG . Su polinomio se puede escribir msbit-first como 0x04C11DB7, o lsbit-first como 0xEDB88320. La página web del W3C en PNG incluye un apéndice con una implementación breve y sencilla basada en tablas en C de CRC-32. [4] Observará que el código corresponde al pseudocódigo lsbit-first byte-a-time presentado aquí, y la tabla se genera usando el código bit-a-time.
El uso de una tabla de 256 entradas suele ser más conveniente, pero se pueden usar otros tamaños. En los microcontroladores pequeños, el uso de una tabla de 16 entradas para procesar cuatro bits a la vez proporciona una mejora de la velocidad útil mientras se mantiene la tabla pequeña. En computadoras con amplio espacio de almacenamiento,La tabla de entrada 65 536 se puede utilizar para procesar 16 bits a la vez.
Generando las tablas
El software para generar las tablas es tan pequeño y rápido que normalmente es más rápido calcularlas al iniciar el programa que cargar tablas precalculadas desde el almacenamiento. Una técnica popular consiste en utilizar el código bit-por-tiempo 256 veces para generar los CRC de los 256 posibles bytes de 8 bits. Sin embargo, esto se puede optimizar significativamente aprovechando la propiedad que . Solo las entradas de la tabla correspondientes a potencias de dos deben calcularse directamente.table[i xor j] == table[i] xor table[j]
En el siguiente código de ejemplo, crc
contiene el valor de table[i]
:
big_endian_table [0]: = 0crc: = 0x8000 // Suponiendo un polinomio de 16 bitsyo: = 1hacer { si crc y 0x8000 { crc: = (crc leftShift 1) xor 0x1021 // El polinomio CRC } else { crc: = crc leftShift 1 } // crc es el valor de big_endian_table [i] ; deje j iterar sobre las entradas ya inicializadas para j de 0 a i − 1 { big_endian_table [i + j]: = crc xor big_endian_table [j]; } i: = i cambio a la izquierda 1} mientras que yo <256
- Fragmento de código 7: generación de la tabla CRC de bytes a la vez, MSB primero
little_endian_table [0]: = 0crc: = 1;yo: = 128hacer { si crc y 1 { crc: = (crc rightShift 1) xor 0x8408 // El polinomio CRC } else { crc: = crc rightShift 1 } // crc es el valor de little_endian_table [i] ; deje j iterar sobre las entradas ya inicializadas para j de 0 a 255 por 2 × i { little_endian_table [i + j]: = crc xor little_endian_table [j]; } i: = i desplazamiento a la derecha 1} mientras que i> 0
- Fragmento de código 8: generación de tabla CRC de bytes a la vez, LSB primero
En estos ejemplos de código, el índice de la tabla i + j
es equivalente a ; puede utilizar el formulario que le resulte más conveniente.i xor j
Byte-Slicing usando múltiples tablas
Existe un algoritmo de corte por N (normalmente corte por 8 para CRC32; N ≤ 64) que generalmente duplica o triplica el rendimiento en comparación con el algoritmo de Sarwate. En lugar de leer 8 bits a la vez, el algoritmo lee 8N bits a la vez. Hacerlo maximiza el rendimiento en procesadores superescalares . [5] [6] [7] [8]
No está claro quién inventó realmente el algoritmo. [9]
Cálculo paralelo sin tabla
La actualización paralela para un byte o una palabra a la vez también se puede realizar de forma explícita, sin una tabla. [10] Esto se utiliza normalmente en implementaciones de hardware de alta velocidad. Para cada bit, se resuelve una ecuación después de que se hayan introducido 8 bits. Las siguientes tablas enumeran las ecuaciones para algunos polinomios de uso común, utilizando los siguientes símbolos:
c yo | CRC bit 7… 0 (o 15… 0) antes de la actualización |
r yo | CRC bit 7… 0 (o 15… 0) después de la actualización |
d i | bit de datos de entrada 7… 0 |
e yo = d yo + c yo | e p = e 7 + e 6 +… + e 1 + e 0 (bit de paridad) |
s yo = re yo + c yo + 8 | s p = s 7 + s 6 +… + s 1 + s 0 (bit de paridad) |
Polinomio: | ( x 7 + x 3 + 1) × x (CRC-7-CCITT desplazado a la izquierda) | x 8 + x 5 + x 4 + 1 (CRC-8-Dallas / Maxim) |
---|---|---|
Coeficientes: | 0x12 = (0x09 << 1) ( MSBF / normal) | 0x8c ( LSBF / reverso) |
r 0 ←r 1 ←r 2 ←r 3 ←r 4 ←r 5 ←r 6 ←r 7 ← | 0e 0 + e 4 + e 7 e 1 + e 5 e 2 + e 6 e 3 + e 7 + e 0 + e 4 + e 7 e 4 + e 1 + e 5 e 5 + e 2 + e 6 e 6 + e 3 + e 7 | e 0 + e 4 + e 1 + e 0 + e 5 + e 2 + e 1 e 1 + e 5 + e 2 + e 1 + e 6 + e 3 + e 2 + e 0 e 2 + e 6 + e 3 + e 2 + e 0 + e 7 + e 4 + e 3 + e 1 e 3 + e 0 + e 7 + e 4 + e 3 + e 1 e 4 + e 1 + e 0 e 5 + e 2 + e 1 e 6 + e 3 + e 2 + e 0 e 7 + e 4 + e 3 + e 1 |
Fragmentos de código C : | uint8_t c , d , e , f , r ; … E = c ^ d ; f = e ^ ( e >> 4 ) ^ ( e >> 7 ); r = ( f << 1 ) ^ ( f << 4 ); | uint8_t c , d , e , f , r ; … E = c ^ d ; f = e ^ ( e << 3 ) ^ ( e << 4 ) ^ ( e << 6 ); r = f ^ ( f >> 4 ) ^ ( f >> 5 ); |
Polinomio: | x 16 + x 12 + x 5 + 1 (CRC-16-CCITT) | x 16 + x 15 + x 2 + 1 (CRC-16-ANSI) | ||
---|---|---|---|---|
Coeficientes: | 0x1021 (MSBF / normal) | 0x8408 (LSBF / reverso) | 0x8005 (MSBF / normal) | 0xa001 (LSBF / inversa) |
r 0 ←r 1 ←r 2 ←r 3 ←r 4 ←r 5 ←r 6 ←r 7 ←r 8 ←r 9 ←r 10 ←r 11 ←r 12 ←r 13 ←r 14 ←r 15 ← | s 4 + s 0 s 5 + s 1 s 6 + s 2 s 7 + s 3 s 4 s 5 + s 4 + s 0 s 6 + s 5 + s 1 s 7 + s 6 + s 2 c 0 + s 7 + s 3 c 1 + s 4 c 2 + s 5 c 3 + s 6 c 4 + s 7 + s 4 + s 0 c 5 + s 5 + s 1 c 6 + s 6 + s 2 c 7 + s 7 + s 3 | c 8 + e 4 + e 0 c 9 + e 5 + e 1 c 10 + e 6 + e 2 c 11 + e 0 + e 7 + e 3 c 12 + e 1 c 13 + e 2 c 14 + e 3 c 15 + e 4 + e 0 e 0 + e 5 + e 1 e 1 + e 6 + e 2 e 2 + e 7 + e 3 e 3 e 4 + e 0 e 5 + e 1 e 6 + e 2 e 7 + e 3 | s p s 0 + s p s 1 + s 0 s 2 + s 1 s 3 + s 2 s 4 + s 3 s 5 + s 4 s 6 + s 5 c 0 + s 7 + s 6 c 1 + s 7 c 2 c 3 c 4 c 5 c 6 c 7 + s p | c 8 + e p c 9 c 10 c 11 c 12 c 13 c 14 + e 0 c 15 + e 1 + e 0 e 2 + e 1 e 3 + e 2 e 4 + e 3 e 5 + e 4 e 6 + e 5 e 7 + e 6 e p + e 7 e p |
Fragmentos de código C : | uint8_t d , s , t ; uint16_t c , r ; … S = d ^ ( c >> 8 ); t = s ^ ( s >> 4 ); r = ( c << 8 ) ^ t ^ ( t << 5 ) ^ ( t << 12 ); | uint8_t d , e , f ; uint16_t c , r ; … E = c ^ d ; f = e ^ ( e << 4 ); r = ( c >> 8 ) ^ ( f << 8 ) ^ ( f << 3 ) ^ ( f >> 4 ); | uint8_t d , s , p ; uint16_t c , r , t ; … S = d ^ ( c >> 8 ); p = s ^ ( s >> 4 ); p = p ^ ( p >> 2 ); p = p ^ ( p >> 1 ); p = p & 1 ; t = p | ( s << 1 ); r = ( c << 8 ) ^ ( t << 15 ) ^ t ^ ( t << 1 ); | uint8_t d , e , p ; uint16_t c , r , f ; … E = c ^ d ; p = e ^ ( e >> 4 ); p = p ^ ( p >> 2 ); p = p ^ ( p >> 1 ); p = p & 1 ; f = e | ( p << 8 ); r = ( c >> 8 ) ^ ( f << 6 ) ^ ( f << 7 ) ^ ( f >> 8 ); |
Cálculo de dos pasos
Como el polinomio CRC-32 tiene una gran cantidad de términos, al calcular el resto un byte a la vez, cada bit depende de varios bits de la iteración anterior. En implementaciones de hardware en paralelo de bytes, esto requiere puertas XOR de entrada múltiple o en cascada, lo que aumenta el retardo de propagación .
Para maximizar la velocidad de cálculo, se puede calcular un resto intermedio pasando el mensaje a través de un registro de desplazamiento de 123 bits. El polinomio es un múltiplo cuidadosamente seleccionado del polinomio estándar, de modo que los términos (tomas de retroalimentación) están muy espaciados y ningún bit del resto se XOR más de una vez por iteración de byte. Por lo tanto, solo se necesitan puertas XOR de dos entradas, las más rápidas posibles. Finalmente, el resto intermedio se divide por el polinomio estándar en un segundo registro de desplazamiento para producir el resto CRC-32. [11]
Comprobación de una pasada
Al agregar un CRC a un mensaje, es posible separar el CRC transmitido, volver a calcularlo y verificar el valor recalculado con el transmitido. Sin embargo, una técnica más simple se usa comúnmente en hardware.
Cuando el CRC se transmite con el orden de bytes correcto (que coincide con la convención de ordenación de bits elegida), un receptor puede calcular un CRC general, sobre el mensaje y el CRC, y si son correctos, el resultado será cero. Esta posibilidad es la razón por la que la mayoría de los protocolos de red que incluyen un CRC lo hacen antes del delimitador final; no es necesario saber si el final del paquete es inminente para comprobar el CRC.
Variantes de CRC
En la práctica, la mayoría de los estándares especifican preestablecer el registro en todos unos e invertir el CRC antes de la transmisión. Esto no tiene ningún efecto sobre la capacidad de un CRC para detectar bits cambiados, pero le da la capacidad de notar bits que se agregan al mensaje.
Preestablecido en −1
La matemática básica de un CRC acepta (considera como transmitidos correctamente) mensajes que, cuando se interpretan como polinomios, son múltiplos del polinomio CRC. Si se anteponen algunos bits 0 iniciales a dicho mensaje, no cambiarán su interpretación como polinomio. Esto equivale al hecho de que 0001 y 1 son el mismo número.
Pero si el mensaje que se transmite se preocupa por los 0 bits iniciales, la incapacidad del algoritmo CRC básico para detectar tal cambio es indeseable. Si es posible que un error de transmisión pueda agregar tales bits, una solución simple es comenzar con el rem
registro de desplazamiento establecido en un valor distinto de cero; por conveniencia, normalmente se utiliza el valor de todos unos. Esto es matemáticamente equivalente a complementar (NOT binario) los primeros n bits del mensaje, donde n es el número de bits en el registro CRC.
Esto no afecta la generación y verificación de CRC de ninguna manera, siempre que tanto el generador como el verificador usen el mismo valor inicial. Cualquier valor inicial distinto de cero servirá, y algunos estándares especifican valores inusuales, [12] pero el valor de todos unos (-1 en binario de complemento a dos) es con mucho el más común. Tenga en cuenta que una generación / verificación de CRC de una pasada aún producirá un resultado de cero cuando el mensaje sea correcto, independientemente del valor preestablecido.
Post-invertir
El mismo tipo de error puede ocurrir al final de un mensaje, aunque con un conjunto de mensajes más limitado. Agregar 0 bits a un mensaje equivale a multiplicar su polinomio por x , y si anteriormente era un múltiplo del polinomio CRC, el resultado de esa multiplicación también lo será. Esto es equivalente al hecho de que, dado que 726 es un múltiplo de 11, también lo es 7260.
Se puede aplicar una solución similar al final del mensaje, invirtiendo el registro CRC antes de que se agregue al mensaje. Una vez más, cualquier cambio distinto de cero servirá; invertir todos los bits (XOR con un patrón de todos unos) es simplemente lo más común.
Esto tiene un efecto en la verificación CRC de una pasada: en lugar de producir un resultado de cero cuando el mensaje es correcto, produce un resultado fijo distinto de cero. (Para ser precisos, el resultado es el CRC (sin un ajuste preestablecido distinto de cero, pero con post-inversión) del patrón de inversión.) Una vez que se ha obtenido esta constante (más fácilmente realizando una generación / verificación de CRC de una pasada en un mensaje arbitrario), se puede usar directamente para verificar la exactitud de cualquier otro mensaje verificado usando el mismo algoritmo CRC.
Ver también
Categoría general
- Error al corregir el código
- Lista de funciones hash
- La paridad es equivalente a un CRC de 1 bit con polinomio x +1 .
Sumas de comprobación no CRC
- Adler-32
- Suma de comprobación de Fletcher
Referencias
- ^ Dubrova, Elena; Mansouri, Shohreh Sharif (mayo de 2012). "Un enfoque basado en BDD para construir LFSR para codificación CRC paralela" . Actas del Simposio Internacional IEEE sobre Lógica de Valores Múltiples : 128-133. ISBN 978-0-7695-4673-5.
- ^ a b Williams, Ross N. (24 de septiembre de 1996). "Una guía indolora de algoritmos de detección de errores CRC V3.00" . Archivado desde el original el 27 de septiembre de 2006 . Consultado el 16 de febrero de 2016 .
- ^ Sarwate, Dilip V. (agosto de 1998). "Cálculo de comprobaciones de redundancia cíclica mediante búsqueda de tablas". Comunicaciones de la ACM . 31 (8): 1008–1013. doi : 10.1145 / 63030.63037 .
- ^ "Especificación de gráficos de red portátiles (PNG) (segunda edición): anexo D, implementación de código de redundancia cíclica de muestra" . W3C . 2003-11-10 . Consultado el 16 de febrero de 2016 .
- ^ Kounavis, Michael E .; Berry, Frank L. (27 a 30 de junio de 2005). Un enfoque sistemático para la construcción de generadores CRC de alto rendimiento basados en software (PDF) . 2013 Simposio IEEE sobre Computadoras y Comunicaciones (ISCC). Cartagena, Murcia, España. págs. 855–862. doi : 10.1109 / ISCC.2005.18 . ISBN 0-7695-2373-0.
- ^ Berry, Frank L .; Kounavis, Michael E. (noviembre de 2008). "Nuevos algoritmos basados en búsqueda de tablas para la generación de CRC de alto rendimiento". Transacciones IEEE en computadoras . 57 (11): 1550-1560. doi : 10.1109 / TC.2008.85 .
- ^ Generación CRC de alto octanaje con el algoritmo Intel Slicing-by-8 (PDF) (Informe técnico). Intel . Archivado desde el original (PDF) el 22 de julio de 2012.
- ^ https://www.kernel.org/doc/Documentation/crc32.txt
- ^ Menon-Sen, Abhijit (20 de enero de 2017). "¿Quién inventó el algoritmo de corte por N CRC32?" .
- ^ Jon Buller (15 de marzo de 1996). "Re: 8051 y CRC-CCITT" . Grupo de noticias : comp.arch.embedded . Usenet: [email protected] . Consultado el 16 de febrero de 2016 .
- ^ Glaise, René J. (20 de enero de 1997). "Un cálculo de dos pasos del código de redundancia cíclica CRC-32 para redes ATM" . Revista de investigación y desarrollo de IBM . Armonk, Nueva York : IBM . 41 (6): 705. doi : 10.1147 / rd.416.0705 . Archivado desde el original el 30 de enero de 2009 . Consultado el 16 de febrero de 2016 .
- ^ Por ejemplo, RFID de baja frecuencia Hoja de datos TMS37157 - Dispositivo de interfaz pasiva de baja frecuencia con EEPROM e interfaz de transpondedor de 134,2 kHz (PDF) , Texas Instruments , noviembre de 2009, p. 39 , recuperado el 16 de febrero de 2016 ,
el generador CRC se inicializa con el valor 0x3791 como se muestra en la Figura 50.
enlaces externos
- JohnPaul Adamovsky. "Código redundante cíclico de 64 bits - XOR División larga a búsqueda de tabla de bytes" .
- Andrew Kadarch, Bob Jenkins. "Implementación CRC eficiente (~ 1 ciclo de CPU por byte)" .