V I S I T A N T E S

viernes, 7 de diciembre de 2012

6.4.-MECANISMOS DE DETECCION Y CORRECCION DE ERRORES


Las redes de computadores deben ser capaces de transmitir datos de un dispositivo a otro con cierto nivel de precisión. Para muchas aplicaciones, el sistema debe garantizar que los datos recibidos son iguales a los trasmitidos. Sin embargo, siempre que una señal electromagnética fluye de un punto a otro, está sujeta a interferencias impredecibles debido al calor, el magnetismo y diversas formas de electricidad. Esta interferencia puede cambiar la forma o la temporización de la señal. Si la señal transporta datos binarios codificados, tales cambios pueden alterar su significado.

Las aplicaciones requieren entonces un mecanismo que permita detectar y corregir los posibles errores ocurridos durante la transmisión. Algunas aplicaciones tienen cierta tolerancia de errores (ej. transmisión de  audio/video), mientras  que  para  otras  aplicaciones se  espera  un  alto  nivel  de precisión (ej. transmisión de archivos).

En este documento se discuten algunos conceptos relacionados con la detección y corrección de errores en la transmisión de datos, así como algunas técnicas que llevan a cabo estas tareas.

Tipos de Errores

Antes  de  estudiar  los  mecanismos  que  permiten  la  detección  y/o  corrección  de  errores,  es importante entender cuáles son esos posibles errores.

 Error de Bit

Este término significa que únicamente un bit de una unidad de datos determinada (byte, caracter, paquete, etc.) cambia de 0 a 1 o de 1 a 0 [1][2]. Para comprender el impacto de este cambio, podemos imaginar que cada grupo de 8 bits es un caracter ASCII con un 0 adido a la izquierda. Un error de bit podría alterar completamente el caracter ASCII enviado (ej. ‘A’: ASCII 65) y en el receptor se obtendría un caracter completamente diferente (ej. ‘I: ASCII 73).

Los errores en un único bit son el tipo de error menos probable en la transmisión de datos en serie. Imagine que un emisor envía datos a 1Mbps. Esto nos dice que cada bit dura únicamente 1/1000000 seg. Para que ocurra un error de bit, el ruido debe tener una duración de sólo 1μseg, lo que es muy raro. Sin embargo, puede ocurrir un error de bit si se están enviando los datos usando transmisión paralela. Por ejemplo, si se usan 8 cables para enviar los 8 bits de un byte al mismo tiempo, y uno de los cables es ruidoso, se puede corromper un bit de cada byte.

 Error de Ráfaga

Significa que dos o más bits de la unidad de datos han sido alterados. Es importante notar que los errores de ráfaga no implican que se afecten bits consecutivos. La longitud de la faga se mide desde el primer hasta el último bit incorrecto. Algunos bits intermedios pueden no estar afectados [1][2].

La Figura 1 muestra un ejemplo de error de ráfaga.


1
0
0
0
1
1
0
1

 
Enviado:





Recibido:


1
1
0
0
0
0
0
1

 
Figura 1. Error de faga


En este caso, la longitud de la ráfaga sería 5, porque es la distancia en bits desde el primer bit erróneo hasta el último. Dentro de la ráfaga puede haber bits correctos y/o erróneos.

La presencia de errores de ráfaga es más probable en las transmisiones en serie. La duración del ruido es normalmente mayor que la duración del bit, lo que significa que cuando el ruido afecta los datos, afecta un conjunto de bits. El número de bits afectados dependerá de la tasa de datos y de la duración del ruido.


 Redundancia

Una vez que se conocen los tipos de errores que pueden existir, es necesario identificarlos. En un entorno de comunicación de datos no se tendrá una copia de los datos originales que permita comparar los datos recibidos para detectar si hubo errores en la transmisión. En este caso, no habrá forma de detectar si ocurrió un error hasta que se haya decodificado la transmisión y se vea que no tienen sentido los datos recibidos. Si los computadores comprobaran errores de esta forma, sería un proceso muy  lento y  costoso. Es  necesario un  mecanismo que  sea  sencillo y  completamente efectivo.

El concepto clave para detectar o corregir errores es la redundancia. Para esto es necesario enviar bits extra junto con los datos. Estos bits son añadidos por el emisor y eliminados por el receptor, permitiendo detectar y posiblemente corregir los bits afectados.

