Código de verificación de redundancia cíclica (CRC)

Al igual que el código de verificación Hamming, el código CRC también es un método de verificación comúnmente utilizado en la comunicación de datos.

La idea básica del algoritmo CRC es tratar los datos transmitidos como un número con una gran cantidad de dígitos. Divide este número por otro número. El resto obtenido se adjunta a los datos originales como datos de verificación.

A diferencia del entrelazado de bits de datos del código de verificación Hamming y bits de verificación, en el código CRC, el bit de verificación (bit R) está detrás del bit de información (bit K)

Con a Tome la pregunta como ejemplo: suponga que los datos a verificar son. D8～D1 = ​​​​10101011. Si se usa CRC y el polinomio generado es 10011, el código CRC es:

En primer lugar, debemos prestar atención a una expresión en la pregunta: "polinomio", que se escribe como "10011" ", a menudo escrito como "x^4+x+1" en algunas preguntas

Primero, agregue la potencia 0 más alta del polinomio después del bit de datos. Por ejemplo, el El término de potencia más alto del polinomio aquí es x^4, luego suma cuatro ceros después de los bits de datos para obtener: 101010110000, como dividendo

Luego, usa el polinomio 10011 como divisor para dividir. Cabe señalar que en la parte enmarcada de la figura, los bits correspondientes solo realizan operaciones xor, es decir, la resta se realiza sin afectar a otros bits.

El resto final: 1010, que es el dígito de control. . Entonces el código CRC completo es: 10101011 1010

Tomando el ejemplo de la sección anterior como ejemplo, supongamos que el código CRC recibido se convierte en 10001011 1010 y se produce un error en el décimo bit (bit bajo en el bien).

Ahora intenta usar el código CRC y el polinomio 10011 para realizar una división corta:

El resto es 1010(2) = 1 8+1 2 = 10(10), es decir, el décimo bit ocurre mal, simplemente invierta el valor del décimo bit para obtener el valor correcto