Detección y Corrección de errores

Otra tarea importantísima de la capa de enlace (y de las demás capas superiores) es la de detectar, y si se desea, corregir errores ya que el nivel físico tradicionalmente no está libre de errores por ruido termal, interferencias electromagnéticas, etc.

 

Para detectar que hubo un error, al enviarse un marco se guarda en una tabla cuándo se envió y se le asocia un tiempo para recibir su confirmación. Si no se recibe la confirmación por parte del receptor, se re-envía el marco. El problema que puede surgir es que si se perdió la confirmación, el receptor puede tener marcos duplicados, lo cual se soluciona al asignar un número de secuencia a cada marco, para descartar los duplicados y re-enviar su confirmación.

Otra forma de detectar un error (que ya no fue la pérdida del marco, sino la corrupción de su contenido), es insertar un código de chequeo, y para esta labor se utilizan códigos basados en el concepto de "distancia de Hamming". La distancia de Hamming para un código cualquiera se define como el número de bits diferentes al hacer un XOR entre todos sus símbolos.

 

Si los símbolos de un código difieren a lo menos en 2X+1 bits, al variar X bits (dañar X bits) obtenemos un nuevo símbolo que se parecerá más en un bit a un código válido que a otro código válido y por lo tanto podemos decir que el símbolo dañado en realidad es el más parecido realizando así su corrección.

Para el diseño estándar de protocolos, se han especificado algunas cadenas de chequeo bien conocidas llamadas CRC-12, CRC-16 y CRC-CCITT con R=12,16 y 16 bits respectivamente. Estas cadenas se interpretan como polinomios de la manera que sigue.

CRC-12 = 1100000001111 = X12 + X11 + X3 + X2 + X + 1.

CRC-16 = 11000000000000101 = X16 + X15 + X2 + 1

CRC-CCITT = 10001000000100001 = X16 + X12 + X5 + 1

Observemos que la posición del bit con un uno representa la potencia del polinomio. Cada uno de estos polinomios se conocen como "generador polinomial" y las siglas CRC significan "Cyclic Redundancy Code".

Los tres pasos para detectar errores con estos polinomios son:

1. Si el CRC es de grado R, tome el marco de tamaño M y concaténele R ceros al final generando una nueva cadena o polinomio P.
2. Divida el polinomio P entre el CRC correspondiente usando división de módulo dos. En esta división se va a obtener un residuo K.
3. Réstele K al polinomio P usando resta de módulo dos obteniendo así una cadena T. La cadena T es el marco que será enviado a través de la capa física.

 

Nivel de Enlace/Detección y Corrección de errores