Un mecanismo de detección de errores que podría satisfacer los requisitos antes expuestos sería enviar dos veces cada unidad de datos. El dispositivo receptor podría entonces comparar ambas copias bit a bit. Cualquier discrepancia indicaría un error y se podría corregir mediante un mecanismo apropiado. Este sistema sería extremadamente lento. No solamente se doblaría el tiempo de transmisión, sino que además habría que añadir el tiempo necesario para comparar cada unidad bit a bit.

El concepto de incluir información extra en la transmisión con el único propósito de comparar es bueno. Pero en lugar de repetir todo el flujo de datos, se puede añadir un grupo más pequeño de bits al final de cada unidad. Esta técnica se denomina redundancia porque los bits extra son redundantes a la información, descartándose tan pronto como se ha comprobado la exactitud de la transmisión [1][2].

 Detección vs. Corrección

La corrección de errores es más difícil que la detección. En la detección sólo se quiere determinar si ha ocurrido un error, existiendo dos posibles respuestas: o no. La corrección como tal es sencilla, consiste tan solo en invertir los valores de los bits erróneos; sin embargo, es necesario previamente determinar la cantidad de bits erróneos, y aún más importante la ubicación de los mismos dentro de la unidad de datos [1][2].

La corrección de errores se puede conseguir de dos formas. En la primera, cuando se descubre un error, el receptor puede pedir al emisor que retransmita toda la unidad de datos (BEC, Backwards Error Correction). Con la segunda, el receptor puede usar un código corrector de errores, que corrija automáticamente determinados errores (FEC, Forward Error Correction).

En teoría, es posible corregir cualquier error automáticamente en un código binario. Sin embargo, los códigos correctores son más sofisticados que los códigos detectores y necesitan más bits de redundancia. El mero de bits necesarios para corregir un error de ráfaga es tan alto que en la mayoría de los casos su uso no resulta eficiente [4].

FEC (Forward Error Correction) vs. Retransmisión

Como se mencionó previamente, existen dos mecanismos para la corrección de errores:

1 FEC: Forward Error Correction.
2 BEC: Backwards Error Correction.

FEC es el proceso en el que una vez detectado el error, el receptor trata de determinar el mensaje original, usando los bits de redundancia. Para esto es necesario incluir una mayor cantidad de bits de redundancia en la unidad de datos. BEC o retransmisión es la técnica en la que el receptor detecta la ocurrencia del error y solicita al emisor que reenvíe el mensaje. Se repite la retransmisión del mensaje hasta que el receptor compruebe que el mensaje ha llegado sin error (es posible que un error no sea detectado y el mensaje sea interpretado como correcto) [1][3].

Cada una de estas técnicas ocupa su nicho diferente [4]. En enlaces altamente confiables es más económico usar técnicas BEC, retransmitiendo los mensajes defectuosos que surjan eventualmente, sin  necesidad  de  agregar  una  gran  cantidad  de  bits  de  redundancia,  lo  que  acarrearía  una disminución de las prestaciones. Sin embargo, en enlaces poco confiables como los inalámbricos, puede resultar beneficioso agregar la redundancia suficiente a cada mensaje para que el receptor pueda reconstruir el mensaje original. Existen dos razones primordiales que sustentan el uso de las técnicas FEC:

1 La tasa de errores por bit en un enlace poco confiable puede ser muy grande, lo que resultará en un gran mero de retransmisiones.
2 En algunos casos, el tiempo de propagación es muy elevado en comparación con el tiempo de transmisión. Por este motivo la retransmisión del mensaje resultaría muy costosa [3].

 Códigos de bloque

Para entender la manera en que pueden manejarse los errores, es necesario estudiar de cerca cómo se codifican los datos. Por lo general, una unidad de datos (generalmente llamada en este ambiente trama) consiste de m bits de datos y r bits redundantes usados para la verificación, siendo la longitud total de una trama n (n = m + r). A la unidad de n bits que contiene datos y bits de redundancia se le conoce como  palabra codificada. La cantidad de bits de redundancia y la robustez del proceso son factores importantes del esquema de codificación [1][2].

 Distancia Hamming

Para empezar se define un concepto de utilidad. Se define la distancia Hamming d(v1, v2) entre dos palabras codificadas de n bits vy v2, como el número de bits en el que vy v2  difieren [2]. Por ejemplo:

v1 = 10001001;              v2 = 10110001               |            entonces,           d(v1, v2) = 3

Distancia Hamming mínima
Se llama distancia Hamming mínima a la distancia Hamming más pequeña entre todos los posibles pares de palabras codificadas de un esquema de codificación. Se usa el rmino dmin para definir la distancia Hamming mínima  en  un  esquema de  codificación. Para  hallar  este  valor,  se  deben encontrar las distancias Hamming entre todas las palabras codificadas del esquema, y se selecciona la más pequeña [2].

