Las redes
deben ser capaces de transferir datos de un dispositivo a otro con total
exactitud, si los datos recibidos no son idénticos a los emitidos, el sistema
de comunicación es inútil. Sin embargo, siempre que se transmiten de un origen
a un destino, se pueden corromper por el camino. Los sistemas de comunicación
deben tener mecanismos para detectar y corregir errores que alteren los datos
recibidos debido a múltiples factores de la transmisión.
La
detección y corrección de errores se implementa bien en el nivel de enlace de
datos o bien en el nivel de transporte del modelo OSI
·
Tipos de
errores.
Interferencias,
calor, magnetismo, etc, influyen en una señal electromagnética, esos factores
pueden alterar la forma o temporalidad de una señal. Si la señal transporta
datos digitales, los cambios pueden modificar el significado de los datos. Los
errores posibles son:
Error de
bit
Unicamente
un bit de una unidad de datos determinada cambia de 1 a 0 o viceversa.
Un error de bit altera el significado del dato. Son el tipo de error menos probable en una transmisión de datos serie, puesto que el intervalo de bit es muy breve (1/frecuencia) el ruido tiene que tener una duración muy breve. Sin embargo si puede ocurrir en una transmisión paralela, en que un cable puede sufrir una perturbación y alterar un bit de cada byte.
Error de
ráfaga.
El error
de ráfaga significa que dos o más bits de la unidad de datos han cambiado. Los
errores de ráfaga no significan necesariamente que los errores se produzcan en
bits consecutivos. La longitud de la ráfaga se mide desde el primero hasta el
último bit correcto, algunos bits intermedios pueden estar bien.
Los
errores de ráfaga es más probable en transmisiones serie, donde la duración del
ruido es normalmente mayor que la duración de un bit, por lo que afectara a un
conjunto de bits. El número de bits afectados depende de la tasa de datos y de
la duración del ruido
·
Detección.
Se
conocen el tipo de errores que pueden existir, el problema es ser capaz de
reconocerlos, dado que no se puede comparar el dato recibido con el original,
sólo se podría saber que ha habido un error cuando se descodifique todo el
mensaje y se vea que no tiene sentido. Sin embargo existen determinadas
técnicas sencillas y objetivas para detectar los errores producidos en la
transmisión:
Redundancia.
La
redundancia consiste en enviar dos veces cada unidad de datos, de forma que el
dispositivo receptor puede hacer una comparación bit a bit entre ambos datos y
detectar si ha habido errores, para corregirlos con el mecanismo apropiado.
Esta técnica es muy exacta pero enlentece la transmisión.
Sin
embargo el concepto es aplicable añadiendo al flujo de datos un grupo pequeño
de bits al final de cada unidad, siendo estos bits redundantes con una parte de
la información, esos bits redundantes se descartan una vez comprobada la
integridad de la transmisión.
En las
comunicaciones de datos se usan cuatro tipos de comprobación de redundancia:
verificación de redundancia vertical (VRC, Vertical Redundancy Check) conocida
como verificación de paridad, verificación de redundancia longitudinal (LRC
longitudinal Redundancy Check), verificación de redundancia cíclica (CRC Cyclic
Redundandy Check) y suma de comprobación (Checksum). Las tres primeras se
implementan habitualmente en el nivel físico para que pueda usarlo en nivel de
enlace de datos, mientras que la suma de comprobación se usa en los niveles más
altos.
Verificación
de redundancia vertical VRC
Es el
mecanismo más frecuente y barato, la VRC se denomina a menudo verificación de
paridad, y se basa en añadir un bit de redundancia, denominado bit de paridad,
al final de cada unidad de datos, de forma que el número total de unos en la
unidad (incluyendo el bit de paridad) sea par, o impar en el caso de la
verificación de paridad impar.
Esta
técnica permite reconocer un error de un único bit, y también de ráfaga siempre
que el número total de bits cambiados sea impar. La función de paridad (par o
impar) suma el dato y devuelve la cantidad de unos que tiene el dato,
comparando la paridad real (par o impar) con la esperada (par o impar)
Verificación
de redundancia longitudinal LRC
En esta
técnica, los bloques de bits se organizan en forma de tabla (filas y columnas),
a continuación se calcula un bit de paridad para cada columna y se crea una
nueva fila de bits, que serán los bits de paridad de todo el bloque, a
continuación se añaden los bits de paridad al dato y se envían al receptor.
Típicamente
los datos se agrupa en unidades de múltiplos de 8 -1 byte- (8, 16,24,32 bits)
la función coloca los octetos uno debajo de otro y calcula la paridad de los
bits primeros, de los segundos, etc, generando otro octeto cuyo primer bit es
el de paridad de todos los primeros bits, etc.
Esta
técnica incrementa la probabilidad de detectar errores de ráfaga, ya que una
LRC de n bits (n bits de paridad) puede detectar una ráfaga de más de n bits,
sin embargo un patrón de ráfaga que dañe algunos bits de una unidad de datos y
otros bits de otra unidad exactamente en la misma posición, el comprobador de
LRC no detectará un error.
Verificación
de redundancia cíclica CRC
A
diferencia de las técnicas VRC y LRC, que se basan en la suma (para calcular la
paridad), la técnica CRC se basa en la división binaria. En esta técnica, se
añaden bits redundantes en la unidad de datos de forma que todo el conjunto sea
divisible exactamente por un número binario determinado, en el destino los
datos recibidos son divididos por ese mismo número, si en ese caso no hay resto
de la operación, el dato es aceptado, si apareciera un resto de la división, el
dato se entendería que se ha corrompido y se rechazará.
La
técnica añade unos bits de CRC, de la siguiente manera en tres pasos básicos:
en primer lugar se añade una tira de n ceros, siendo n el número inmediatamente
menor al número de bits del divisor predefinido (que tiene n+1 bits), el
segundo paso es dividir la nueva unidad de datos por el divisor predefinido
usando un proceso de división binaria, el resto que quedara sería los bits de
CRC a añadir, el tercer paso es sustituir los n bits añadidos en el paso
primero por los n bits del resto de la operación del segundo paso, el dato
final será divisible exactamente por el divisor predefinido. La imagen muestra
el esquema del proceso.
Corrección de errores
Los
mecanismos explicados detectan errores pero no los corrigen. La corrección del
error se puede conseguir de dos formas, en la primera, cuando de descubre un
error el receptor puede pedir al emisor que retransmita toda la unidad de
datos, con la segunda, el receptor puede usar un código de corrección de
errores que corrija automáticamente determinados errores. En teoría es posible
corregir automáticamente cualquier error en un código binario, sin embargo los
códigos de corrección son más sofisticados que los de detección y necesitan mas
bits de redundancia, el número de bits necesarios es tan alto que su uso no es
eficiente, por esa razón la mayoría de la corrección se limita a errores de
tres bits o menos.
Corrección
de errores de un único bit
El
concepto de la corrección de errores se puede comprender con el caso más
sencillo: el error de un único bit. Un error de un bit supone que un bit ha
cambiado de un 0 a un 1 o de un 1 a un 0, para corregir el error, el receptor
sólo tiene que invertir el valor del bit alterado, sin embargo, para hacer eso,
el receptor debe saber en qué bit está el error, por lo que el secreto de la
corrección de errores es localizar el bit o bits inválidos. La cuestión es el
uso de los bits de redundancia para la corrección. Ahora bien ¿cuantos bits de
redundancia usar?
Para
calculas el número de bits de redundancia r necesarios para corregir un número
de bits de datos m, es necesario encontrar una relación entre m y r.
Si a m de
datos bits se le añaden r bits de redundancia, la unidad transmitida es m+r,
los bits de redundancia r deben ser capaces de indicar todas las posibilidades
de error de 1 bit posibles, incluyendo el no error, que en m+r bits es de m+r+1
posibilidades (no error, error en bit0, error en bit 1, etc), por ello r debe
ser capaz de indicar todas esos estados. Dado que los r bits pueden representar
2r estados, entonces r debe ser tal que 2r ≥ m + r + 1.
Código
Hamming
Se pueden
utilizar los bits de redundancia para corregir errores, pero ¿cómo se manipulan
esos bits para descubrir en qué posición se ha producido el error? R. W.
Hamming desarrolló una técnica que proporciona una solución práctica. El código
Hamming se puede aplicar a unidades de datos de cualquier longitud y usa la
relación de bits de datos y de redundancia. En el código cada bit r es el bit
de VRC (redundancia vertical) para una combinación de bits de datos. Por
ejemplo, un dato de 7 bits necesita 4 bits de redundancia, los colocaremos en
las posiciones 1, 2, 4 y 8, con lo que la secuencia transmitida es la que
indica la figura.
Detección y corrección.
El
receptor recibe la transmisión, toma los datos y recalcula cuatro nuevos VRC
usando el mismo conjunto de bits usados en el cálculo en el emisor, a
continuación reensambla los nuevos valores de paridad siguiendo el orden de la
posición (r8, r4, r2, r1) la cifra resultante indica si ha habido error y en
qué bit se ha producido. Si el resultado es 0000 no ha habido error, cualquier
otro resultado indica error y bit erróneo. Una vez identificado el bit erróneo,
el receptor puede cambiar el valor de ese bit para corregir el error.
Corrección
de errores de ráfaga.
Se puede
diseñar un código Hamming para corregir errores de ráfaga de una cierta
longitud, sin embargo el número de bits de redundancia necesarios es muy
elevado, porque los errores pueden ser de tantos bits pero pueden estar en
cualquiera de los bits de la cadena transmitida.
