El cálculo de una comprobación de redundancia cíclica se deriva de las matemáticas de la división polinómica, módulo dos . En la práctica, se parece 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 o exclusivas reemplazan las restas. 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 ofuscado [2] ) a través del paralelismo byte a byte y las compensaciones espacio-temporales .
Varios estándares CRC extienden el algoritmo de división polinómica especificando un valor de registro de desplazamiento inicial, un paso final de OR exclusivo y, lo más importante, un orden de bits ( endianness ). Como resultado, el código que se ve 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.
Como ejemplo de implementación de la división polinómica en hardware, supongamos 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 . Para la ilustración, utilizaremos el polinomio CRC-8-ATM ( HEC ) . Escribiendo el primer bit transmitido (el coeficiente de la potencia más alta de ) a la izquierda, esto corresponde a la cadena de 9 bits "100000111".
El valor del byte 57 16 se puede transmitir en dos órdenes diferentes, según 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, esto es = 11101010. Estos se pueden multiplicar por para producir dos polinomios de mensaje de 16 bits .
El cálculo del resto consiste entonces en restar múltiplos del polinomio generador . Esto es como una división decimal larga, 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 hay necesidad de registrarlo.
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 con respecto al original; y un grupo sombreado en azul en el medio que es "interesante". El grupo "interesante" tiene una longitud de 8 bits, que coincide con el grado del polinomio. En cada paso, se resta el múltiplo apropiado del polinomio para hacer que el grupo cero sea un bit más largo, y el grupo sin cambios se vuelve un bit más corto, hasta que solo queda el resto final.
En el ejemplo de msbit-first, el polinomio restante es . Al convertirlo a un número hexadecimal utilizando la convención de que la potencia más alta de x es el msbit, este es A2 16 . En el ejemplo de lsbit-first, el resto es . Al convertirlo a hexadecimal utilizando la convención de que la potencia más alta de x es el lsbit, este es 19 16 .
Escribir el mensaje completo en cada paso, como se hace en el ejemplo anterior, es muy tedioso. Las implementaciones eficientes utilizan un registro de desplazamiento de 1 bit para almacenar solo los bits interesantes. Multiplicar el polinomio por es equivalente a desplazar el registro una posición, ya que los coeficientes no cambian de valor, sino que solo se mueven hasta el siguiente término del polinomio.
Aquí se presenta un primer borrador de un pseudocódigo para calcular un CRC de n bits. Utiliza un tipo de datos compuesto artificial para polinomios, donde xno es una variable entera, sino un constructor que genera un objeto Polinomio que se puede sumar, multiplicar y exponenciar. Sumar dos polinomios es sumarlos, módulo dos; es decir, aplicar OR exclusivo a 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]) // Primeros n bits del mensaje // Una variante popular complementa remainderPolynomial aquí; consulte § Preestablecido en −1 a continuación para i desde 1 hasta len { restoPolinomial := restoPolinomial * x + bitString[i+n] * x 0 // Definir bitString[k]=0 para k>len si el coeficiente de x n de restoPolinomial = 1 { restoPolinomio := restoPolinomio generador xorPolinomio } } // Una variante popular complementa a remainderPolynomial aquí; consulte § Post-inversión a continuación para devolver remainderPolynomial}Tenga en cuenta que este código de ejemplo evita la necesidad de especificar una convención de ordenamiento de bits al no utilizar bytes; la entrada bitStringya está en forma de una matriz de bits, y remainderPolynomialse manipula en términos de operaciones polinomiales; la multiplicación por podría ser un desplazamiento hacia la izquierda o hacia la derecha, y la suma de se realiza al coeficiente, que podría ser el extremo derecho o izquierdo del registro.bitString[i+n]
Este código tiene dos desventajas. En primer lugar, requiere un registro de n +1 bits para almacenar el remainderPolynomialde modo que se pueda probar el coeficiente. Más importante aún, requiere que el se rellene con n bits cero.bitString
El primer problema se puede resolver probando el coeficiente de antes de multiplicarlo por .remainderPolynomial
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 combinen las distintas entradas en el . Y, específicamente, no es necesario agregar remainderPolynomialun bit dado del hasta el último instante cuando se prueba para determinar si es compatible con el .bitStringremainderPolynomialxorgeneratorPolynomial
Esto también elimina la necesidad de precargar los remainderPolynomialprimeros n bits del mensaje:
función crc( matriz de bits bitString[1..len], int len) { restoPolinomio := 0 // Una variante popular complementa a remainderPolynomial aquí; consulte § Preestablecido en −1 a continuación para i desde 1 hasta len { restoPolinomial := restoPolinomial xor (bitstring[i] * x n−1 ) si (coeficiente de x n−1 de restoPolinomial) = 1 { restoPolinomio := (restoPolinomio * x ) xor generadorPolinomio } demás { restoPolinomio := (restoPolinomio * x ) } } // Una variante popular complementa a remainderPolynomial aquí; consulte § Post-inversión a continuación para devolver remainderPolynomial}Esta es la implementación estándar de CRC de hardware bit a bit, y vale la pena estudiarla; una vez que comprenda 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 los coeficientes de it y of simplemente se descartan. Esta es la razón por la que generalmente verá polinomios CRC escritos en binario con el coeficiente principal omitido.generatorPolynomial
En el software, es conveniente tener en cuenta que, si bien se puede retrasar la ejecución xorde cada bit hasta el último momento, también es posible hacerlo antes. Por lo general, es conveniente ejecutar la ejecución de xorun byte a la vez, incluso en una implementación de bit a bit. Aquí, tomamos la entrada en bytes de 8 bits:
función crc( matriz de bytes cadena[1..len], int len) { restoPolinomio := 0 // Una variante popular complementa a remainderPolynomial aquí; consulte § Preestablecido en −1 a continuación para i desde 1 hasta len { remainderPolynomial := remainderPolynomial xor polynomialForm (string[i]) * x n−8 para j de 1 a 8 { // Suponiendo 8 bits por byte si el coeficiente de x n−1 de remainderPolynomial = 1 { restoPolinomio := (restoPolinomio * x ) xor generadorPolinomio } demás { restoPolinomio := (restoPolinomio * x ) } } } // Una variante popular complementa a remainderPolynomial aquí; consulte § Post-inversión a continuación para devolver remainderPolynomial}Esta suele ser la implementación de software más compacta, utilizada en microcontroladores cuando el espacio es más importante que la velocidad.
Cuando se implementa en hardware serial de bits , el polinomio generador describe de forma única la asignación de bits; el primer bit transmitido es siempre el coeficiente de la potencia más alta de , y los últimos 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 utiliza transmisión paralela , enmarcado 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 (endianness) 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 una comunicación en serie , es mejor utilizar el orden de bits en el que se enviarán finalmente 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 reorganización de los bits.
Por ejemplo, tanto el estándar IEEE 802 ( Ethernet ) como el RS-232 ( puerto serial ) especifican la transmisión con el bit menos significativo primero (little-endian), por lo que una implementación de CRC de software para proteger los datos enviados a través de dicho enlace debe asignar los bits menos significativos en cada byte a coeficientes de las potencias más altas 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 primer bit es un poco más sencillo de implementar en software, por lo que se ve con más frecuencia, pero muchos programadores encuentran que el orden de bits de primer bit es más fácil de seguir. Así, por ejemplo, la extensión XMODEM -CRC, un uso temprano de los CRC en software, utiliza un CRC de primer bit.
Hasta ahora, el pseudocódigo ha evitado especificar el orden de los bits dentro de los bytes describiendo los cambios en el pseudocódigo como multiplicaciones por y escribiendo conversiones explícitas de la forma binaria a la polinómica. En la práctica, el CRC se guarda en un registro binario estándar utilizando una convención de ordenación de bits particular. En la forma msbit-first, los bits binarios más significativos se enviarán primero y, por lo tanto, contienen los coeficientes polinómicos 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 ser más concreto, 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 { // Probar el coeficiente x 15 rem := (rem leftShift 1) xor 0x1021 } demás { rem := rem Shift izquierda 1 } rem := rem y 0xffff // Recorta el resto a 16 bits } } // Una variante popular complementa a rem aquí: return rem}// El bit menos significativo primero (little-endian) // 1+x 5 +x 12 +(x 16 ) = 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 string[i] para j de 1 a 8 { // Suponiendo 8 bits por byte si rem y 0x0001 { // Probar el coeficiente x 15 rem := (rem rightShift 1) xor 0x8408 } demás { rem := rem Shift derecha 1 } } } // Una variante popular complementa a rem aquí: return rem}Tenga en cuenta que la forma lsbit-first evita la necesidad de realizar un desplazamiento 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 ordenamiento de bits elegida.
Otra optimización común utiliza una tabla de búsqueda indexada por los coeficientes de orden más alto de rempara procesar más de un bit de dividendo por iteración. [3] Lo más común es utilizar una tabla de búsqueda de 256 entradas, reemplazando el cuerpo del bucle externo (sobre i) con:
// Msbit primerorem = (rem leftShift 8) xor big_endian_table[string[i] xor ((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)]
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 el formato de imagen PNG . Su polinomio se puede escribir msbit-first como 0x04C11DB7, o lsbit-first como 0xEDB88320. La página web del W3C sobre PNG incluye un apéndice con una implementación simple y breve basada en tablas en C de CRC-32. [4] Notarás que el código corresponde al pseudocódigo lsbit-first byte-at-a-time presentado aquí, y la tabla se genera utilizando el código bit-at-a-time.
Generalmente, lo más conveniente es utilizar una tabla de 256 entradas, pero se pueden utilizar otros tamaños. En microcontroladores pequeños, el uso de una tabla de 16 entradas para procesar cuatro bits a la vez proporciona una mejora útil en la velocidad y, al mismo tiempo, mantiene la tabla pequeña. En computadoras con amplio almacenamiento, unaLa tabla de 65 536 entradas se puede utilizar para procesar 16 bits a la vez.
El software para generar las tablas es tan pequeño y rápido que suele ser más rápido calcularlas al iniciar el programa que cargar tablas precalculadas desde el almacenamiento. Una técnica popular es utilizar el código bit a bit 256 veces para generar los CRC de los 256 bytes de 8 bits posibles. Sin embargo, esto se puede optimizar significativamente aprovechando la propiedad de que . Solo es necesario calcular directamente las entradas de la tabla correspondientes a potencias de dos.table[i xor j] == table[i] xor table[j]
En el siguiente código de ejemplo, crccontiene el valor de table[i]:
tabla_big_endian[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 Shift izquierda 1 } // crc es el valor de big_endian_table[i] ; deje que j itere sobre las entradas ya inicializadas para j desde 0 hasta i−1 { tabla_big_endian[i + j] := crc xor tabla_big_endian[j]; } i := i desplazamiento a la izquierda 1} mientras yo < 256tabla_little_endian[0] := 0crc := 1;yo := 128hacer { si crc y 1 { crc := (crc rightShift 1) xor 0x8408 // El polinomio CRC } else { crc := crc Shift derecha 1 } // crc es el valor de little_endian_table[i] ; deje que j itere sobre las entradas ya inicializadas para j desde 0 hasta 255 por 2 × i { tabla_little_endian[i + j] := crc xor tabla_little_endian[j]; } i := i desplazamiento a la derecha 1} mientras i > 0En 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
Este es un algoritmo práctico para la variante CRC-32 de CRC. [5] La CRCTable es una memorización de un cálculo que debería repetirse para cada byte del mensaje (Cálculo de comprobaciones de redundancia cíclica § Cálculo de múltiples bits).
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 los datos nLookupIndex ← (byte crc32 xor) 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 bitscrc32 ← crc32 xor 0xFFFFFFFFdevolver crc32
En C, el algoritmo se ve así:
#include <inttypes.h> // uint32_t, uint8_t uint32_t CRC32 ( const uint8_t datos [], tamaño_t longitud_datos ) { uint32_t crc32 = 0xFFFFFFFFu ; para ( tamaño_t i = 0 ; i < longitud_datos ; i ++ ) { const uint32_t índice_búsqueda = ( crc32 ^ datos [ i ]) & 0xff ; crc32 = ( crc32 >> 8 ) ^ CRCTable [ índice_búsqueda ]; // CRCTable es una matriz de 256 constantes de 32 bits } // Finaliza el valor CRC-32 invirtiendo todos los bits crc32 ^= 0xFFFFFFFFu ; devolver crc32 ; } Existe un algoritmo slice-by -n (normalmente slice-by-8 para CRC32) que normalmente duplica o triplica el rendimiento en comparación con el algoritmo Sarwate. En lugar de leer 8 bits a la vez, el algoritmo lee 8 n bits a la vez. De esta manera se maximiza el rendimiento en procesadores superescalares . [6] [7] [8] [9]
No está claro quién inventó realmente el algoritmo. [10]
Para entender las ventajas, comencemos con el caso de corte por 2. Deseamos calcular un CRC de 2 bytes (16 bits) a la vez, pero el enfoque estándar basado en tablas requeriría una tabla de 65536 entradas, que es demasiado grande. Como se mencionó en § Generación de las tablas, 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]
Por lo tanto, la tabla grande no se almacena explícitamente, sino que cada iteración calcula el valor CRC que estaría allí combinando los valores en 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é hacer dos búsquedas en tablas separadas, cuando el algoritmo estándar byte a la vez haría dos búsquedas en la misma tabla?
La diferencia es el paralelismo a nivel de instrucción . En el algoritmo estándar, el índice de cada búsqueda depende del valor obtenido en la búsqueda anterior. Por lo tanto, la segunda búsqueda no puede comenzar hasta que se complete la primera.
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 realizar un seguimiento de más de 100 cargas en curso), esto tiene el potencial de duplicar la velocidad del bucle interno.
Obviamente, esta técnica se puede extender a tantos segmentos como el procesador pueda aprovechar.
Cuando el ancho de corte es igual al tamaño del CRC, se produce una pequeña aceleración. En la parte del algoritmo básico de Sarwate en la que el valor CRC anterior se desplaza por el tamaño de la consulta de la tabla, el valor CRC anterior se desplaza por completo (lo que queda es todo cero), por lo que el XOR se puede eliminar de la ruta crítica.
El bucle interno resultante de n segmentos consta de:
Esto todavía tiene la propiedad de que todas las cargas en el segundo paso deben completarse antes de que pueda comenzar la siguiente iteración, lo que da como resultado 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 corte excede el tamaño del CRC, aparece una segunda aceleración significativa.
Esto se debe a que una parte de los resultados del primer paso ya no dependen de ninguna iteración anterior. Al realizar una operación XOR de un CRC de 32 bits con 64 bits de mensaje, la mitad del resultado es simplemente una copia del mensaje. Si se codifica 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 se complete la iteración del bucle anterior. El resultado es suficiente trabajo para mantener ocupado continuamente al subsistema de memoria del procesador , lo que logra el máximo rendimiento. Como se mencionó, en los microprocesadores posteriores al año 2000, realizar una operación de corte por 8 es generalmente suficiente para alcanzar este nivel.
No hay una necesidad particular de que las porciones tengan 8 bits de ancho. Por ejemplo, sería perfectamente posible calcular un CRC de 64 bits a la vez utilizando un algoritmo de porciones por 9, utilizando 9 tablas de búsqueda de 128 entradas para manejar 63 bits, y el bit 64º manejado por el algoritmo de bit a la vez (que es efectivamente una tabla de búsqueda de 1 bit y 2 entradas). Esto reduciría casi a la mitad el tamaño de la tabla (pasando de 8×256 = 2048 entradas a 9×128 = 1152) a expensas de una carga más dependiente de los datos por iteración.
La actualización paralela de un byte o una palabra a la vez también se puede realizar explícitamente, sin una tabla. [11] 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 desplazado 8 bits. Las siguientes tablas enumeran las ecuaciones para algunos polinomios de uso común, utilizando los siguientes símbolos:
Como el polinomio CRC-32 tiene una gran cantidad de términos, al calcular el resto byte a byte, cada bit depende de hasta 8 bits de la iteración anterior. En implementaciones de hardware de bytes en paralelo, esto requiere puertas XOR de 8 entradas o en cascada, lo que aumenta el retardo de propagación .
Para maximizar la velocidad de cálculo, se puede calcular un resto intermedio calculando primero el CRC del mensaje módulo x 123 + x 111 + x 92 + x 84 + x 64 + x 46 + x 23 + 1. Este es un múltiplo cuidadosamente seleccionado del polinomio CRC-32 de modo que los términos (tomas de retroalimentación) estén separados por al menos 8 posiciones. De este modo, un registro de desplazamiento de 123 bits se 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 para obtener el resto CRC-32. [12]
Si se permiten puertas XOR de 3 o 4 entradas, se pueden utilizar polinomios intermedios más cortos de grado 71 o 53, respectivamente.
El cálculo del resto por bloques 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. [13]
Al agregar un CRC a un mensaje, es posible separar el CRC transmitido, volver a calcularlo y comparar el valor recalculado con el transmitido. 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 ordenamiento de bits elegida), un receptor puede calcular un CRC general, sobre el mensaje y el CRC, y si son correctos, el resultado será cero. [14] 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 de 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 llamada encuadre basado en CRC . (Esto requiere múltiples cuadros para detectar la adquisición o pérdida de encuadre, por lo que está limitado a aplicaciones donde los cuadros tienen una longitud conocida y el contenido del cuadro es lo suficientemente aleatorio como para que los CRC válidos en datos desalineados sean poco frecuentes).
En la práctica, la mayoría de los estándares especifican que se debe preestablecer el registro en todos los bits 1 e invertir el CRC antes de la transmisión. Esto no afecta la capacidad del CRC para detectar bits modificados, pero le otorga la capacidad de notar los bits que se agregan al mensaje.
Las matemáticas básicas de un CRC aceptan (consideran como transmitidos correctamente) mensajes que, cuando se interpretan como un polinomio, son un múltiplo del polinomio CRC. Si se anteponen algunos bits 0 iniciales a dicho mensaje, no cambiarán su interpretación como polinomio. Esto es equivalente al hecho de que 0001 y 1 son el mismo número.
Pero si el mensaje que se transmite sí se preocupa por los bits 0 iniciales, la incapacidad del algoritmo CRC básico para detectar dicho cambio es indeseable. Si es posible que un error de transmisión pueda agregar dichos bits, una solución simple es comenzar con el remregistro de desplazamiento configurado en algún valor distinto de cero; por conveniencia, se usa típicamente el valor de todos unos. Esto es matemáticamente equivalente a complementar (NO binario) los primeros n bits del mensaje, donde n es el número de bits en el registro CRC.
Esto no afecta de ninguna manera 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 servirá, y algunas normas especifican valores inusuales, [15] pero el valor de todos unos (−1 en el binario de complemento a dos) es, con diferencia, el más común. Tenga en cuenta 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.
El mismo tipo de error puede ocurrir al final de un mensaje, aunque con un conjunto más limitado de mensajes. Añadir 0 bits a un mensaje equivale a multiplicar su polinomio por x y, si antes era un múltiplo del polinomio CRC, el resultado de esa multiplicación también lo será. Esto equivale al hecho de que, como 726 es 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 añadirlo al mensaje. Nuevamente, cualquier cambio distinto de cero servirá; invertir todos los bits (XOR con un patrón de todos unos) es simplemente la opción más común.
Esto tiene un efecto en 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 post-inversión, del patrón de inversión). Una vez que se ha obtenido esta constante (por ejemplo, realizando una generación/comprobación CRC de una sola pasada en un mensaje arbitrario), se puede utilizar directamente para verificar la corrección de cualquier otro mensaje comprobado utilizando el mismo algoritmo CRC.
Categoría general
Sumas de comprobación sin CRC
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.
{{cite tech report}}: CS1 maint: year (link) Una buena fuente para obtener aún más informacióngenerador de CRC se inicializa con el valor 0x3791 como se muestra en la Figura 50.