Matemáticas de las comprobaciones de redundancia cíclica

La comprobación de redundancia cíclica (CRC) verifica el resto de la división en el anillo de polinomios sobre GF(2) (el cuerpo finito de los enteros módulo 2). Es decir, el conjunto de polinomios donde cada coeficiente es cero o uno, y las operaciones aritméticas se repiten en círculo.

Cualquier cadena de bits puede interpretarse como los coeficientes de un polinomio de este tipo, y un mensaje tiene un CRC válido si es divisible por (es decir, es un múltiplo de) un polinomio generador acordado . Como ejemplo, el mensaje${\displaystyle 101100}$se considera como${\displaystyle x^{5}+x^{3}+x^{2}}$(que es divisible por${\displaystyle x^{2}}$(véase Aritmética polinomial módulo 2 más abajo para más detalles). Los CRC son convenientes y populares porque tienen buenas propiedades de detección de errores y un múltiplo de este tipo se puede construir fácilmente a partir de cualquier polinomio de mensaje.${\displaystyle M(x)}$al agregar un${\displaystyle n}$polinomio de resto de -bits${\displaystyle R(x)}$producir${\displaystyle W(x)=M(x)\cdot x^{n}+R(x)}$, dónde${\displaystyle n}$es el grado del polinomio generador.

Aunque la separación de${\displaystyle W(x)}$en la parte del mensaje${\displaystyle M(x)}$y la parte de la suma de comprobación${\displaystyle R(x)}$es conveniente para el uso de CRC, las propiedades de detección de errores no hacen distinción; los errores se detectan por igual en cualquier lugar dentro de${\displaystyle W(x)}$.

En general, el cálculo de CRC corresponde a la división euclidiana de polinomios sobre GF(2):

${\displaystyle M(x)\cdot x^{n}=Q(x)\cdot G(x)+R(x).}$

Aquí${\displaystyle M(x)}$es el mensaje original polinomial y${\displaystyle G(x)}$es el grado-${\displaystyle n}$polinomio generador. Los bits de${\displaystyle M(x)\cdot x^{n}}$son el mensaje original con${\displaystyle n}$ceros añadidos al final. La suma de verificación CRC se forma mediante los coeficientes del polinomio restante.${\displaystyle R(x)}$cuyo grado es estrictamente menor que${\displaystyle n}$por las propiedades de la división euclidiana. El polinomio cociente${\displaystyle Q(x)}$no tiene interés. Usando la operación módulo , se puede afirmar que

${\displaystyle R(x)=M(x)\cdot x^{n}\,{\bmod {\,}}G(x).}$

En la comunicación, el remitente adjunta el${\displaystyle n}$bits de R después de los bits del mensaje original de M, lo que equivale a enviar${\displaystyle W(x)=M(x)\cdot x^{n}+R(x)}$(la palabra clave ). Esta equivalencia se puede ver porque sabemos que${\displaystyle R(x)}$tiene un grado estrictamente menor que${\displaystyle n}$y el mensaje binario${\displaystyle M(x)\cdot x^{n}}$corresponde a es el mensaje original desplazado a la izquierda${\displaystyle n}$veces. Por lo tanto, se añade el${\displaystyle n}$bits de R (posiblemente con ceros iniciales) al mensaje simplemente sumando los polinomios. Escribiendo${\displaystyle W(x)}$De esta manera se demuestra que${\displaystyle W(x){\bmod {\,}}G(x)=0}$como

${\displaystyle M(x)\cdot x^{n}=Q(x)\cdot G(x)+R(x)}$

${\displaystyle \Rightarrow }$

${\displaystyle M(x)\cdot x^{n}-R(x)=Q(x)\cdot G(x)}$

${\displaystyle \Rightarrow }$porque en GF(2)${\displaystyle -1=1}$

${\displaystyle W(x)=M(x)\cdot x^{n}+R(x)=Q(x)\cdot G(x)}$

El receptor, sabiendo${\displaystyle G(x)}$, divide${\displaystyle W(x)}$por${\displaystyle G(x)}$y comprueba que el resto sea cero. Si lo es, el receptor lo descarta.${\displaystyle R(x)}$(el último${\displaystyle n}$bits) y asume los bits del mensaje recibido${\displaystyle M(x)}$son correctas.

Las implementaciones de software a veces separan el mensaje en sus partes y comparan el recibido.${\displaystyle R(x)}$a un valor reconstruido a partir del mensaje recibido, pero las implementaciones de hardware invariablemente encuentran que la división de longitud completa descrita anteriormente es más simple.

En la práctica, los cálculos CRC se asemejan mucho a la división larga en binario, excepto que las restas involucradas no toman prestados dígitos más significativos y, por lo tanto, se convierten en operaciones "o" exclusivas .

Un CRC es una suma de verificació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 pueden utilizarse 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 muy similares.

Dado que los coeficientes están restringidos a un solo bit, cualquier operación matemática sobre polinomios CRC debe asignar los coeficientes del resultado a cero o a uno. Por ejemplo, además:

${\displaystyle (x^{3}+x)+(x+1)=x^{3}+2x+1\equiv x^{3}+1{\pmod {2}}.}$

Tenga en cuenta que${\displaystyle 2x}$es equivalente a cero en la ecuación anterior porque la suma de coeficientes se realiza módulo 2:

${\displaystyle 2x=x+x=x\times (1+1)\equiv x\times 0=0{\pmod {2}}.}$

La suma de polinomios módulo 2 es lo mismo que la operación XOR a nivel de bits . Dado que XOR es la inversa de sí misma, la resta de polinomios módulo 2 también es lo mismo que la operación XOR a nivel de bits.

La multiplicación es similar (un producto sin acarreo ):

${\displaystyle (x^{2}+x)(x+1)=x^{3}+2x^{2}+x\equiv x^{3}+x{\pmod {2}}.}$

También podemos dividir polinomios módulo 2 y hallar el cociente y el resto. Por ejemplo, supongamos que estamos dividiendo${\displaystyle x^{3}+x^{2}+x}$por${\displaystyle x+1}$Descubriríamos que

${\displaystyle {\frac {x^{3}+x^{2}+x}{x+1}}=(x^{2}+1)-{\frac {1}{x+1}}.}$

En otras palabras,

${\displaystyle (x^{3}+x^{2}+x)=(x^{2}+1)(x+1)-1\equiv (x^{2}+1)(x+1)+1{\pmod {2}}.}$

La división produce un cociente de${\displaystyle x^{2}+1}$con un resto de −1, que, al ser impar, tiene un último bit de 1.

En las ecuaciones anteriores,${\displaystyle x^{3}+x^{2}+x}$representa los bits del mensaje original 111,${\displaystyle x+1}$es el polinomio generador y el resto${\displaystyle 1}$(equivalentemente,${\displaystyle x^{0}}$) es el CRC. El grado del polinomio generador es 1, por lo que primero multiplicamos el mensaje por${\displaystyle x^{1}}$Llegar${\displaystyle x^{3}+x^{2}+x}$.

Existen varias variaciones estándar de CRC, cualquiera de las cuales puede usarse con cualquier polinomio CRC. Las variaciones de implementación, como el orden de bytes y la presentación del CRC, solo afectan la asignación de cadenas de bits a los coeficientes de${\displaystyle M(x)}$y${\displaystyle R(x)}$y no afectan las propiedades del algoritmo.

• El resto de la división no tiene por qué ser cero. Aunque todo el texto anterior está escrito en términos de divisibilidad por el polinomio generador, cualquier resto fijo${\displaystyle S(x)}$puede utilizarse y tendrá el mismo rendimiento que un resto cero. Lo más común es el polinomio de todos unos.${\displaystyle (x^{n}+1)/(x+1)}$se utiliza, pero, por ejemplo, el campo de control de errores del encabezado del modo de transferencia asíncrono tiene un resto de${\displaystyle x^{6}+x^{4}+x^{2}+1.}$ La única complicación surge si el mismo hardware que genera el CRC al encontrar${\displaystyle R(x)=M(x)\cdot x^{n}{\bmod {G}}(x)+S(x)}$se utiliza para comprobar el CRC con una división de ancho completo de${\displaystyle W(x)\cdot x^{n}{\bmod {G}}(x).}$ Este último no producirá un resto de 0, ni de${\displaystyle S(x)}$, pero de${\displaystyle S(x)\cdot x^{n}{\bmod {G}}(x).}$ Esto no dificulta la comprobación CRC; simplemente hay que conocer el patrón esperado.
• La división larga puede comenzar con un resto distinto de cero. El resto generalmente se calcula utilizando una${\displaystyle n}$-registro de desplazamiento de bits que contiene el resto actual, mientras se suman los bits del mensaje y se realiza la reducción módulo${\displaystyle G(x)}$Se realiza la división normal inicializa el registro de desplazamiento a cero, pero también puede inicializarse a un valor distinto de cero. (De nuevo, lo más común es que todos los valores sean unos, pero se puede usar cualquier patrón). Esto es equivalente a sumar (XOR) el patrón de inicialización con el primero.${\displaystyle n}$fragmentos del mensaje antes de introducirlos en el algoritmo. La ecuación CRC se convierte en:${\displaystyle M(x)\cdot x^{n}+\sum _{i=m}^{m+n-1}x^{i}=Q(x)\cdot G(x)+R(x)}$, dónde${\displaystyle m>\deg(M(x))}$es la longitud del mensaje en bits. El cambio que esto impone en${\displaystyle R(x)}$es una función del polinomio generador y la longitud del mensaje,${\displaystyle \sum _{i=m}^{m+n-1}x^{i}\,{\bmod {\,}}G(x)}$.

Estas dos variaciones sirven para detectar bits cero añadidos al mensaje. Un bit cero precedente añade un coeficiente cero inicial a${\displaystyle W(x),}$que no cambia su valor y, por lo tanto, no cambia su divisibilidad por el polinomio generador. Al agregar un patrón fijo a los primeros bits de un mensaje, se pueden detectar esos bits cero adicionales.

Asimismo, el uso de un resto distinto de cero detecta los bits cero finales añadidos a un mensaje. Si un mensaje protegido por CRC${\displaystyle W(x)}$tiene un bit cero añadido, el polinomio recibido es${\displaystyle W(x)\cdot x.}$ Si el primero es divisible por el polinomio generador, también lo es el segundo. Usando un resto distinto de cero${\displaystyle S(x)}$, agregar un bit cero dará como resultado un resto diferente${\displaystyle S(x)\cdot x{\bmod {G}}(x)}$y, por lo tanto, se detectará el bit adicional.

En la práctica, estas dos variaciones se utilizan invariablemente juntas. Cambian el CRC transmitido, por lo que deben implementarse tanto en el transmisor como en el receptor. Ambos extremos deben preconfigurar sus circuitos de división a todos unos, el transmisor debe agregar el patrón de inversión final al resultado, y el receptor debe esperar este patrón al verificar el CRC. Si el receptor verifica el CRC mediante división de longitud completa, el resto porque el CRC de una palabra clave 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${\displaystyle n}$unos.

Estas inversiones son extremadamente comunes, pero no se realizan universalmente, incluso en el caso de los polinomios CRC-32 o CRC-16-CCITT. Casi siempre se incluyen al enviar mensajes de longitud variable, pero a menudo se omiten al comunicar mensajes de longitud fija, ya que es menos probable que surja el problema de los bits cero añadidos.

La capacidad de detección de errores de un CRC depende del grado de su polinomio generador y del polinomio generador específico utilizado. El "polinomio de error"${\displaystyle E(x)}$es la diferencia simétrica entre la palabra clave del mensaje recibido y la palabra clave del mensaje correcto. Un algoritmo CRC no detectará un error si y solo si el polinomio de error es divisible por el polinomio CRC.

• Dado que un CRC se basa en la división, ningún polinomio puede detectar errores que consistan en una cadena de ceros antepuestos a los datos, o en la falta de ceros iniciales. Sin embargo, consulte la sección  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${\displaystyle x^{k}}$, y${\displaystyle x^{k}}$es divisible solo por polinomios${\displaystyle x^{i}}$dónde${\displaystyle i\leq k}$.
• 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${\displaystyle E(x)=x^{i}+x^{k}=x^{k}\cdot (x^{i-k}+1),\;i>k}$. Como se indicó anteriormente, el${\displaystyle x^{k}}$El término no será divisible por el polinomio CRC, lo que deja el${\displaystyle x^{i-k}+1}$término. Por definición, el valor más pequeño de${\displaystyle {i-k}}$de tal manera que un polinomio divide${\displaystyle x^{i-k}+1}$es el orden o exponente del polinomio . Los polinomios de mayor orden se denominan polinomios primitivos , y para polinomios de grado${\displaystyle n}$con coeficientes binarios, tienen orden${\displaystyle 2^{n}-1}$.
• Todos los errores en un número impar de bits serán detectados por un polinomio que es un múltiplo de${\displaystyle x+1}$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${\displaystyle x+1}$y un polinomio primitivo de grado${\displaystyle n-i}$ya que todos los polinomios primitivos excepto${\displaystyle x+1}$tienen un número impar de coeficientes distintos de cero.
• Todos los errores de ráfaga de longitud${\displaystyle n}$será detectado por cualquier polinomio de grado${\displaystyle n}$o mayor que tenga un valor distinto de cero${\displaystyle x^{0}}$término.

(Como nota al margen, nunca hay razón para usar un polinomio con cero${\displaystyle x^{0}}$término. Recuerde que un CRC es el resto del polinomio del mensaje multiplicado por${\displaystyle x^{n}}$dividido por el polinomio CRC. Un polinomio con una raíz cuadrada.${\displaystyle x^{0}}$el término siempre tiene${\displaystyle x}$como factor. Entonces, si${\displaystyle K(x)}$es el polinomio CRC original y${\displaystyle K(x)=x\cdot K'(x)}$, entonces

${\displaystyle M(x)\cdot x^{n-1}=Q(x)\cdot K'(x)+R(x)}$

${\displaystyle M(x)\cdot x^{n}=Q(x)\cdot x\cdot K'(x)+x\cdot R(x)}$

${\displaystyle M(x)\cdot x^{n}=Q(x)\cdot K(x)+x\cdot R(x)}$

Es decir, el CRC de cualquier mensaje con el${\displaystyle K(x)}$El polinomio es el mismo que el del mismo mensaje con el${\displaystyle K'(x)}$polinomio con un cero añadido. Es simplemente un desperdicio de bits.

La combinación de estos factores significa que los buenos polinomios CRC suelen ser polinomios primitivos (que tienen la mejor detección de errores de 2 bits) o polinomios primitivos de grado${\displaystyle n-1}$, multiplicado por${\displaystyle x+1}$(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${\displaystyle n}$). ^{[ 1 ]}

• Reducción de Barrett
• Código corrector de errores
• Lista de algoritmos de suma de verificación
• Paridad (telecomunicaciones)
• Representaciones polinómicas de comprobaciones de redundancia cíclica