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 elctromagnéticas, etc.
Una vez que la capa de enlace ya sabe como identificar el comienzo y fin de un marco, se puede dar a la tarea de verificar si están correctos. Se pueden hacer dos cosas: simplemente detectar que hubo un error y pedir la retransmisión del marco o mensaje (lo cual no es factible en líneas unidireccionales) o bien corregir los bits dañados.
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. Por ejemplo, si tenemos un código con los símbolos A,B,C; donde A = 11000, B=00011, C=01101, tenemos:
| A xor B 11000 | A xor C 11000 | |
Distancia de Hamming
- = mínimo(4,3,3) = 3 bits.
Si los símbolos de un código difieren a lo menos en X bits, es posible saber que ocurrieron X-1 errores ya que al variar un símbolo válido (dañarlo) en X-1 bits es imposible obtener otro símbolo válido. 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.
Por otro lado, si la longitud de los datos es M bits y consideramos que los bits que producen la distancia de Hamming es de R bits, entonces tenemos que la longitud de la cadena sin incluir el inicio y fin de marco es N con N=(M+R). Compruebe que para corregir un error en una cadena se debe cumplir que (M+R) < 2 R. Por ejemplo, si destinamos 3 bits al chequeo, (M+3) < 8, entonces M < 5, lo que significa que puedo tener un código de 32 símbolos con capacidad de corregir errores de un bit. Esta fórmula sirve para establecer el tamaño de una cadena de transmisión mínima con corrección de errores.
Para el diseño estándard 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 = X^12 + X^11 + X^3 + X^2 + X + 1. CRC-16 = 11000000000000101 = X^16 + X^15 + X^2 + 1
- CRC-CCITT = 10001000000100001 = X^16 + X^12 + X^5 + 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:
- 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.
- 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.
- 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.
El efecto del algoritmo anterior es simple, si hacemos lo mismo con un número decimal conocido. Supongamos que CRC=3 y P = 25. Al dividir 25 entre 3 nos da un residuo K=1. Entonces lo que enviamos es una cadena compuesta de las partes 25-1= (24). Observemos que no se transmite el 24, sino una cadena 25-1. En el destino, se hace la división (binaria) de la cadena compuesta (25-1)/3 = 8 y el residuo es cero, lo cual significa que la cadena original es correcta y son los primeros M bits.
