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 añ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 rá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.
|
Recibido:
|
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: sí 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 nú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 nú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 v1 y v2, como el número de bits en el que v1
y 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 té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 2m palabras de datos,
y con n bits se pueden crear hasta 2n
palabras codificadas. Como n>m,
el nú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 2m
palabras son válidas, pero como se ha visto, debido a la manera en que se codifican
no se usan las 2n palabras 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].
