Métodos de detección y control de errores¶

Las redes deben ser capaces de transferir datos con exactitud. Sin embargo, siempre que se transmiten datos de un origen a un destino, se pueden corromper por el camino. Los sistemas fiables deben tener mecanismos para detectar y corregir tales errores.

Los errores en la transmisión pueden ser debidos a tres causas distintas:

• Características materiales de la línea.

• Equipos de transmisión.

• Causas externas al circuito de datos.

Para cuantificar el efecto de los errores sobre la transmisión se utiliza la tasa de error, o BER (Bit Error Rate), que es el cociente entre el número de bits recibidos erróneamente y el número total de bits transmitidos. Para redes WAN se considera como BER aceptable uno en torno a \(10^{-6}\) y para redes LAN en torno a \(10^{-9}\).

Otra forma de cuantificar los errores es mediante la tasa de error residual, que es el cociente entre el número de bits erróneos no detectados y el número de bits erróneos transmitidos.

La detección y corrección de errores se implementa bien a nivel de enlace de datos o a nivel de transporte del modelo OSI.

Tipos de errores¶

Los errores que se producen en una transmisión son de los siguientes tipos:

• Error de bit. Significa que únicamente un bit de una unidad de datos determinada (byte, carácter, unidad de datos o paquete) cambia de \(1\) a \(0\) o de \(0\) a \(1\).

  Los errores en un único bit son los menos probables en una transmisión de datos en serie¹, pero sí se pueden dar en transmisiones en paralelo.

• Error de ráfaga. Significa que dos o más bits de la unidad de datos han cambiado de \(1\) a \(0\) o de \(0\) a \(1\). La longitud de la ráfaga se mide desde el primero hasta el último bit correcto, pudiendo ser algunos bits intermedios no corruptos.

Códigos de detección de errores¶

Para detectar el mayor número de errores se utilizan los códigos de control de errores. Estos códigos se dividen en autocorrectores y detectores.

Códigos autocorrectores¶

Los códigos autocorrectores son aquellos que detectan y corrigen los errores producidos en una posición concreta. Esta tarea la desempeña el equipo receptor.

Códigos detectores¶

En los códigos puramente detectores el receptor detecta los errores, pero no es capaz de corregirlos, lo que hace es solicita el reenvío de la información. Las técnicas de solicitud de reenvío se denominan ARQ.

Modalidades de ARQ¶

Las distintas modalidades de ARQ son las siguientes:

• ARQ con envío y espera. Es el método más lento. El emisor envía un paquete, si hay un error el receptor envía una señal de no reconocido, NAK, con lo que el emisor reenvía el paquete. Si no hay error el receptor envía señal de reconocido, ACK, con lo que el emisor pasa a enviar el siguiente paquete.

• ARQ de envío continuo no selectivo. Se emplea en conexiones full-duplex. El emisor va enviando bloques de paquetes sin espera entre ellos, a la vez que los almacena en búferes de memoria. Si el receptor advierte un error en un bloque, le envía al emisor una señal NAK, con lo que el emisor reenvía todo el bloque. Cuando los búferes de memoria están saturados hay un tiempo de espera hasta que el receptor comunica que se pueden vaciar y se puede comenzar a enviar el siguiente bloque de paquetes.

• ARQ de envío continuo selectivo. Es una mejora del modo anterior, en la que además de línea full-duplex se necesita una identificación de cada paquete del bloque enviado. Cuando se produce un NAK se reenvía sólo el paquete que ha llegado mal, y no todo el bloque. Además, al llegar un NAK se vacían los búferes anteriores a ese paquete, que ya se sabe que no son defectuosos, con lo que se reducen los tiempos de parada. El inconveniente de este método es que la información a enviar es mayor.

Códigos de control de errores¶

Los códigos de control de errores son siempre redundantes. Un código redundante es el que utiliza más bits de los estrictamente necesarios para la transmisión de los datos; gracias a esta característica se pueden detectar y corregir los errores.

Se dividen en sistemáticos y no sistemáticos, según la forma de añadir los bits redundantes.

Códigos no sistemáticos¶

En los códigos no sistemáticos los bits redundantes se añaden implícitamente en el código. Se les llama códigos M entre N, como por ejemplo el 3 entre 8, que para emitir un carácter de 8 bits añade otros 3 de control.

Los bits de control siempre se ponen a 1 flanqueando el carácter.

Códigos sistemáticos¶

En los códigos sistemáticos para determinar el valor de los bits redundantes se aplica un algoritmo a la información a transmitir.

Ejemplos de códigos sistemáticos¶

Código de paridad horizontal¶

Con este código se añade un único bit redundante para hacer que el número total de bits sea par o impar.

Código de paridad vertical¶

Se aplica a más de una palabra de información. Es necesario saber cuántas palabras forman el bloque al que se aplica el algoritmo. A cada palabra se le aplica un código de paridad horizontal y al bloque la paridad vertical, como se ve en el siguiente ejemplo, en el que se ha aplicado paridad par.

Con este código si hay un error no sólo se detecta sino que se corrige, ya que se puede saber en qué bit se ha producido el error.

Código de Hamming¶

Con el código de Hamming se añade un número de bits redundantes que depende del número de bits que se usan para representar una palabra de información, de modo que se cumpla la desigualdad \(\(2^P \geq P+N+1,\)\) donde \(N\) es el número de bits por palabra y \(P\) el número de bits redundantes. Los bits redundantes se añaden intercalándose con los bits que forman la palabra en las posiciones 1, 2, 4, 8, …, empezando por los bits menos significativos.

Este código es difícil de implementar por circuitería pero sencillo a nivel de software. Sólo es capaz de detectar y corregir un bit erróneo.

Códigos lineales¶

En este caso se considera que los bits de la palabra forman un vector. A partir de este vector y de un polinomio generador establecido se obtiene otro vector final, según la fórmula

siendo \(\mathbf{i}\) el vector inicial, \(G\) el polinomio generador y \(\mathbf{c}\) el vector resultante.

Estos códigos facilitan la implementación en hardware, por lo que son más utilizados que los códigos anteriores.

Dentro de los códigos lineales los más utilizados son los CRC, códigos de redundancia cíclica. En éstos los bits del carácter a enviar son los coeficientes de un polinomio. Utilizan la siguiente fórmula:

con \(R(x)=\mbox{resto}(C(x), G(x))\). Lo que se envía por la línea es la información \(C(x)\) y el resto \(R(x)\), de forma que el destino puede detectar errores mediante la fórmula anterior.

Con estos códigos se pueden detectar errores de uno o varios bits en bloques grandes.