Detección y Corrección de Errores en Sistemas de Comunicación

Introducción

Cada tipo de aplicación requiere un determinado nivel de fiabilidad: las transacciones bancarias no toleran errores, mientras que las aplicaciones de video y voz sí pueden tolerar algunos. Si los sistemas de transmisión no alcanzan los requisitos necesarios, se utilizan técnicas de control de errores para mejorar su comportamiento. Estas técnicas se dividen en dos categorías principales: detección de errores y retransmisión (ARQ, Automatic Repetition Request), y corrección de errores avanzada (FEC, Forward Error Correction).

Redundancia y Mecanismos de Control de Errores

Cualquier mecanismo de detección o corrección de errores necesita que la información sea redundante. Esto significa que se transmitirán bits adicionales que no serían necesarios para transmitir únicamente la información. La redundancia se utiliza para:

Detección de errores: Solo se preocupa de decidir si se ha producido algún error.
Corrección de errores: En este caso, hay que saber el número de errores exactos y la posición de los bits erróneos dentro de la palabra transmitida.
Detección de errores con retransmisión: Sistema por el cual, al detectarse un error, se pide la retransmisión del mensaje hasta que este llega sin errores.
Corrección avanzada de errores: El receptor intenta decidir dónde se han producido los errores y los corrige sin solicitar la retransmisión.

Detección de Errores

La información del usuario se codifica de manera que el mensaje cumple con unas determinadas características o patrón. Esto se consigue añadiendo bits redundantes a la información. Si el bloque recibido no presenta el patrón esperado (no es una palabra código válida), significa que se han producido errores y se puede alertar al emisor, rechazarla, etc.

Código Hamming

La distancia entre dos palabras es el número de diferencias entre los bits de la misma posición. La distancia mínima de Hamming de un código es la distancia más pequeña que hay entre todas las parejas de palabras código. Para que un código permita detectar hasta n errores, d_min debe ser n+1. Para que corrija hasta n errores, d_min debe ser 2n+1.

Paridad Simple

d_min = 2. Detectará todos los errores de 1 bit. Ejemplo: carácter: 7 + 1 bit paridad, código ASCII. Añade 1 bit de redundancia para cada k bits de información. Overhead = 1/(k+1). Detecta todos los errores de un número impar de bits, no detecta los pares. Cualquier técnica de detección de errores fallará en la detección de algunos errores, concretamente en aquellos donde los errores convierten una palabra código válida en otra palabra código válida.

Efectividad del Código de Errores

Se mide como la probabilidad de que el sistema falle en la detección de un error. Hay que conocer las condiciones en que se producen errores. Dependen de las características particulares del canal de comunicación.

Vector de Error Aleatorio

Suponemos que se transmite una palabra código de n bits. Se define el vector de error e = (e₁, e₂…e_n) donde e_i=1 si se produce un error en la transmisión del bit i y e_i=0 en otro caso. El modelo del vector de error aleatorio considera que los 2ⁿ posibles vectores de error son equiprobables. En este modelo, la probabilidad de e no depende del número de errores que contiene. En el sistema de paridad simple se producirán errores en la detección de errores siempre que el número de bits erróneos del vector de error sea par, por tanto, la probabilidad de error en la detección de error es 1/2.

Bits de Error Aleatorios

En este modelo, los errores en cada bit se producen con una probabilidad p y de forma independiente los unos de los otros. La probabilidad de un vector de error con j errores es p^j(1-p)^n–j, para cualquier canal de interés p 1, esto significa que la probabilidad de cada vector de error se reduce a medida que aumenta el número de bits que contiene. Los patrones con 1 error son más probables que los de dos, estos que los de 3, y así sucesivamente.

Paridad Bidimensional

Para mejorar la cobertura se insertan más bits de paridad. La información se dispone en columnas, se añade un bit de paridad simple a cada fila y cada columna. Se usaba en los primeros sistemas de control de errores. Todos los errores de 1, 2 y 3 bits son detectables, pero no lo son todos los patrones de 4 o más.

Códigos Polinómicos

Representamos las palabras código mediante polinomios y no vectores. Se usa aritmética polinómica en lugar de las sumas de comprobación. Se implementan mediante registros de desplazamiento. También se llaman códigos de redundancia cíclica CRC. Los usan la mayoría de estándares de comunicación para la detección de errores. Son la base de métodos de corrección de errores más potentes. Uno de los motivos para la utilización de estos códigos en sistemas de detección de errores es la facilidad de su implementación mediante circuitos formados a partir de registros de desplazamiento. La secuencia es:

Se aceptan los bits de información i_k_-1, i_k_-2…i₀.
Se añaden n–k ceros a la información.
Se introduce la secuencia en un registro de desplazamiento que realiza la división polinómica.
Después de n desplazamientos, el registro contiene el residuo.

Patrones de error no detectables: El receptor acepta una palabra si el residuo de la división r(x)/g(x) es cero. Por tanto, como b(x) es divisible por g(x) por construcción, si e(x) es también divisible por g(x), no se detectará el error. Para poder detectar una mayoría de los errores, habrá que seleccionar un polinomio generador que no sea divisor de los patrones de error más probables.

Internet Checksum

: algunos protocolos de internet (IP,TCP,UDP) usan bits de comprobación para detectar errores. En el caso del protocolo IP se calcula una suma de comprobación para el contenido de la cabecera y se inserta en un campo especial. Como la suma de comprobación se debe recalcular en cada encaminador, el algoritmo escogido lo es más porque permite una implementación en software sencilla y no tanto por sus capacidades detectoras.