Algoritmo de verificación CRC
Supongamos que el polinomio de información original antes de la codificación es P(x), la potencia más alta de P(x) más 1 es igual a k; el polinomio generador es G(x), la potencia más alta de G(x) es igual a r; el polinomio CRC es r(x); el polinomio de información codificada con CRC es T(x).
El método de codificación del remitente: multiplique P (x) por xr (es decir, la secuencia de código binario correspondiente se desplaza a la izquierda en R bits) y luego divida por G (x), el resto es R(x). Expresado como T(x)=xrP(x)+R(x).
Método de decodificación del receptor: divide T(x) por G(x) para obtener un número. Si el resto es 0, significa que no hubo ningún error en la transmisión, de lo contrario significa que hubo un error en la transmisión.
Por ejemplo, suponiendo que el código de información es 1100 y el polinomio generador es 1011, es decir, P(x) = x3+x2, G(x) = x3+x+1, el proceso de cálculo La CRC es la siguiente.
xrp(x) = x3(x3+x2) = X6+X5g(x) = x3+x+1, es decir, r(x) = x. x) r= 3. El CRC es 010.
Si utiliza la división vertical (módulo de computadora 2), el proceso de cálculo es el siguiente
1110-1011/11000000 (1100 se desplaza 3 bits hacia la izquierda). 1011-110 1011-1010 10 1010101011-001000-06545
Si la transmisión es correcta,
t(x)=(X6+X5+x)/G(x)= , G(x) = sin resto. Volviendo a la división vertical anterior, si el dividendo es 1100010, es obvio que se puede dividir por el cociente del tercer 1.
El proceso de cálculo anterior nos ayuda a comprender el concepto de CRC. Sin embargo, la programación directa para implementar el algoritmo anterior no sólo es engorrosa sino también ineficiente. De hecho, el CRC no se calcula ni verifica directamente en ingeniería.
La siguiente tabla enumera algunos datos CRC en el estándar:
Ejemplo de aplicación de abreviatura polinomial generadora de nombre*
CRC-4 x4+x+1 3 ITU G.704
CRC-8 x8+X5+x4+1 31 ds 18b 20
CRC-12 x 12+x 11+x3+x2+x+1 80F
CRC-16 x 16+x 15+x2+1 8005 IBM SDLC
CRC-ITU * * x 16+x 12+X5+1 1021 ISO HDLC, ITU X .25, V.34/V.41/V.42, PPP-FCS, ZigBee
CRC-32 x32+x26+x23+...+x2+x+1 04c 11db 7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS
CRC-32c x32+x28+x27+...+x8+X6+1 1 edc6f 41 SCTP
*Generar El coeficiente de el término de potencia más alto del polinomio se fija en 1, por lo que el 1 más alto se elimina uniformemente en la fórmula abreviada. Por ejemplo, 04C11DB7 es en realidad 104C11DB7. * *Anteriormente conocido como CRC-CCITT. El predecesor de la UIT fue el Comité Consultivo sobre Telégrafos y Teléfonos Internacionales.
Observaciones:
(1) El polinomio generador se especifica en la norma.
(2) 2) El código de verificación CRC se basa en tratar la cadena de bits como un polinomio con coeficientes 0 o 1, y el flujo de datos de k bits puede considerarse desde el orden k-1 hasta 0. orden con respecto a X La secuencia de coeficientes del polinomio k-1. Usando esta codificación, el emisor y el receptor deben acordar de antemano el polinomio generador G(x), y sus bits alto y bajo deben ser 1. Para calcular la suma de verificación de una trama de M bits M(x), la idea básica es agregar la suma de verificación al final de la trama para que el polinomio de esa trama con la suma de verificación pueda dividirse por G(x).
Cuando el receptor recibe una trama con una suma de comprobación, G(x) la elimina. Si hay un resto, la verificación CRC es incorrecta y solo la verificación sin resto es correcta.