Detección y corrección de errores mediante códigos de bloque

Las palabras de datos de longitud m bits no se transmiten directamente, sino que son previamente transformadas en palabras codificadas de n bits. Con m bits se pueden crear hasta 2palabras de datos, y con n bits se pueden crear hasta 2n palabras codificadas. Como n>m, el mero de palabras codificadas es mayor al número de palabras de datos. El proceso de codificación en bloques es uno- a-uno: la misma palabra de datos es transformada siempre en la misma palabra codificada. Las palabras codificadas obtenidas a partir de una palabra de datos son llamadas válidas. Esto significa que se tendrán 2n 2m palabras codificadas que no serán utilizadas. Estas palabras codificadas son llamadas inválidas [1].

 Detección de errores con códigos de bloque
Ahora, ¿cómo puede usarse la codificación por bloques para detectar errores? Si se cumplen las siguientes dos condiciones, el receptor será capaz de detectar variaciones en la palabra codificada original:

1 El receptor tiene la lista de las palabras codificadas válidas.
   La palabra codificada válida transmitida ha sido modificada a una inválida. La 

El emisor crea palabras codificadas a partir de palabras de datos usando un generador que aplica reglas y procedimientos de codificación específicos del esquema empleado. Cada palabra codificada que es enviada al receptor puede variar durante la transmisión. Si la palabra codificada recibida no es válida, es descartada. Sin embargo, si la palabra codificada es modificada como otra palabra codificada válida durante la transmisión, el error no será detectado.

Corrección de errores con códigos de bloque
En el caso discutido previamente (detección de errores), el receptor sólo necesita saber que la palabra codificada es inválida para detectar un error. En la corrección de errores, el receptor deberá descubrir  la  palabra  codificada  originalmente enviada.  La  idea  principal  es  la  misma  que  la empleada en la detección de errores, pero el verificador es mucho más complejo. Se aprecia el funcionamiento del proceso de corrección en la 



















 
Una vez que se recibe una palabra inválida, el receptor calcula la distancia Hamming entre la palabra recibida y las palabras válidas. La menor de las distancias calculadas indica cual es la palabra codificada válida que el emisor originalmente transmitió. Si dos o más palabras válidas

generan el mismo valor, que resulta ser el mínimo, entonces el error no puede ser corregido y la palabra recibida se descarta.

En la mayoría de las aplicaciones de transmisión 2palabras son válidas, pero como se ha visto, debido a la manera en que se codifican no se usan las 2palabras codificadas posibles. Es viable entonces hacer una lista de las palabras codificadas válidas y encontrar las dos cuya distancia Hamming sea mínima. Esta será la distancia Hamming de todo el código [1][4].

Las propiedades de detección y corrección de errores de un código dependen de su distancia Hamming. Si dos palabras codificadas están separadas una distancia Hamming d, se requerirán d errores de un bit para convertir una en otra.

Para detectar d errores se necesita un código de distancia d + 1, pues con tal código no habrá manera de que d errores de bit puedan cambiar una palabra codificada válida a otra. Cuando el receptor encuentra una palabra codificada no válida, sabe que ha ocurrido un error de transmisión. De manera similar, para corregir d errores se necesita un código de distancia 2d + 1, pues así las palabras codificadas válidas estarán tan separadas que, aún con d cambios, la palabra codificada original sigue estando más cercana que cualquier otra palabra codificada, por lo que puede determinarse de manera única [4].

El Ejemplo 1 muestra dos sencillos códigos de bloque para la detección y corrección de errores de un bit:

Ejemplo 1:

Código para detección de errores
Código para la corrección de errores
Palabra de Datos
Palabra Codificada
Palabra de Datos
Palabra Codificada
00
000
00
00000
01
011
01
01011
10
101
10
10101
11
110
11
11110


El ejemplo muestra la notable diferencia en la cantidad de bits de redundancia necesarios entre una técnica de detección en contraste con los necesarios en una técnica de corrección de errores.

 Códigos cíclicos

Los códigos cíclicos son códigos de bloque que cumplen varias propiedades:

    Al aplicar la operación XOR sobre dos palabras codificadas válidas, se genera otra palabra codificada válida.
    Si una palabra codificada válida es rotada en forma cíclica, el resultado es otra palabra codificada válida.

Por ejemplo, si se tiene la palabra codificada 1001101001, y se rota hacia la izquierda de forma cíclica, entonces 0011010011 debe ser una palabra codificada válida [1][3].