Cálculo de comprobaciones de redundancia cíclica

El cálculo de una comprobació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 la división larga de la cadena de mensaje binario , con un número fijo de ceros añadidos, por la cadena del "polinomio generador", excepto que las operaciones OR exclusivas reemplazan a las restas. La división de este tipo se realiza eficientemente 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 ofuscado ^{[ 2 ]} ) a través del paralelismo byte a byte y las compensaciones espacio-temporales .

Ejemplo de generación de un CRC de 8 bits . El generador es un registro de desplazamiento de tipo Galois con puertas XOR ubicadas según las potencias (números blancos) de x en el polinomio generador. La secuencia de mensajes puede tener cualquier longitud. Después de que se haya desplazado a través del registro, seguido de 8 ceros, el resultado en el registro es la suma de verificación.

Verificación de los datos recibidos mediante suma de comprobación. El mensaje recibido se procesa mediante el mismo registro que el generador, pero en lugar de ceros, se le adjunta la suma de comprobación recibida. Los datos correctos dan como resultado ceros; un bit corrupto, ya sea en el mensaje o en la suma de comprobación, daría un resultado diferente, indicando que se ha producido un error.

Diversos estándares CRC extienden el algoritmo de división polinómica especificando un valor inicial para el registro de desplazamiento, un paso final de OR exclusivo y, lo más importante, un orden de bits ( endianness ). Como resultado, el código que se observa 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 polinómica en hardware, supongamos que estamos intentando calcular un CRC de 8 bits de un mensaje de 8 bits formado por el carácter ASCII "W", que es binario 01010111 ₂ , decimal 87 ₁₀ , o hexadecimal 57 ₁₆ . Para ilustrarlo, utilizaremos el polinomio CRC-8-ATM ( HEC ). $x^{8}+x^{2}+x+1$ . Escribiendo el primer bit transmitido (el coeficiente de la potencia más alta de $x$ ) a la izquierda, esto corresponde a la cadena de 9 bits "100000111".

El valor de byte 57 ₁₆ se puede transmitir en dos órdenes diferentes, dependiendo de la convención de ordenación de bits utilizada. Cada una genera un polinomio de mensaje diferente. $M(x)$ . Msbit-primero, esto es $x^{6}+x^{4}+x^{2}+x+1$ = 01010111, mientras que lsbit-first, es $x^{7}+x^{6}+x^{5}+x^{3}+x$ = 11101010. Estos se pueden multiplicar luego por $x^{8}$ para producir dos polinomios de mensaje de 16 bits $x^{8}M(x)$ .

El cálculo del resto consiste entonces en restar múltiplos del polinomio generador. $G(x)$ Esto es similar a la división larga decimal, pero aún más simple, ya que los únicos múltiplos posibles en cada paso son 0 y 1, y las restas toman prestado "desde el infinito" en lugar de reducir los dígitos superiores. Como no nos interesa el cociente, no es necesario registrarlo.

Observe que, tras cada resta, los bits se dividen en tres grupos: al principio, un grupo compuesto enteramente por ceros; al final, un grupo que permanece inalterado respecto al original; y un grupo intermedio sombreado en azul, considerado "interesante". Este último grupo tiene una longitud de 8 bits, que coincide con el grado del polinomio. En cada paso, se resta el múltiplo correspondiente del polinomio para aumentar en un bit el grupo de ceros y reducir en un bit el grupo que permanece inalterado, hasta que solo queda el resto final.

En el ejemplo msbit-first, el polinomio restante es $x^{7}+x^{5}+x$ . Convirtiendo a un número hexadecimal usando la convención de que la potencia más alta de x es el bit más significativo; esto es A2 ₁₆ . En el bit menos significativo primero, el resto es $x^{7}+x^{4}+x^{3}$ . Al convertirlo a hexadecimal usando la convención de que la mayor potencia de x es el bit menos significativo, esto es 19 ₁₆ .

Implementación

Escribir el mensaje completo en cada paso, como se hizo en el ejemplo anterior, es muy tedioso. Las implementaciones eficientes utilizan un $n$ Registro de desplazamiento de bits para almacenar solo los bits de interés. Multiplicando el polinomio por $x$ es equivalente a desplazar el registro un lugar, ya que los coeficientes no cambian de valor, sino que solo se mueven al siguiente término del polinomio.

Aquí se presenta un primer borrador de pseudocódigo para calcular un CRC de n bits. Utiliza un tipo de dato compuesto artificial para polinomios, donde xno es una variable entera, sino un constructor que genera un objeto Polynomial que puede sumarse, multiplicarse y elevarse a la potencia de dos. Sumar dos polinomios es realizar la operación OR exclusiva de los coeficientes de cada término coincidente de ambos polinomios.xor

