La verificación de redundancia cíclica (CRC) se basa en la división en el anillo de polinomios sobre el campo finito GF (2) (los números enteros módulo 2 ), es decir, el conjunto de polinomios donde cada coeficiente es cero o uno, y operaciones aritméticas envolver alrededor.
Cualquier cadena de bits se puede interpretar como los coeficientes de un polinomio de mensaje de este tipo, y para encontrar el CRC, multiplicamos el polinomio de mensaje pory luego encuentre el resto al dividir por el grado - polinomio generador . Los coeficientes del polinomio restante son los bits del CRC.
Matemáticas
En general, el cálculo de CRC corresponde a la división euclidiana de polinomios sobre GF (2) :
Aquí es el polinomio del mensaje original y es el gradopolinomio generador. Los pedazos de son el mensaje original con ceros agregados al final. La 'suma de comprobación' de CRC está formada por los coeficientes del polinomio restante cuyo grado es estrictamente menor que . El polinomio del cocienteno es de interés. Utilizando la operación de módulo , se puede afirmar que
En la comunicación, el remitente adjunta el bits de R después de los bits del mensaje original de M, que podría demostrarse que es equivalente a enviar (la palabra clave .) El receptor, sabiendo y por lo tanto , separa M de R y repite el cálculo, verificando que la R recibida y la calculada sean iguales. Si es así, el receptor asume que los bits del mensaje recibido son correctos.
En la práctica, los cálculos de CRC se asemejan más a la división larga en binario, excepto que las sustracciones involucradas no toman prestados de dígitos más significativos y, por lo tanto, se convierten en operaciones exclusivas de u .
Un CRC es una suma de comprobación en un sentido matemático estricto, ya que puede expresarse como la suma ponderada módulo 2 de síndromes por bit , pero esa palabra generalmente se reserva más específicamente para sumas calculadas utilizando módulos más grandes, como 10, 256, o 65535.
Los CRC también se pueden utilizar como parte de códigos de corrección de errores , que permiten no solo la detección de errores de transmisión, sino también la reconstrucción del mensaje correcto. Estos códigos se basan en principios matemáticos estrechamente relacionados.
Aritmética polinomial módulo 2
Dado que los coeficientes están restringidos a un solo bit, cualquier operación matemática en polinomios CRC debe asignar los coeficientes del resultado a cero o uno. Por ejemplo, además:
Tenga en cuenta que es equivalente a cero en la ecuación anterior porque la suma de coeficientes se realiza módulo 2:
El módulo 2 de adición de polinomios es lo mismo que XOR bit a bit . Dado que XOR es el inverso de sí mismo, la resta polinominal módulo 2 también es igual que XOR bit a bit.
La multiplicación es similar (un producto sin acarreo ):
También podemos dividir polinomios mod 2 y encontrar el cociente y el resto. Por ejemplo, suponga que estamos dividiendo por . Encontraríamos que
En otras palabras,
La división produce un cociente de x 2 + 1 con un resto de -1, que, dado que es impar, tiene un último bit de 1.
En las ecuaciones anteriores, representa los bits del mensaje original 111
, es el polinomio generador, y el resto (equivalentemente, ) es el CRC. El grado del polinomio generador es 1, por lo que primero multiplicamos el mensaje por Llegar .
Variaciones
Hay varias variaciones estándar en los CRC, cualquiera o todos los cuales se pueden utilizar con cualquier polinomio CRC. Las variaciones de implementación , como la presentación de endianness y CRC, solo afectan el mapeo de las cadenas de bits con los coeficientes de y y no afectan las propiedades del algoritmo.
- Para comprobar el CRC, en lugar de calcular el CRC en el mensaje y compararlo con el CRC, se puede ejecutar un cálculo de CRC en toda la palabra de código. Si el resultado (llamado residual) es cero, la verificación pasa. Esto funciona porque la palabra clave es, que siempre es divisible por .
- Esto simplifica muchas implementaciones al evitar la necesidad de tratar los últimos bytes del mensaje especialmente cuando se verifican los CRC.
- El registro de desplazamiento puede inicializarse con unos en lugar de ceros. Esto equivale a invertir la primerabits del mensaje antes de introducirlos en el algoritmo. La ecuación CRC se convierte en, dónde es la longitud del mensaje en bits. El cambio que esto impone a es una función del polinomio generador y la longitud del mensaje, .
- La razón por la que se utiliza este método es porque un CRC no modificado no distingue entre dos mensajes que difieren solo en el número de ceros a la izquierda, porque los ceros a la izquierda no afectan el valor de . Cuando se realiza esta inversión, el CRC distingue entre dichos mensajes.
- El CRC puede invertirse antes de agregarse al flujo de mensajes. Mientras que un CRC sin modificar distingue entre mensajescon diferentes números de ceros finales, no detecta ceros finales añadidos después del resto CRC. Esto se debe a que todas las palabras de código válidas son múltiplos de, entonces veces esa palabra en clave también es un múltiplo. (De hecho, esta es precisamente la razón por la que funciona la primera variante descrita anteriormente).
En la práctica, las dos últimas variaciones se utilizan invariablemente juntas. Cambian el CRC transmitido, por lo que deben implementarse tanto en el transmisor como en el receptor. Si bien el preajuste del registro de desplazamiento a unos es sencillo en ambos extremos, la inversión afecta a los receptores que implementan la primera variación, porque el CRC de una palabra de código completa que ya incluye un CRC ya no es cero. En cambio, es un patrón fijo distinto de cero, el CRC del patrón de inversión de unos.
Por tanto, el CRC puede comprobarse mediante el método obvio de calcular el CRC en el mensaje, invertirlo y compararlo con el CRC en el flujo de mensajes, o calculando el CRC en toda la palabra de código y comparándolo con un valor fijo esperado. , llamado polinomio de verificación, residuo o número mágico . Esto puede calcularse como, o de forma equivalente, calculando el CRC sin modificar de un mensaje que consta de unos, .
Estas inversiones son extremadamente comunes pero no se realizan universalmente, incluso en el caso de los polinomios CRC-32 o CRC-16-CCITT.
Representaciones invertidas y polinomios recíprocos
Representaciones polinomiales
Ejemplo de polinomio CCITT de 16 bits en las formas descritas (los bits dentro de los corchetes se incluyen en la representación de la palabra; los bits fuera son 1 bits implícitos; las barras verticales designan los límites del nibble ):
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 coeficiente 1 [0 0 0 1 | 0 0 0 0 | 0 0 1 0 | 0 0 0 1] Normal [1 | 0 | 2 | 1] Mordiscos de Normal 0x1021 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16[1 0 0 0 | 0 1 0 0 | 0 0 0 0 | 1 0 0 0] 1 Inversa [8 | 4 | 0 | 8] Mordiscos de Reverse 0x840816 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 1 [0 0 0 0 | 1 0 0 0 | 0 0 0 1 | 0 0 0 1] Recíproco [0 | 8 | 1 | 1] Mordiscos de recíproco 0x0811 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Recíproco inverso16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Koopman[1 0 0 0 | 1 0 0 0 | 0 0 0 1 | 0 0 0 0] 1 [8 | 8 | 1 | 0] Nibbles 0x8810
Todos los polinomios generadores de CRC conocidos de grado tienen dos representaciones hexadecimales comunes. En ambos casos, el coeficiente de se omite y se entiende que es 1.
- La representación de msbit-first es un número hexadecimal con bits, el bit menos significativo de los cuales es siempre 1. El bit más significativo representa el coeficiente de y el bit menos significativo representa el coeficiente de .
- La primera representación lsbit es un número hexadecimal con bits, el bit más significativo de los cuales es siempre 1. El bit más significativo representa el coeficiente de y el bit menos significativo representa el coeficiente de .
La forma msbit-first a menudo se denomina en la bibliografía como representación normal , mientras que lsbit-first se denomina representación inversa . Es fundamental utilizar el formulario correcto al implementar un CRC. Si el coeficiente de resulta ser cero, las formas se pueden distinguir de un vistazo al ver qué extremo tiene el bit configurado.
Para confundir aún más el asunto, el artículo de P. Koopman y T. Chakravarty [1] [2] convierte los polinomios del generador de CRC en números hexadecimales de otra manera: msbit-first, pero incluyendo el coeficiente y omitiendo el coeficiente. Esta representación de "Koopman" tiene la ventaja de que el grado se puede determinar a partir de la forma hexadecimal y los coeficientes son fáciles de leer en orden de izquierda a derecha. Sin embargo, no se usa en ningún otro lugar y no se recomienda debido al riesgo de confusión.
Polinomios recíprocos
Un polinomio recíproco se crea asignando el mediante coeficientes de un polinomio al mediante coeficientes de un nuevo polinomio. Es decir, el recíproco del grado polinomio es .
La propiedad más interesante de los polinomios recíprocos, cuando se utilizan en CRC, es que tienen exactamente la misma fuerza de detección de errores que los polinomios de los que son recíprocos. El recíproco de un polinomio genera las mismas palabras de código , solo un bit invertido, es decir, si todas menos la primera Los bits de una palabra de código bajo el polinomio original se toman, se invierten y se usan como un nuevo mensaje, el CRC de ese mensaje bajo el polinomio recíproco es igual al reverso del primero bits de la palabra de código original. Pero el polinomio recíproco no es el mismo que el polinomio original, y los CRC generados con él no son los mismos (incluso con inversión de módulo de bits) que los generados por el polinomio original.
Fuerza de detección de errores
La capacidad de detección de errores de un CRC depende del grado de su polinomio clave y del polinomio clave específico utilizado. El "polinomio de error"es la diferencia simétrica de la palabra de código del mensaje recibido y la palabra de código de mensaje correcta. Un error no será detectado por un algoritmo CRC si y solo si el polinomio de error es divisible por el polinomio CRC.
- Debido a que un CRC se basa en la división, ningún polinomio puede detectar errores que constan de una cadena de ceros antepuestos a los datos o de ceros iniciales faltantes. Sin embargo, consulte Variaciones .
- Todos los errores de un solo bit serán detectados por cualquier polinomio con al menos dos términos con coeficientes distintos de cero. El polinomio de error es, y es divisible solo por polinomios dónde .
- Se detectarán todos los errores de dos bits separados por una distancia menor que el orden del polinomio primitivo que es un factor del polinomio generador . El polinomio de error en el caso de dos bits es. Como se señaló anteriormente, el término no será divisible por el polinomio CRC, que deja el término. Por definición, el valor más pequeño de tal que un polinomio divide es el orden o exponente del polinomio . Los polinomios con el orden más grande se denominan polinomios primitivos , y para polinomios de grado con coeficientes binarios, tener orden .
- Todos los errores en un número impar de bits serán detectados por un polinomio que es un múltiplo de . Esto es equivalente a que el polinomio tenga un número par de términos con coeficientes distintos de cero. Esta capacidad supone que el polinomio generador es el producto de y un polinomio primitivo de grado ya que todos los polinomios primitivos excepto tener un número impar de coeficientes distintos de cero.
- Todos los errores de ráfaga de longitud será detectado por cualquier polinomio de grado o mayor que tiene un valor distinto de cero término.
(Aparte, nunca hay razón para usar un polinomio con cero término. Recuerde que un CRC es el resto de los tiempos del polinomio del mensaje.dividido por el polinomio CRC. Un polinomio con cero el término siempre tiene como factor. Así que si es el polinomio CRC original y , luego
Es decir, el CRC de cualquier mensaje con el polinomio es el mismo que el del mismo mensaje con el polinomio con un cero añadido. Es solo un desperdicio de un poco).
La combinación de estos factores significa que los buenos polinomios CRC son a menudo polinomios primitivos (que tienen la mejor detección de errores de 2 bits) o polinomios primitivos de grado. , multiplicado por (que detecta todos los números impares de errores de bits y tiene la mitad de la capacidad de detección de errores de dos bits de un polinomio primitivo de grado ). [1]
Bitfilters
La técnica de análisis que utiliza filtros de bits [1] permite determinar de manera muy eficiente las propiedades de un polinomio generador dado. Los resultados son los siguientes:
- Todos los errores de ráfaga (excepto uno) con una longitud no mayor que el polinomio generador pueden ser detectados por cualquier polinomio generador . Esto incluye errores de 1 bit (ráfaga de longitud 1). La longitud máxima es, Cuándo es el grado del polinomio generador (que a su vez tiene una longitud de ). La excepción a este resultado es un patrón de bits igual al del polinomio generador.
- Todos los errores de bits desiguales son detectados por polinomios generadores con un número par de términos.
- No se detectan errores de 2 bits en una distancia (múltiple) del filtro de bits más largo de paridad par a un polinomio generador; todos los demás son detectados. Para grados hasta 32 hay un polinomio generador óptimo con ese grado y número par de términos; en este caso, el período mencionado anteriormente es. Paraesto significa que los bloques de 32.767 bits de longitud no contienen errores de 2 bits no descubiertos. Para un número impar de términos en el polinomio generador, puede haber un período de; sin embargo, estos polinomios generadores (con un número impar de términos) no descubren todos los números impares de errores, por lo que deben evitarse. Se puede encontrar una lista de los generadores correspondientes con un número par de términos en el enlace mencionado al principio de esta sección.
- Todos los errores de un solo bit dentro del período de filtro de bits mencionado anteriormente (para términos pares en el polinomio generador) se pueden identificar de forma única por su residuo. Por lo tanto, el método CRC también se puede utilizar para corregir errores de un solo bit (dentro de esos límites, por ejemplo, 32,767 bits con polinomios generadores óptimos de grado 16). Dado que todos los errores impares dejan un residuo impar, se pueden distinguir todos los residuales pares, errores de 1 bit y errores de 2 bits. Sin embargo, al igual que otras técnicas SECDED , los CRC no siempre pueden distinguir entre errores de 1 bit y errores de 3 bits. Cuando ocurren 3 o más errores de bit en un bloque, la corrección de error de bit CRC será errónea en sí misma y producirá más errores.
Ver también
Referencias
- ↑ a b c Koopman, Philip (julio de 2002). Códigos de redundancia cíclica de 32 bits para aplicaciones de Internet (PDF) . La Conferencia Internacional sobre Redes y Sistemas Confiables . págs. 459–468. CiteSeerX 10.1.1.11.8323 . doi : 10.1109 / DSN.2002.1028931 . ISBN 978-0-7695-1597-7. Consultado el 14 de enero de 2011 . - verificación de los resultados de Castagnoli mediante una búsqueda exhaustiva y algunos nuevos buenos polinomios
- ^ Koopman, Philip; Chakravarty, Tridib (junio de 2004). Selección de polinomio del código de redundancia cíclica (CRC) para redes integradas (PDF) . La Conferencia Internacional sobre Redes y Sistemas Confiables . págs. 145-154. CiteSeerX 10.1.1.648.9080 . doi : 10.1109 / DSN.2004.1311885 . ISBN 978-0-7695-2052-0. Consultado el 14 de enero de 2011 . - análisis de polinomios CRC cortos para aplicaciones integradas
enlaces externos
- Koopman, Phil. "Blog: Checksum y CRC Central" .- enumera los polinomios CRC que ofrecen las mejores distancias de Hamming .