Algoritmo de verificación CRC
En la teoría de codificación algebraica, un grupo de códigos se expresa como un polinomio y cada elemento de código en el grupo de códigos se considera como un coeficiente del polinomio. Por ejemplo, 1100101 se expresa como 1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1, es decir, x6+x5+x2+1.
Supongamos que el polinomio de información original antes de la codificación es P (x), y la potencia más alta de P (x) más 1 es igual a k; el polinomio generador es G (x), y 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).
Método de codificación del remitente: multiplique P (x) por xr (es decir, desplace la secuencia de código binario correspondiente hacia la izquierda en r bits) y luego divida por G (x). 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. no ocurrió ningún error en la transmisión; de lo contrario, significa que hay 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 CRC es
p>
xrP(x) =x3(x3+x2) = x6+x5 G(x)= x3+x+1 Es decir, R(x)=x. Tenga en cuenta que la potencia más alta de G (x) es r = 3 y el CRC es 010.
Si usa división vertical (computadora módulo dos, el proceso de cálculo es
1110 ------- 1011 /1100000 (1100 desplazado 3 bits a la izquierda) 1011 -- - - 1110 1011 ----- 1010 1011 ----- 0010 0000 ---- 010 Por lo tanto, T(x)=(x6+x5)+(x)=x6+x5+x, es decir, 1100000 +010= 1100010
Si la transmisión es correcta,
T(x)= (x6+x5+x)/G(x) = , G(x)= sin resto Volviendo a la ecuación anterior, si el dividendo es 1100010, obviamente se puede dividir por el tercero 1.
El proceso de cálculo anterior nos ayuda a comprender el concepto de CRC, pero puede serlo. El algoritmo se implementa directamente mediante programación.
La siguiente tabla enumera información de CRC estándar:
<. p>Ejemplo de aplicación de abreviatura de polinomio del generador de nombres*CRC-4 x4+x+1 3 ITU G.704
CRC-8 x8+x5+x4+1 31 DS18B20
CRC-12 x12+x11+x3+x2+x+1 80F
CRC-16 x16+x15+x2+1 8005 IBM SDLC
CRC-ITU ** x16+x12+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 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI,IEEE 1394,PPP-FCS
CRC-32c x32+x28+x27+...+x8+ x6+1 1EDC6F41 SCTP
* El coeficiente del término de potencia más alto del polinomio generador se fija en 1, por lo que en la abreviatura, se elimina el 1 más alto. Por ejemplo, 04C11DB7 es en realidad 104C11DB7 **Anteriormente conocido como CRC-. CCITT. El predecesor de la UIT es el CCITT.
Observaciones:
(1) El polinomio generador está especificado por el estándar
(2) El código de verificación CRC se basa en tratar la cadena de bits como un coeficiente de 0 O un polinomio de 1, un flujo de datos de k bits puede considerarse como una secuencia de coeficientes de un polinomio de grado k-1 desde el orden k-1 hasta el orden 0 alrededor de x. Usando esta codificación, el emisor y el receptor deben acordar de antemano un polinomio generador G(x), cuyos 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 la trama con suma de verificación pueda dividirse por G(x). Cuando el receptor recibe una trama con una suma de verificación, utiliza G(x) para eliminarla. Si hay un resto, la verificación CRC es incorrecta. Solo la verificación sin resto es correcta.