Contents

1 Fundamentos

• Los c’odigos de detecci’on de errores (en ingl’es, error detecting code o EDC) permiten al receptor conocer si alg’un bit ha sido alterado durante su tr’ansito. Para ello es necesario introducir una cierta cantidad de informaci’on redundante en el mensaje.
• Es responsabilidad del receptor usar los datos recibidos o desecharlos. En este segundo caso, probablemente sea solicitada una retransmisi’on de los datos.

2 Paridad

• Consiste en añadir bits de paridad de forma que el n’umero de bits iguales a 1 en el mensaje sea un n’umero impar si usamos paridad impar o un n’umero par si usamos paridad par [1]. Ejemplos:
      (datos) (paridad)  
      0 0  
      1 1  
      00 0  
      11 0  
      111 1  
      00101 0  
      01001010101001 0  
    

• Usando un ’unico bit de paridad se pueden detectar el 50% de los errores.

3 Checksum

• Consiste en sumar (usando una determinada precisi’on aritm’etica) todas las palabras del mensaje y transmitir como EDC dicha suma [2]. El receptor realiza la misma suma y si no concuerda con el EDC se sabe que se ha producido un error de transmisi’on.
• Como ejemplo se muestra (en C) el algoritmo de la suma de comprobaci’on usado por el TCP y el UDP (v’ease los Cap’itulos ?? y ??):

• Tanto el emisor como el receptor ejecutan el mismo algoritmo. Lo ’unico que cambia es que el receptor incluye la suma de comprobaci’on en el c’alculo (y el emisor no). Si el resultado es 0, entonces se supone que no existen errores de transmisi’on.

4 C’odigo de redundancia c’iclica

• Un mensaje de n + 1 bits puede ser considerado como un polinomio de grado n donde los coeficientes son 0 o 1 [3]. Por ejemplo, el mensaje 00100011 equivaldr’ia 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 (C’odigo de Redundancia C’iclica, o en ingl’es, Cyclic Redundancy Code). El CRC se calcula realizando

• El emisor concatena a M_n(x) los k bits del CRC y los env’ia. Matem’aticamente:

  N’otese que por la forma en que T_n+k(x) es constru’ido, T_n+k(x) debe ser divisible, necesariamente, entre G_k(x).

• Cuando receptor recibe T_n+k(x), comprueba si es divisible entre G_k(x). Si as’i es, supone que no se han producido errores de transmisi’on.

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’ia 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 por el error. Para no detectar el error tendr’ia que ocurrir que

  o lo que es lo mismo, que

  

  ya que por la forma en que T_n+k(x) es constru’ido, se cumple siempre que

  

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

  Denominaci’on	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’otese, por ejemplo, que el CRC-32 detectar’a todos aquellos errores tipo r’afaga¹ que afecte a menos de 32 bits ya que ning’un polinomio error de grado menor que 32 ser’a divisible entre ’el.

References