24.4 CRC (Cyclic Redundancy Check)

• Un mensaje de n + 1 bits puede ser considerado como un polinomio de grado n donde los coeficientes son 0 o 1 [31]. Por ejemplo, el mensaje 00100011 equivaldría al polinomio x⁵ + x + 1.
• Sea M_n(x) el mensaje (polinomio de grado n) de n + 1 bits que el emisor quiere enviar al receptor, y sea G_k(x) el polinomio generador usado para crear el CRC. El CRC se calcula realizando

• El emisor concatena a M_n(x) los k bits del CRC y los envía. Matemáticamente:

  Nótese que T_n+k(x) debe ser divisible entre G_k(x).

• El receptor recibe T_n+k(x) y comprueba si es divisible entre G_k(x). Si así es supone que no se han producido errores de transmisión.

Ejemplo

Trama a transmitir: M₅(x) = x⁵ + x².
Polinomio CRC: G₃(x) = x³ + x² + 1.
Residuo: R₂(x) = 1.
Trama finalmente transmitida: 100100 001
(T₈(x) = x⁸ + x⁵ + 1).

Errores detectados

• Una trama con errores sería T_n+k(x) + E_i(x), donde E_i(x) es el polinomio formado por todos los bits de T_n+k(x) que han sido invertidos. Para no detectar el error tiene que ocurrir que

  o lo que es lo mismo, que

  

  ya que por definición

  

• Por tanto, los mejores polinomios generadores son aquellos que difícimente son factor de otro posible polinomio error. Por ello los polinomios de CRC deben: (1) tener un grado lo más alto posible y (2) no ser factorizables. Ejemplos:

  Denominación	G(x)
  CRC-8	x8 + x2 + x1 + 1
  CRC-10	x10 + x9 + x5 + x4 + x1 + 1
  CRC-12	x12 + x11 + x3 + x2 + 1
  CRC-16	x16 + x15 + x2 + 1
  CRC-CCITT	x16 + x12 + x5 + 1
  CRC-32	x32 + x26 + x23 + x16 + x11+
  	x10 + x8 + x7 + x5 + x4 + x2 + 1

• Nótese, por ejemplo, que el CRC-32 detectará todos aquellos errores tipo ráfaga^* que afecte a menos de 32 bits ya que ningún polinomio error de grado menor que 32 será divisible entre él.