Tratamiento de Errores
En este nivel de enlace se incluyen mecanismos para el tratamiento de errores que permitan detectar cuándo han sucedido errores, dónde y cómo solucionarlo.
La técnica más empleada para detectar errores en una trama es a través del uso del código de redundancia cíclica o CRC.
Otra técnica muy usada es el uso del bit de paridad, o parity check.
Técnica de Detección de Errores: CRC
La técnica ARQ se utiliza en el nivel de enlace, en combinación con el control de flujo para la corrección de los errores de transmisión. este método se basa en la detección de los errores de transmisión en la recepción, por lo cual es necesario implementar en el nivel de enlace un mecanismo de detección de los errores.
Existen diferentes técnicas para verificar que un bloque de datos se transfiere de un sistema a otro sin errores, aunque el más utilizado en el nivel de enlace se conoce como CRC (Cyclic Redundancy Code, código de redundancia cíclica).
Esta técnica se basa en añadir al bloque de datos una secuencia de bits, llamada CRC, obtenida a partir de la Información contenida en el propio bloque de datos. Esta secuencia de bits es calculada por el emisor y transmitida junto con los datos. el receptor, cuando recibe los datos realiza el mismo cálculo. Si el CRC calculado por el receptor coincide con el recibido es que los datos no han sido alterados en la transmisión, es decir, no ha habido errores y por tanto la trama se acepta. cuando el CRC calculado no coincide con el recibido es que ha habido errores en la transmisión, con lo cual la trama se rechaza.
La secuencia de bits o CRC se calcula realizando la operación división binaria de los datos entre un divisor predeterminado. A este divisor se le conoce como polinomio generador. El resto obtenido de la división es el CRC. Se conoce como polinomio generador porque la secuencia de bits del divisor se expresa como un polinomio.
Por ejemplo, el número binario 1100101 se puede expresar de forma polinomial como:
1X6 + 1X5 + 0X4 + 0X3 + 1X2 + 0X1 + 1X0
o lo que es lo mismo, suprimiendo los términos cuyo coeficiente es cero (0): X6 + X5 + X2 + 1
El exponente más alto se conoce como orden, de forma que, en el ejemplo anterior, se dice que es un polinomio de orden 6. los pasos que se siguen para el cálculo del CRC son:
- Llamamos n al orden del polinomio generador.
- A los datos para los que se quiera obtener su CRC se añaden a la derecha n ceros.
- Se lleva a cabo la división binaria entre los datos (con los ceros añadidos) y el polinomio generador.
- El resto que se obtiene en la división es el CRC que tendrá n bits.
En el siguiente ejemplo se quiere calcular el CRC para el bloque de bits 10110010. En este ejemplo utilizamos un bloque de datos de solo 8 bits, pero el proceso es el mismo para bloques de datos más grandes.
En el ejemplo se va a utilizar el siguiente polinomio generador de orden 3: X3 + X2 + 1, que expresado como número binario queda 1101. Como el polinomio generador es de orden 3 se añaden tres ceros a la derecha de los datos y se efectúa la división binaria.
Como se puede observar, la división binaria utiliza las mismas reglas que la división aritmética. La obtención de los cocientes parciales es sencilla:
- Si el bit más significativo del dividendo parcial es 1, el cociente parcial es 1.
- Si el bit más significativo del dividendo parcial es 0, el cociente parcial es 0.
Por ejemplo, para el primer cociente parcial. el dividendo parcial es 1011, por tanto, el cociente parcial es 1.
Se pasa el divisor para restarse al dividendo parcial: la resta binaria también es sencilla:
0 – 0 = 0
0 – 1 = 1
1 – 0 = 1
1 – 1 = 0
Después de cada resta se toma el siguiente bit del dividendo y se descarta el que está más a la izquierda, que siempre va a ser un 0.
Si el cociente parcial es 0, se ponen todos los bits a cero:
Para el cálculo del CRC se descarta el cero de la izquierda del resto. Para el ejemplo queda como resto 100 que, por tanto, será el CRC obtenido.
Un CRC debe tener dos cualidades: Debe tener exactamente un bit menos que el divisor y añadirlo al final de la tira de datos debe hacer que el resultado sea exactamente divisible por el divisor.
Resumen:
CRC: (se debe agregar una suma de verificación o checksum)
Ejemplo: (este método divisa un generador (“g”))
D=111010 (mensaje que queremos enviar), en este caso se agregan 3 bit –> 111010_ _ _
g= 1001 (el binario lo podemos representar como polinomio que representa cada uno de los “1” (uno)) –> x3+1
R= Resto [D*2r/g] (donde “r” son los bit que se agregan al mensaje que queremos enviar)
1) Obtener D*2r
111010*2* nuestro generador que era 1001
111010*23
D*23=111010000
2) Realizar la operación:
111010000:1001 = 1 1 1 1 0 1 (si el dividendo tiene 4 dígitos, se debe coger 4 dígitos del divisor, y se dice que cabe 1 vez, agregando las veces que sean necesarias)
1001 (pongo el divisor abajo y realizo la operación XOR)
01111 (me quedan tres dígitos, y por este motivo bajo 1 dígito para que esten los 4 dígitos)
1001 (pongo el divisor abajo y realizo la operación XOR)
01100 (me quedan tres dígitos, y por este motivo bajo 1 dígito para que esten los 4 dígitos)
1001 (pongo el divisor abajo y realizo la operación XOR)
01010 (me quedan tres dígitos, y por este motivo bajo 1 dígito para que esten los 4 dígitos)
1001 (pongo el divisor abajo y realizo la operación XOR)
001100 (como me quedan dos dígitos, tengo que bajar 1 dígito, como sólo quedarían 3 dígitos, apunto que me cabe 0 veces y por este motivo bajo 1 dígito más para que esten los 4 dígitos y se vuelve a apuntar que cabe 1 vez)
1001 (pongo el divisor abajo y realizo la operación XOR)
0101 (este ya es el valor de la división final o el resto)
Y el resultado de la operación es: 1 1 1 1 0
Entonces:
“D” quería transmitir 111010
Resto: 0101
Lo que transmito es: 111010101 (siempre va hacer de largo igual que “r” los bits que se agregan al mensaje)
Recordemos:
- Bianrio es por 2
- Decimal es por 10
- El binario 2=10
- El binario 2*2=100
Operación XOR: (los distintos valen 1 y los iguales valen 0)
- A xor 0 =A
- A xor A=0
- 1 xor 1 =0
- 0 xor 0=0
- 1 xor 0 =1
- 0 xor 1= 1
Bit de paridad
Si un número impar de bits se transmite incorrectamente, el bit de paridad será incorrecta, lo que indica que se produjo un error de paridad en la transmisión. El bit de paridad sólo es adecuado para la detección de errores, no puede corregir los errores, ya que no hay manera de determinar que está dañado en particular bits.