función crc( matriz de bits bitString[1..len], int len) { remainderPolynomial := polynomialForm(bitString[1..n]) // First n bits of the message// A popular variant complements remainderPolynomial here; see § Preset to −1 belowfor i from 1 to len { remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x⁰// Define bitString[k]=0 for k>lenif coefficient of xⁿ of remainderPolynomial = 1 { remainderPolynomial := remainderPolynomial xor generatorPolynomial } } // A popular variant complements remainderPolynomial here; see § Post-invert belowreturn remainderPolynomial }

Code fragment 1: Simple polynomial division

Note that this example code avoids the need to specify a bit-ordering convention by not using bytes; the input bitString is already in the form of a bit array, and the remainderPolynomial is manipulated in terms of polynomial operations; the multiplication by $x$ could be a left or right shift, and the addition of bitString[i+n] is done to the $x^{0}$ coefficient, which could be the right or left end of the register.

This code has two disadvantages. First, it actually requires an n+1-bit register to hold the remainderPolynomial so that the $x^{n}$ coefficient can be tested. More significantly, it requires the bitString to be padded with n zero bits.

The first problem can be solved by testing the $x^{n-1}$ coefficient of the remainderPolynomial before it is multiplied by $x$ .

The second problem could be solved by doing the last n iterations differently, but there is a more subtle optimization which is used universally, in both hardware and software implementations.

Because the XOR operation used to subtract the generator polynomial from the message is commutative and associative, it does not matter in what order the various inputs are combined into the remainderPolynomial. And specifically, a given bit of the bitString does not need to be added to the remainderPolynomial until the very last instant when it is tested to determine whether to xor with the generatorPolynomial.

This eliminates the need to preload the remainderPolynomial with the first n bits of the message, as well:

function crc(bit array bitString[1..len], int len) { remainderPolynomial := 0 // Una variante popular complementa remainderPolynomial aquí; ver §  Preestablecido a −1 a continuación para i de 1 a len { restablePolynomial := restablePolynomial xor (bitstring[i] * x ⁿ⁻¹ ) si (coeficiente de x ⁿ⁻¹ de restablePolynomial) = 1 { polinomioresto := (polinomioresto * x ) xor polinomio generador } demás { polinomioresto := (polinomioresto * x ) } } // Una variante popular complementa remainderPolynomial aquí; ver §  Post-inversión más abajo return remainderPolynomial }

Fragmento de código 2: División de polinomios con XOR de mensaje diferido

Esta es la implementación estándar de CRC por hardware bit a bit, y merece la pena estudiarla; una vez que se entiende por qué calcula exactamente el mismo resultado que la primera versión, las optimizaciones restantes son bastante sencillas. Si remainderPolynomialtiene solo n bits de longitud, entonces el $x^{n}$ Los coeficientes de it y de generatorPolynomialsimplemente se descartan. Por eso, normalmente verás polinomios CRC escritos en binario con el coeficiente principal omitido.

En software, conviene tener en cuenta que, si bien se puede retrasar la lectura xorde cada bit hasta el último momento, también es posible hacerlo antes. Generalmente, resulta conveniente realizar la lectura xorbyte a byte , incluso en una implementación bit a bit. Aquí, tomamos la entrada en bytes de 8 bits:

función crc( array de bytes cadena[1..len], int len) { resto del polinomio := 0 // Una variante popular complementa remainderPolynomial aquí; ver §  Preestablecido a −1 a continuación para i de 1 a len { restablePolynomial := restablePolynomial xor polynomialForm (string[i]) * x ⁿ⁻⁸para j de 1 a 8 { // Suponiendo 8 bits por byte si el coeficiente de x ⁿ⁻¹ de restablePolynomial = 1 { polinomioresto := (polinomioresto * x ) xor polinomio generador } demás { polinomioresto := (polinomioresto * x ) } } } // Una variante popular complementa remainderPolynomial aquí; ver §  Post-inversión más abajo return remainderPolynomial }

Fragmento de código 3: División de polinomios con XOR de mensajes byte a byte

Esta suele ser la implementación de software más compacta, utilizada en microcontroladores cuando el espacio es un bien preciado en comparación con la velocidad.

Orden de bits (endianness)

When implemented in bit serial hardware, the generator polynomial uniquely describes the bit assignment; the first bit transmitted is always the coefficient of the highest power of $x$ , and the last $n$ bits transmitted are the CRC remainder $R(x)$ , starting with the coefficient of $x^{n-1}$ and ending with the coefficient of $x^{0}$ , a.k.a. the coefficient of 1.

However, when bits are processed a byte at a time, such as when using parallel transmission, byte framing as in 8B/10B encoding or RS-232-style asynchronous serial communication, or when implementing a CRC in software, it is necessary to specify the bit ordering (endianness) of the data; which bit in each byte is considered "first" and will be the coefficient of the higher power of $x$ .

If the data is destined for serial communication, it is best to use the bit ordering the data will ultimately be sent in. This is because a CRC's ability to detect burst errors is based on proximity in the message polynomial $M(x)$ ; if adjacent polynomial terms are not transmitted sequentially, a physical error burst of one length may be seen as a longer burst due to the rearrangement of bits.

For example, both IEEE 802 (ethernet) and RS-232 (serial port) standards specify least-significant bit first (little-endian) transmission, so a software CRC implementation to protect data sent across such a link should map the least significant bits in each byte to coefficients of the highest powers of $x$ . On the other hand, floppy disks and most hard drives write the most significant bit of each byte first.

The lsbit-first CRC is slightly simpler to implement in software, so is somewhat more commonly seen, but many programmers find the msbit-first bit ordering easier to follow. Thus, for example, the XMODEM-CRC extension, an early use of CRCs in software, uses an msbit-first CRC.

So far, the pseudocode has avoided specifying the ordering of bits within bytes by describing shifts in the pseudocode as multiplications by $x$ and writing explicit conversions from binary to polynomial form. In practice, the CRC is held in a standard binary register using a particular bit-ordering convention. In msbit-first form, the most significant binary bits will be sent first and so contain the higher-order polynomial coefficients, while in lsbit-first form, the least-significant binary bits contain the higher-order coefficients. The above pseudocode can be written in both forms. For concreteness, this uses the 16-bit CRC-16-CCITT polynomial $x^{16}+x^{12}+x^{5}+1$ :

// El bit más significativo primero (big-endian) // (x ¹⁶ )+x ¹² +x ⁵ +1 = (1) 0001 0000 0010 0001 = 0x1021 function crc( byte array string[1..len], int len) { rem := 0 // Una variante popular complementa rem aquí para i desde 1 hasta 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 { // Probar el coeficiente x ¹⁵ rem := (rem leftShift 1) xor 0x1021 } demás { rem := rem leftShift 1 } rem := rem y 0xffff // Recortar 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, bit más significativo primero.

// Bit menos significativo primero (little-endian) // 1+x ⁵ +x ¹² +(x ¹⁶ ) = 1000 0100 0000 1000 (1) = 0x8408 function crc( byte array string[1..len], int len) { rem := 0 // Una variante popular complementa rem aquí para i desde 1 hasta len { rem := rem xor string[i] para j de 1 a 8 { // Suponiendo 8 bits por byte si rem y 0x0001 { // Probar el coeficiente x ¹⁵ rem := (rem rightShift 1) xor 0x8408 } demá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 desplazar string[i]antes del xor. En cualquier caso, asegúrese de transmitir los bytes del CRC en el orden que coincida con la convención de ordenación de bits elegida.

Cálculo multibit mediante tablas de búsqueda

Las implementaciones de software más rápidas procesan más de un bit de dividendo por iteración utilizando tablas de búsqueda , indexadas por los coeficientes de orden más alto de rem, para memorizar los pasos de división por bit.

Algoritmo de Sarwate (tabla de búsqueda única)

La técnica más común utiliza una tabla de búsqueda de 256 entradas para procesar 8 bits de entrada por iteración. ^{[ 3 ]} Esto reemplaza el cuerpo del bucle externo (sobre i) con:

// Msbit-first rem = (rem leftShift 8) xor big_endian_table[string[i] xor ((los 8 bits más a la izquierda de rem) rightShift (n-8))] // Lsbit-first rem = (rem rightShift 8) xor little_endian_table[string[i] xor (los 8 bits más a la derecha de rem)]

Fragmento de código 6: Núcleos de la división basada en tablas

El uso de una tabla de 256 entradas suele ser lo más conveniente, pero se pueden usar otros tamaños. En microcontroladores pequeños, usar una tabla de 16 entradas para procesar cuatro bits a la vez proporciona una mejora de velocidad útil al tiempo que mantiene la tabla pequeña. En computadoras con amplio almacenamiento, unaSe puede utilizar una tabla de 65 536 entradas para procesar 16 bits a la vez.

Generación de la tabla de búsqueda

El software para generar la tabla de búsqueda es tan pequeño y rápido que suele ser más rápido calcularla al iniciar el programa que cargar tablas precalculadas desde el almacenamiento. Una técnica popular es usar el código bit a bit 256 veces para generar los CRC de los 256 posibles bytes de 8 bits. ^{[ 4 ]} Sin embargo, esto se puede optimizar significativamente aprovechando la propiedad de que . Solo las entradas de la tabla correspondientes a potencias de dos necesitan ser calculadas directamente.table[i xor j] == table[i] xor table[j]

En el siguiente código de ejemplo, crccontiene el valor de table[i]:

big_endian_table[0] := 0 crc := 0x8000 // Suponiendo un polinomio de 16 bits i := 1 hacer { si crc y 0x8000 { crc := (crc leftShift 1) xor 0x1021 // El polinomio CRC } else { crc := crc Mayús izquierda 1 } // crc es el valor de big_endian_table[i] ; deja que j itere sobre las entradas ya inicializadas para j desde 0 hasta i−1 { big_endian_table[i + j] := crc xor big_endian_table[j]; } i := i desplazamiento a la izquierda 1 } mientras i < 256

Fragmento de código 7: Generación de tabla CRC byte a byte, con el bit más significativo primero.

little_endian_table[0] := 0 crc := 1; i := 128 hacer { si crc y 1 { crc := (crc rightShift 1) xor 0x8408 // El polinomio CRC } else { crc := crc Mayús derecha 1 } // crc es el valor de little_endian_table[i] ; deja que j itere sobre las entradas ya inicializadas para j desde 0 hasta 255 por 2 × i { little_endian_table[i + j] := crc xor little_endian_table[j]; } i := i desplazamiento a la derecha 1 } mientras i > 0

Fragmento de código 8: Generación de tabla CRC byte a byte, lsbit-first

En estos ejemplos de código, el índice de la tabla i + jes equivalente a ; puede utilizar la forma que le resulte más conveniente.i xor j

Ejemplo de CRC-32

Uno de los polinomios CRC más comunes es el CRC-32 , utilizado, entre otros, por Ethernet , FDDI , ZIP y otros formatos de archivo , así como por el formato de imagen PNG . Su polinomio se puede escribir con el bit más significativo primero como 0x04C11DB7, o con el bit menos significativo primero como 0xEDB88320.

Este es un ejemplo práctico de la variante CRC-32 de CRC. ^{[ 5 ]}

Una fuente alternativa es la página web del W3C sobre PNG, que incluye un apéndice con una implementación corta y sencilla basada en tablas en C de CRC-32. ^{[ 4 ]} Observará que el código corresponde al algoritmo de byte a byte lsbit-first presentado aquí, y la tabla se genera utilizando el código bit a byte.

Función CRC32  Entrada: datos: Bytes  // Matriz de bytes Salida: crc32: UInt32  // Valor CRC-32 sin signo de 32 bits // Inicializar CRC-32 al valor inicial crc32 ← 0xFFFFFFFF  para cada byte en datos hacer nLookupIndex ← (crc32 xor byte) y 0xFF crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] // CRCTable es una matriz de 256 constantes de 32 bits // Finaliza el valor CRC-32 invirtiendo todos los bits crc32 ← crc32 xor 0xFFFFFFFF return crc32

En C, el algoritmo se ve así:

#include <stdint.h> // uint32_t, uint8_t #include <stddef.h> // size_testático uint32_t CRCTable [ 256 ];// La inicialización por múltiples hilos es redundante, pero segura. static void CRC32_init ( void ) { uint32_t crc32 = 1 ; // C garantiza que CRCTable[0] ya es igual a 0. for ( unsigned int i = 128 ; i ; i >>= 1 ) { crc32 = ( crc32 >> 1 ) ^ ( crc32 & 1 ? 0xedb88320 : 0 ); for ( unsigned int j = 0 ; j < 256 ; j += 2 * i ) CRCTable [ i + j ] = crc32 ^ CRCTable [ j ]; } }uint32_t CRC32 ( const uint8_t data [], size_t data_length ) { uint32_t crc32 = 0xFFFFFFFFu ;if ( CRCTable [ 255 ] == 0 ) CRC32_init (); for ( size_t i = 0 ; i < data_length ; i ++ ) { crc32 ^= data [ i ]; crc32 = ( crc32 >> 8 ) ^ CRCTable [ crc32 & 0xFF ]; } // Finalizar el valor CRC-32 invirtiendo todos los bits crc32 ^= 0xFFFFFFFFu ; return crc32 ; }

Segmentación de bytes mediante varias tablas

Existe un algoritmo de segmentación por n bits (normalmente por 8 bits para CRC32) que suele duplicar o triplicar 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. Esto maximiza el rendimiento en procesadores superescalares . ^{[ 6 ]}^{[ 7 ]}^{[ 8 ]}^{[ 9 ]}

No está claro quién inventó realmente el algoritmo. ^{[ 10 ]}

Para comprender las ventajas, comencemos con el caso de segmentación por 2. Deseamos calcular un CRC de dos bytes (16 bits) a la vez, pero el enfoque estándar basado en tablas requeriría una tabla de 65536 entradas, un tamaño inconveniente. Como se menciona en la sección Generación de la tabla de búsqueda , las tablas CRC tienen la propiedad de que . Podemos usar esta identidad para reemplazar la tabla grande por dos tablas de 256 entradas: .table[i xor j] = table[i] xor table[j]table[i + 256 × j] = table_low[i] xor table_high[j]

Así pues, la tabla grande no se almacena explícitamente, sino que en cada iteración se calcula el valor CRC que estaría presente al combinar los valores de dos tablas más pequeñas. Es decir, el índice de 16 bits se divide en dos índices de 8 bits. A primera vista, esto parece inútil; ¿por qué realizar dos búsquedas en tablas separadas, cuando el algoritmo estándar de procesamiento byte a byte realizaría dos búsquedas en la misma tabla?

La diferencia radica en el paralelismo a nivel de instrucciones . En el algoritmo estándar, el índice de cada búsqueda depende del valor obtenido en la anterior. Por lo tanto, la segunda búsqueda no puede comenzar hasta que la primera haya finalizado.

Cuando se utilizan tablas segmentadas, ambas búsquedas pueden comenzar al mismo tiempo. Si el procesador puede realizar dos cargas en paralelo (los microprocesadores de la década de 2020 pueden gestionar más de 100 cargas en curso), esto tiene el potencial de duplicar la velocidad del bucle interno.

Esta técnica obviamente puede extenderse a tantas rebanadas como el procesador pueda aprovechar.

Cuando el ancho de segmentación es igual al tamaño del CRC, se produce una ligera mejora en la velocidad. En la parte del algoritmo básico de Sarwate donde el valor CRC anterior se desplaza según el tamaño de la búsqueda en la tabla, dicho valor se elimina por completo (lo que queda es todo cero), por lo que la operación XOR puede eliminarse de la ruta crítica.

El bucle interno resultante de segmentación por n consta de:

Realiza una operación XOR entre el CRC actual y los siguientes n bytes del mensaje.
buscar cada byte del valor resultante en las n tablas de segmentos, luego
Aplica la operación XOR a los n resultados para obtener el siguiente CRC.

Esto sigue teniendo la particularidad de que todas las cargas del segundo paso deben completarse antes de que pueda comenzar la siguiente iteración, lo que provoca pausas regulares durante las cuales el subsistema de memoria del procesador (en particular, la caché de datos) no se utiliza. Sin embargo, cuando el ancho de segmentación supera el tamaño del CRC, se observa una segunda aceleración significativa.

Esto se debe a que una parte de los resultados del primer paso ya no depende de ninguna iteración anterior. Al aplicar la operación XOR a un CRC de 32 bits con un mensaje de 64 bits, la mitad del resultado es simplemente una copia del mensaje. Si se programa con cuidado (para evitar crear una dependencia de datos falsa ), la mitad de las cargas de la tabla de segmentos pueden comenzar antes de que finalice la iteración anterior del bucle. El resultado es suficiente trabajo para mantener el subsistema de memoria del procesador continuamente ocupado, lo que permite alcanzar el máximo rendimiento. Como se mencionó, en los microprocesadores posteriores al año 2000, la segmentación por 8 suele ser suficiente para alcanzar este nivel.

No es necesario que las porciones tengan un ancho de 8 bits. Por ejemplo, sería perfectamente posible calcular un CRC de 64 bits en 64 bits utilizando un algoritmo de segmentación de 9, empleando 9 tablas de búsqueda de 128 entradas para gestionar 63 bits, y el bit 64 se gestionaría mediante el algoritmo bit a bit (que es, en la práctica, una tabla de búsqueda de 1 bit y 2 entradas). Esto reduciría casi a la mitad el tamaño de la tabla (de 8 × 256 = 2048 entradas a 9 × 128 = 1152) a costa de una carga adicional dependiente de datos por iteración.

Computación multibit sin tablas de búsqueda

La actualización paralela de un byte o una palabra a la vez también se puede realizar explícitamente, sin una tabla. ^{[ 11 ]} Para cada bit se resuelve una ecuación después de que se hayan desplazado 8 bits.

Los pasos de reducción múltiples normalmente se expresan como una operación matricial. Un desplazamiento y reducción módulo un grado- $n$ polinomio generador $G(x)$ es equivalente a multiplicar por el $n\times n$ matriz complementaria $A=C(G)$ . $r$ Los pasos se escriben como la matriz $A^{r}=C(G)^{r}$ .

Esta técnica se usa normalmente en implementaciones de hardware de alta velocidad, pero es práctica en software para polinomios CRC pequeños o dispersos. ^{[ 12 ]} Para polinomios CRC grandes y densos, el código se vuelve impracticablemente largo.

Ejemplos de polinomios dispersos

Las siguientes tablas enumeran las ecuaciones que procesan 8 bits a la vez módulo algunos polinomios de uso común, utilizando los siguientes símbolos:

Cálculo en dos pasos

Para polinomios densos, como el polinomio CRC-32, calcular el resto byte a byte produce ecuaciones donde cada bit depende de hasta 8 bits de la iteración anterior. En implementaciones de hardware en paralelo de bytes, esto requiere puertas XOR de 8 entradas o en cascada, las cuales tienen un retardo de puerta considerable .

Para maximizar la velocidad de cálculo, se puede calcular un resto intermedio calculando primero el CRC del mensaje módulo un polinomio disperso que sea múltiplo del polinomio CRC. Para CRC-32, el polinomio x ¹²³ + x ¹¹¹ + x ⁹² + x ⁸⁴ + x 64 + x ⁴⁶ + x ²³⁺ 1 tiene la propiedad de que sus términos (puntos de retroalimentación) están separados por al menos 8 posiciones. Por lo tanto, un registro de desplazamiento de 123 bits puede avanzar 8 bits por iteración utilizando solo puertas XOR de dos entradas, lo más rápido posible. Finalmente, el resto intermedio se puede reducir módulo el polinomio estándar en un segundo registro de desplazamiento más lento (una vez por CRC, en lugar de una vez por byte de entrada) para obtener el resto CRC-32. ^[¹³^]

Si se permiten compuertas XOR de 3 o 4 entradas, se pueden utilizar polinomios intermedios más cortos de grado 71 o 53, respectivamente.

transformación del espacio de estados

La técnica anterior funciona, pero requiere un gran registro de desplazamiento intermedio. Una técnica más eficiente en términos de hardware que se ha utilizado para redes de alta velocidad desde aproximadamente el año 2000 es la transformación del espacio de estados . El bucle interno de un $r$ El motor CRC bit a bit consiste en actualizar repetidamente el resto intermedio. $y$ para reflejar una $r$ -parte de bits del mensaje $y_{i}$ usando:

y_{i}=A^{r}\cdot (y_{i-1}\oplus x_{i}).

El desafío de implementación es que la multiplicación de matrices por $A^{r}$ debe realizarse en $r$ tiempos de bits. En general, como $r$ a medida que aumenta, también lo hace la complejidad de esta multiplicación, lo que resulta en una aceleración máxima de aproximadamente $r/2.$ ^{[ 14 ]} Para mejorar esto, primero descomponga esta ecuación usandola propiedad distributivaen:

y_{i}=A^{r}y_{i-1}\oplus A^{r}x_{i}.

Luego, encontramos una matriz invertible. $T$ y realizar un cambio de base , multiplicando el estado intermedio por $T^{-1}$ . Por lo tanto, la iteración queda así:

T^{-1}y_{i}=T^{-1}A^{r}T(T^{-1}y_{i-1})\oplus T^{-1}A^{r}x_{i}.

El CRC final se recupera como $y=T(T^{-1}y).$ Es importante tener en cuenta que la multiplicación de entrada por $T^{-1}A^{r}$ y la multiplicación de la salida por $T$ no son críticos en cuanto al tiempo, ya que se pueden segmentar a la profundidad que sea necesaria para cumplir con el objetivo de rendimiento. Solo la multiplicación central por $T^{-1}A^{r}T$ debe completarse dentro de $r$ tiempos de bits. Es posible encontrar una matriz de transformación $T$ lo que le da la forma de una matriz compañera. En otras palabras, se puede implementar utilizando las mismas puertas XOR de 2 entradas (rápidas) que el algoritmo bit a bit. ^{[ 15 ]}^{[ 16 ]} Esto permite una $r$ CRC paralelo de bits para operar $r$ veces más rápido que una implementación serial de 1 bit.

Hay muchas posibilidades $n\times n$ matrices de transformación con esta propiedad, por lo que es posible elegir una que también minimice la complejidad de las matrices de entrada y salida. $T^{-1}A^{r}$ y $T$ . ^{[ 16 ]}

Computación por bloques

El cálculo por bloques del resto se puede realizar en hardware para cualquier polinomio CRC factorizando la matriz de transformación del espacio de estados necesaria para calcular el resto en dos matrices de Toeplitz más simples . ^{[ 17 ]}

Verificación de una sola pasada

Al añadir un CRC a un mensaje, es posible separar el CRC transmitido, recalcularlo y comparar el valor recalculado con el original. Sin embargo, en hardware se suele utilizar una técnica más sencilla.

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 global, sobre el mensaje y el CRC, y si son correctos, el resultado será cero. ^{[ 18 ]} 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.

De hecho, algunos protocolos utilizan el CRC como delimitador de mensajes, una técnica denominada enmarcado basado en CRC . (Esto requiere múltiples tramas para detectar la adquisición o la pérdida de la trama, por lo que se limita a aplicaciones donde las tramas tienen una longitud conocida y el contenido de las tramas es lo suficientemente aleatorio como para que los CRC válidos en datos desalineados sean poco frecuentes).

variantes de CCR

En la práctica, la mayoría de los estándares especifican preconfigurar el registro a todos unos e invertir el CRC antes de la transmisión. Esto no afecta la capacidad del CRC para detectar bits modificados, pero le permite detectar bits añadidos al mensaje.

Preestablecido a −1

La lógica matemática básica de un CRC acepta (considera como correctamente transmitidos) mensajes que, al interpretarse como un polinomio, son múltiplos del polinomio CRC. Si se añaden bits 0 al principio de dicho mensaje, no se modificará su interpretación como polinomio. Esto es equivalente a que 0001 y 1 sean el mismo número.

Pero si el mensaje transmitido sí tiene en cuenta los bits iniciales a cero, la incapacidad del algoritmo CRC básico para detectar dicho cambio resulta indeseable. Si existe la posibilidad de que un error de transmisión añada estos bits, una solución sencilla consiste en comenzar con el remregistro de desplazamiento configurado a un valor distinto de cero; por conveniencia, se suele utilizar el valor de 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 en absoluto a la generación y verificación de CRC, siempre que tanto el generador como el verificador utilicen el mismo valor inicial. Cualquier valor inicial distinto de cero es válido, y algunos estándares especifican valores inusuales ^{[ 19 ]} , pero el valor de todos unos (−1 en binario de complemento a dos) es, con mucho, el más común. Cabe destacar que una generación/verificación de CRC de una sola pasada seguirá produciendo un resultado de cero cuando el mensaje sea correcto, independientemente del valor preestablecido.

Post-inversión

El mismo tipo de error puede ocurrir al final de un mensaje, aunque con un conjunto más limitado de mensajes. Agregar bits cero a un mensaje equivale a multiplicar su polinomio por x , y si previamente era un múltiplo del polinomio CRC, el resultado de esa multiplicación también lo será. Esto es equivalente a que, dado que 726 es un múltiplo de 11, 7260 también lo es.

Se puede aplicar una solución similar al final del mensaje, invirtiendo el registro CRC antes de agregarlo al mensaje. Nuevamente, cualquier cambio distinto de cero servirá; invertir todos los bits (mediante una operación XOR con un patrón de unos) es simplemente la opción más común.

Esto afecta a la comprobación CRC de una sola 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, con cero preestablecido pero con inversión posterior, del patrón de inversión). Una vez obtenida esta constante (por ejemplo, mediante la generación/comprobación de un CRC de una sola pasada en un mensaje arbitrario), se puede utilizar directamente para verificar la corrección de cualquier otro mensaje comprobado con el mismo algoritmo CRC.

Véase también

Categoría general

Código de corrección de errores
Lista de funciones hash
La paridad es equivalente a un CRC de 1 bit con polinomio $x +1$ .

sumas de verificación sin CRC

Referencias

↑ Dubrova, Elena; Mansouri, Shohreh Sharif (mayo de 2012). "Un enfoque basado en BDD para la construcción de LFSRS para codificación CRC paralela" . 2012 IEEE 42nd International Symposium on Multiple-Valued Logic . pp. 128–133 . doi : 10.1109/ISMVL.2012.20 . ISBN 978-0-7695-4673-5. S2CID 27306826 .
1 2 Williams, Ross N. (1996-09-24). "Una guía sencilla para los algoritmos de detección de errores CRC V3.00" . Archivado del original el 27-09-2006 . Recuperado el 16-02-2016 .
↑ Sarwate, Dilip V. (agosto de 1998). "Cálculo de comprobaciones de redundancia cíclica mediante búsqueda en tabla" . Communications of the ACM . 31 (8): 1008– 1013. doi : 10.1145/63030.63037 . S2CID 5363350 .
1 2 "Especificación de Portable Network Graphics (PNG) (Segunda edición): Anexo D, Implementación de ejemplo de código de redundancia cíclica" . W3C . 10 de noviembre de 2003. Consultado el 16 de febrero de 2016 .
↑ " [ MS-ABS ] : Algoritmo CRC de 32 bits" . msdn.microsoft.com . Archivado del original el 7 de noviembre de 2017. Consultado el 4 de noviembre de 2017 .
↑ Kounavis, ME; Berry, FL (2005). "Un enfoque sistemático para la construcción de generadores CRC basados en software de alto rendimiento". 10.º Simposio IEEE sobre Computadoras y Comunicaciones (ISCC'05) (PDF) . págs. 855–862 . doi : 10.1109/ISCC.2005.18 . ISBN 0-7695-2373-0. S2CID 10308354 .
↑ Berry, Frank L.; Kounavis, Michael E. (noviembre de 2008). "Nuevos algoritmos basados en búsqueda en tablas para la generación de CRC de alto rendimiento". IEEE Transactions on Computers . 57 (11): 1550– 1560. Bibcode : 2008ITCmp..57.1550K . doi : 10.1109/TC.2008.85 . S2CID 206624854 .
↑ Generación de CRC de alto rendimiento con el algoritmo Intel Slicing-by-8 (PDF) (Informe técnico). Intel . Archivado del original (PDF) el 22 de julio de 2012.
↑ "Breve tutorial sobre el cálculo de CRC" . Archivos del kernel de Linux .
↑ Menon-Sen, Abhijit (2017-01-20). "¿Quién inventó el algoritmo CRC32 de segmentación por N?" .
↑ Jon Buller (15 de marzo de 1996). "Re: 8051 y CRC-CCITT" . Grupo de noticias : comp.arch.embedded . Usenet: 31498ED0.7C0A@nortel.com . Consultado el 16 de febrero de 2016 .
↑ Proyecto AVR-LibC (15 de marzo de 2024). "AVR-LibC <util/crc16.h>" .
↑ Glaise, René J. (1997-01-20). "Un cálculo en dos pasos del código de redundancia cíclica CRC-32 para redes ATM" . IBM Journal of Research and Development . 41 (6). Armonk, NY : IBM : 705. doi : 10.1147/rd.416.0705 . Archivado del original el 30-01-2009 . Recuperado el 16-02-2016 .
↑ Pei, Tong-Bi; Zukowsk, Charles (abril de 1992). "Circuitos CRC paralelos de alta velocidad en VLSI". IEEE Transactions on Communications . 40 (4): 653– 657. Bibcode : 1992ITCom..40..653P . doi : 10.1109/26.141415 . Si bien se puede lograr una aceleración significativa utilizando computación paralela, la simple multiplicación por $k$ no se logra del todo cuando $k$ $> 2.$ De hecho, $⁠$ $k$ $/$ $2$ $⁠$ (o más precisamente $[0.4$ $k$ $, 0.6$ $k$ $l$ ) parece ser un modelo razonable en una amplia gama de situaciones. Con $k$ $= 8$ , estimamos que el polinomio prototipo logró una aceleración de aproximadamente 4.9.
↑ Derby, Jeff H. (25–29 de noviembre de 2001). Cálculo de CRC de alta velocidad mediante transformaciones de espacio de estados . Conferencia Global de Telecomunicaciones. San Antonio, TX, EE. UU. pp. 166–170 . doi : 10.1109/GLOCOM.2001.965100 .
1 2 Kennedy, Christopher; Reyhani-Masoleh, Arash (7 de junio de 2009). Cálculos CRC de alta velocidad utilizando transformaciones de espacio de estados mejoradas . Conferencia Internacional IEEE sobre Electro/Tecnología de la Información. doi : 10.1109/EIT.2009.5189575 .
↑ Das, Arindam (abril de 2023). "Cálculo por bloques del código de redundancia cíclica utilizando matrices de Toeplitz factorizadas en lugar de una tabla de búsqueda". IEEE Transactions on Computers . 72 (4): 1110– 1121. Bibcode : 2023ITCmp..72.1110D . doi : 10.1109/TC.2022.3189574 . ISSN 0018-9340 . S2CID 250472783 .
↑ Kadatch, Andrew; Jenkins, Bob (3 de septiembre de 2010). Todo lo que sabemos sobre CRC pero tememos olvidar (PDF) (Informe técnico). pág. 4. El hecho de que el CRC de un mensaje seguido de su CRC sea un valor constante que no depende del mensaje... es bien conocido y se ha utilizado ampliamente en la industria de las telecomunicaciones durante mucho tiempo. Una buena fuente para obtener aún más información.
↑ Por ejemplo, hoja de datos del RFID de baja frecuencia 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ág. 39 , consultado 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: división larga XOR a búsqueda en tabla byte a byte" .

Andrew Kadarch, Bob Jenkins. "Implementación eficiente de CRC (~1 ciclo de CPU por byte)" . GitHub .

[1] Dubrova, Elena; Mansouri, Shohreh Sharif (mayo de 2012). "Un enfoque basado en BDD para la construcción de LFSRS para codificación CRC paralela" . 2012 IEEE 42nd International Symposium on Multiple-Valued Logic . pp. 128–133 . doi : 10.1109/ISMVL.2012.20 . ISBN 978-0-7695-4673-5. S2CID 27306826 .

[williams96-2] 1 2 Williams, Ross N. (1996-09-24). "Una guía sencilla para los algoritmos de detección de errores CRC V3.00" . Archivado del original el 27-09-2006 . Recuperado el 16-02-2016 .

[3] Sarwate, Dilip V. (agosto de 1998). "Cálculo de comprobaciones de redundancia cíclica mediante búsqueda en tabla" . Communications of the ACM . 31 (8): 1008– 1013. doi : 10.1145/63030.63037 . S2CID 5363350 .

[PNGspec-4] 1 2 "Especificación de Portable Network Graphics (PNG) (Segunda edición): Anexo D, Implementación de ejemplo de código de redundancia cíclica" . W3C . 10 de noviembre de 2003. Consultado el 16 de febrero de 2016 .

[5] " [ MS-ABS ] : Algoritmo CRC de 32 bits" . msdn.microsoft.com . Archivado del original el 7 de noviembre de 2017. Consultado el 4 de noviembre de 2017 .

[6] Kounavis, ME; Berry, FL (2005). "Un enfoque sistemático para la construcción de generadores CRC basados en software de alto rendimiento". 10.º Simposio IEEE sobre Computadoras y Comunicaciones (ISCC'05) (PDF) . págs. 855–862 . doi : 10.1109/ISCC.2005.18 . ISBN 0-7695-2373-0. S2CID 10308354 .

[7] Berry, Frank L.; Kounavis, Michael E. (noviembre de 2008). "Nuevos algoritmos basados en búsqueda en tablas para la generación de CRC de alto rendimiento". IEEE Transactions on Computers . 57 (11): 1550– 1560. Bibcode : 2008ITCmp..57.1550K . doi : 10.1109/TC.2008.85 . S2CID 206624854 .

[8] Generación de CRC de alto rendimiento con el algoritmo Intel Slicing-by-8 (PDF) (Informe técnico). Intel . Archivado del original (PDF) el 22 de julio de 2012.

[9] "Breve tutorial sobre el cálculo de CRC" . Archivos del kernel de Linux .

[10] Menon-Sen, Abhijit (2017-01-20). "¿Quién inventó el algoritmo CRC32 de segmentación por N?" .

[11] Jon Buller (15 de marzo de 1996). "Re: 8051 y CRC-CCITT" . Grupo de noticias : comp.arch.embedded . Usenet: 31498ED0.7C0A@nortel.com . Consultado el 16 de febrero de 2016 .

[12] Proyecto AVR-LibC (15 de marzo de 2024). "AVR-LibC <util/crc16.h>" .

[glaise-13] Glaise, René J. (1997-01-20). "Un cálculo en dos pasos del código de redundancia cíclica CRC-32 para redes ATM" . IBM Journal of Research and Development . 41 (6). Armonk, NY : IBM : 705. doi : 10.1147/rd.416.0705 . Archivado del original el 30-01-2009 . Recuperado el 16-02-2016 .

[14] Pei, Tong-Bi; Zukowsk, Charles (abril de 1992). "Circuitos CRC paralelos de alta velocidad en VLSI". IEEE Transactions on Communications . 40 (4): 653– 657. Bibcode : 1992ITCom..40..653P . doi : 10.1109/26.141415 . Si bien se puede lograr una aceleración significativa utilizando computación paralela, la simple multiplicación por $k$ no se logra del todo cuando $k$ $> 2.$ De hecho, $⁠$ $k$ $/$ $2$ $⁠$ (o más precisamente $[0.4$ $k$ $, 0.6$ $k$ $l$ ) parece ser un modelo razonable en una amplia gama de situaciones. Con $k$ $= 8$ , estimamos que el polinomio prototipo logró una aceleración de aproximadamente 4.9.

[15] Derby, Jeff H. (25–29 de noviembre de 2001). Cálculo de CRC de alta velocidad mediante transformaciones de espacio de estados . Conferencia Global de Telecomunicaciones. San Antonio, TX, EE. UU. pp. 166–170 . doi : 10.1109/GLOCOM.2001.965100 .

[Kennedy2009-16] 1 2 Kennedy, Christopher; Reyhani-Masoleh, Arash (7 de junio de 2009). Cálculos CRC de alta velocidad utilizando transformaciones de espacio de estados mejoradas . Conferencia Internacional IEEE sobre Electro/Tecnología de la Información. doi : 10.1109/EIT.2009.5189575 .

[17] Das, Arindam (abril de 2023). "Cálculo por bloques del código de redundancia cíclica utilizando matrices de Toeplitz factorizadas en lugar de una tabla de búsqueda". IEEE Transactions on Computers . 72 (4): 1110– 1121. Bibcode : 2023ITCmp..72.1110D . doi : 10.1109/TC.2022.3189574 . ISSN 0018-9340 . S2CID 250472783 .

[Kadatch2010-18] Kadatch, Andrew; Jenkins, Bob (3 de septiembre de 2010). Todo lo que sabemos sobre CRC pero tememos olvidar (PDF) (Informe técnico). pág. 4. El hecho de que el CRC de un mensaje seguido de su CRC sea un valor constante que no depende del mensaje... es bien conocido y se ha utilizado ampliamente en la industria de las telecomunicaciones durante mucho tiempo. Una buena fuente para obtener aún más información.

[19] Por ejemplo, hoja de datos del RFID de baja frecuencia 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ág. 39 , consultado el 16 de febrero de 2016. El generador CRC se inicializa con el valor 0x3791 como se muestra en la figura 50.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]