Subcapa de Enlace. Detección de errores

Conceptos básicos:

• Error de bit significa que sólo cambia una unidad de información, es decir, un 0 se convierte en 1 o viceversa.

• Error de ráfaga significa que dos o más bits cambian dentro de la información.

• Redundancia: se denomina así a los datos extras que se envían junto con la información pero no son información. Son eliminados en el receptor.

Mecanismos de detección de errores

Se utilizan para averiguar si se ha producido un error en la transmisión y se basan en la inclusión de información redundante.

Técnicas utilizadas:

• Verificación de paridad.

• Redundancia cíclica.

• Suma de comprobación (Checksum)

Verificación de paridad.

Es una de las técnicas más simples. Se utiliza cuando la probabilidad de error es pequeña, para detectar errores de bits individuales en pequeños bloques de datos (p. ej. en caracteres)

 Sólo puede detectar errores de bits o errores de ráfaga si el número de errores es impar.

¿Qué es la paridad?

• La paridad de un carácter o un bloque de bits se refiere al número de 1's que contiene dicho bloque.

• La paridad puede ser par o impar:

  • Bit de paridad par

    • Vale 0 si el número de unos que contiene el bloque es par (o cero).

    • Vale 1 si el número de unos que contiene el bloque es impar.

  • Bit de paridad impar

  • Vale 1 si el número de unos que contiene el bloque es par (o cero).

  • Vale 0 si el número de unos que contiene el bloque es impar.

Limitaciones de la paridad

• Los bits de paridad sólo son capaces de detectar los "errores impares"

  • Es decir, aquellos errores que sólo afectan a un número impar de bits.

  • Si el error afecta a un número par de bits, entonces no podrá ser detectado

  Ejemplo (paridad par)

¿Cómo se calcula la paridad? La paridad equivale a la función lógica XOR

Para calcular la paridad de un carácter se puede realizar una XOR de todos los bits del carácter

La técnica consiste en que los datos más el bit redundante tengan el número de 1 que coincidan con el tipo de paridad.

Existen dos tipos:

• Paridad impar: Consiste en añadir un 1 al final de los datos si el número de unos es par y un 0 si es impar.

• Paridad par: Consiste en añadir un 0 al final de los datos si el número de unos es par y un 1 si es impar.

Redundancia cíclica

La comprobación de redundancia cíclica (CRC) es un código de detección de errores usado frecuentemente en redes digitales y en dispositivos de almacenamiento para detectar cambios accidentales en los datos. Los bloques de datos ingresados en estos sistemas contiene un valor de verificación adjunto, basado en el residuo de una división de polinomios; el cálculo es repetido en el destino, y la acción de corrección puede tomarse en caso de que el valor de verificación no concuerde; por lo tanto se puede afirmar que este código es un tipo de función que recibe un flujo de datos de cualquier longitud como entrada y devuelve un valor de longitud fija como salida. El término suele ser usado para designar tanto a la función como a su resultado. Pueden ser usadas como suma de verificación para detectar la alteración de datos durante su transmisión o almacenamiento. Las CRC son populares porque su implementación en hardware binario es simple, son fáciles de analizar matemáticamente y son particularmente efectivas para detectar errores ocasionados por ruido en los canales de transmisión.

Se basan en el uso de un polinomio generador G(X) de grado r, y en el principio de que n bits de datos binarios se pueden considerar como los coeficientes de un polinomio de orden n-1. Por ejemplo, los datos 10111 pueden tratarse como el polinomio x +x²+x¹+x⁴ ⁰  A estos bits de datos se añaden r bits de redundancia de forma que el polinomio resultante sea divisible por el polinomio generador, sin generar resto.  El receptor verificará si el polinomio recibido es divisible por G(X). Si no lo es, habrá un error en la transmisión.

Técnicas de detección de errores

Terminología:

• M(x): Trama a transmitir (k bits)

• G(x): Divisor o generador polinomial (n + 1 bits)

• R(x): Resto de la división o CRC (n bits)

• Generación del CRC en el emisor. A la trama a transmitir, M(x), se concatenan n ceros a la derecha. Esto es equivalente a multiplicar M(x) * 2 n. A continuación, M(x) * 2 n se divide por el generador polinomial (divisor) G(x). La división se realiza en aritmética módulo 2 (las sumas o restas parciales se sustituyen por operaciones XOR). Esta división da lugar a un cociente Q(x) y a un resto R(x) ○ El resto R(x) representa el código de redundancia cíclica (CRC). El emisor envía la trama concatenada con el CRC o resto, es decir:

  • Trama enviada: T(x) = M(x)* 2 n + R(x)

    • Comprobación del CRC en el receptor

    • El receptor toma la trama recibida, T(x)=M(x)* 2 n + R(x), y la divide por el mismo generador polinomial G(x)

    • El resto de esta división debe ser cero. En caso contrario significa que se ha producido un error en la transmisión

Ejemplo de generador polinomial (8 bits)

Algunos generadores polinomiales estándar

Suma de comprobación (checksum) : sistema por el cual se aplica una función de comprobación (hash) a todos los datos y el resultado se envía como dato redundante. En el receptor, se vuelve a aplicar esta función hash y se comprueba con la recibida.

• Si son iguales entonces los datos no tienen errores. En Internet se utiliza el checksum de 16 bits, es decir, se agrupan los datos del mensaje en bloques de 16 bits y se aplica un hash consistente en la suma en complemento a 1 de estos, este será el checksum. En el receptor se suman nuevamente todos los datos más el checksum y debe dar 111....111, si hay algún 0 ha habido un error. Existen métodos que puede reparar ciertos errores pero la cantidad de información redundante que añaden los hace poco viables.