Detección y corrección de errores (bits)

Detección y corrección de errores
6. Detección y corrección de errores
• No podemos evitar que haya errores, pero si los hay debemos
detectarlos.
• Otro asunto distinto es que una vez detectado el error, se sepa
corregirlo mediante técnicas sofisticadas de cálculo o
retransmisión de la información.
• Perder información
▫ no significa que la información que envía el emisor no llegue al
receptor.
▫ Significa que hay cambios no deseados o imprevistos en la
información
Un bit que sea 0 se convierte en 1 y viceversa
Ejemplo: sistema de comunicaciones de un cajero automático3
6. 1. La detección del error
La paridad simple/lineal
• Se basa en que junto con la información del usuario se envían
una serie de bits que indican cualidades de estos datos.
• Una alteración en la información se detecta por comparación
con esos bits especiales de paridad (que hace que no se
correspondan con los valores previstos en el momento de la
emisión).
• Este sistema sólo es capaz de detectar errores producidos en un
número impar de bits de la cadena transmitida.
• Se utiliza sobre todo en transmisiones asíncronas donde se
manda un bit de paridad por carácter o dato.4
6. 1. La detección del error (cont.)
Paridad Par: el bit de paridad se calcula contando el número de unos: si
es un número par el bit vale 0, si es impar vale 1
Paridad impar:el bit de paridad se calcula contando el número de unos:
si es un número par el bit vale 1, si es impar vale 0
Ej. Si queremos enviar la cadena 0011011
Paridad par:
0011011(0)
Si se altera el segundo 0 de la cadena de bit y recibimos 0111011(0)
el receptor descubre el error porque en número de unos es 5 (impar y debería ser
un número par).
Ej. Si queremos enviar la cadena 0011011
Paridad impar:
0011011(1)
Si se altera el segundo 0 de la cadena de bit y recibimos 0111011(1)
el receptor descubre el error porque en número de unos es 6 (par y debería ser un
número impar).5
6. 1. La detección del error (cont.)
La paridad de bloque
La paridad de bloque es un caso especial de la paridad simple.
También puede ser par o impar.
Se trata de organizar la información por bloques, componiendo
una tabla de n x m bits.
Seguidamente se sacan los bits de paridad por filas y por
columnas.
Por último, se envían por la línea de transmisión junto con los bits
constitutivos del mensaje los bits de paridad calculados. Estos bits
calculados constituyen la paridad de bloque o checksum .6
6. 1. La detección del error (cont.)
La paridad de bloque (II)
El receptor reconstituye la tabla y comprueba que los códigos de
paridad sean correctos.
Si se ha alterado el valor de algún bit del mensaje no solo se
puede detectar que se ha producido un error, sino que también se
puede saber dónde se ha producido.
Este método no solo es capaz de detectar el error sino también
de corregirlo, en algunos casos.
En caso de que se pierdan varios bits en la secuencia, este método
es capaz de detectarlo aunque no de corregirlos; por tanto, es más
sensible que el método de paridad simple.7
6. 1. La detección del error (cont.)
Ej. Supongamos que queremos transmitir la siguiente información
00110, 01010, 11001, 11111 la expresamos así en una tabla y
calculamos los bits de paridad por filas y por columnas:
Envía
Llega
0 0 1 1 0 0 0 0 1 1 0 0
0 1 0 1 0 0 0 1 1 1 0 0
1 1 0 0 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 0 1 0 1 0
Al recalcular el receptor los códigos de paridad detecta que no
coinciden los códigos de la 2a fila y 3a columna que deberían ser 1’s.
Se ha detectado pero además se sabe dónde se ha producido.8
6. 1. La detección del error (cont.)
Redundancia cíclica (CRC)
Dado un bloque de mensaje de k-bit, el transmisor genera una
secuencia de n-bits, denominada secuencia de comprobación de
la trama (FCS)
De tal manera que la trama resultante, con n+k bits , sea divisible por
algún número previamente acordado entre emisor y receptor,
denominado polinomio patrón, P.
El receptor entonces dividirá la trama recibida por ese patrón y si no
hay resto en la división se supone que no ha habido errores.9
6. 1. La detección del error (cont.)
Ejemplo:
G(x)= X 5 +x 4 +x 2 +1
Dado el mensaje M = 1010001101 (10 bits) El patrón P = 110101 (6 bits)
Por tanto la FCS será de 5 bits (grado del polinomio de P)
El mensaje se multiplica por 2 5 (desplazar hacia la izquierda 5 bits)
El resultado se divide por P
1010001101 00000 |110101
110101 (patrón)
1101010110
111011
110101
111010
110101
111110
110101
101100
110101
110010
110101
01110 (Resto)
El resto se suma la mensaje a transmitir T= 10100011010111010
6. 1. La detección del error (cont.)
Si no hay error el receptor recibe T intacto.
La trama recibida se divide por P:
101000110101110 |110101
110101
1101010110
111011
110101
111010
110101
111110
110101
101111
110101
110101
110101
0000000 como no hay resto no ha habido errores.11
6. 1. La detección del error (cont.)
PROCEDIMIENTO DE APLICACIÓN DEL MÉTODO DE REDUNDANCIA
CÍCLICA
1) MENSAJE A TRANSMITIR
-
Añadir n (grado del polinomio patron) ceros al mensaje M para obtener M0
-
Dividir M0 entre el patron
-
Sumar el resto obtenido a M0
2) COMPROBACION DEL MENSAJE RECIBIDO
2.1. - Dividir el mensaje recibido entre el patrón
- Comprobar que el resto es cero
- Obtener el mensaje quitando los n últimos bits
2.2.
- Restar los n últimos bits (sustituir por 0)
- Dividir entre el patrón
- Comprobar que el resto coincide con los n últimos bits quitados12
6. 1. La detección del error (cont.)
Con este método se podrán detectar:
Todos los errores de un único bit.
Todos los errores dobles, siempre que el patrón tenga al menos 3
unos.
Cualquier número impar de errores siempre que el patrón contenga el
factor x +1 ( es decir acabe en 11)
Cualquier ráfaga de errores en la que la longitud de la ráfaga sea
menor que la longitud del polinomio divisor.
La mayoría de las ráfagas de mayor longitud.
Los patrones más frecuentes son:
CRC-12 = X 12 +X 11 +X 3 +X 2 +X+1.
Se utiliza para la transmisión de secuencias de
caracteres de 6 bits y genera un FCS de 12 bits .
CRC-16 = X 16 +X 15 +X 2 +1.
Se utiliza en los Estados Unidos.
CRC-CCITT = X 16 +X 12 +X 5 +1.
Se utiliza en Europa .13
6.2. La corrección del error
• La estrategia de corrección de errores se dividen en dos grandes
grupos:
▫ Sistemas de corrección hacia delante
Consiste en reconstruir la información perdida a partir de los
datos erróneos recibidos.
▫ Sistemas de corrección hacia atrás
Se basan en que cuando el receptor detecta que ha recibido un
código erróneo le dice al emisor que vuelva a repetir el mensaje14
6.2. La corrección del error (cont.)
Sistemas de corrección hacia delante
Código Hamming
• El primer modo de corrección de errores consiste en dejar que el
destinatario determine, a partir de la información redundante que ha
recibido del emisor y del propio mensaje, los bits erróneos.
• Se basan en añadir un conjunto de bits de comprobación a los bits de
información que se pretenden transmitir.
• Cuando se produce un error los bits de comprobación informan de cual
es el bit o conjunto de bits erróneos.
• El conjunto de bits de información (d) y bits de comprobación (B)
constituyen una palabra de código Hamming (b).
• Estudiaremos el funcionamiento de los códigos Hamming para el caso
de la detección y corrección de un único bit erróneo.15
6.2. La corrección del error (cont.)
• Código Hamming para el caso de la detección y corrección de un único bit
erróneo.
▫ Ecuaciones de paridad
a: b1+b3+b5+b7+b9+b11+b13+b15
b: b2+b3+b6+b7+b10+b11+b14+b15
c: b4+b5+b6+b7+b12+b13+b14+b15
d: b8+b9+b10+b11+b12+b13+b14+b15
▫ Comprobación de errores.
Si la paridad se cumple el resultado de cada ecuación es 0, si no se cumple
es 1. Con ello obtendremos 4 valores (0 ó 1) para a, b, c y d. Con ellos
compondremos el valor binario “dcba” que traducido al decimal nos dará
la posición del bit erróneo recibido.