1
Tema 4:Tema 4:DetecciDeteccióón y Correccin y Correccióón de Erroresn de Errores
Escuela Politécnica SuperiorIngeniería Informática
Universidad Autónoma de Madrid
2
OBJETIVOS
Conocer cómo pueden detectarse y prevenirse errores que puedan aparecer en los distintos intercambios de información que realiza el ordenador.
Aplicar distintos métodos de detección y corrección de errores.
TEMA 4: DETECCIÓN Y CORRECCIÓN DE ERRORES
4.1 Control de errores usando paridad
4.2 Códigos de autochequeoy autocorrectores
DetecciDeteccióón y Correccin y Correccióón de Erroresn de Errores
Bibliografía Tema 4:- Introduction to Computer Hardware and Data Communications.
P.-A. GOUPILLE. (Prentice Hall, 1993). Cap. 5.
3
Conceptos previosConceptos previos
• Concepto de Código:
- De un conjunto de palabras (por ejemplo: Posibles palabras binarias de una longitud determinada), código es un subconjunto
- Ejemplo: • Código: Palabras de tres bits con sólo un dígito a 1• En las palabras binarias de longitud 3:
{000, 001, 010, 011, 100, 101, 110, 111}
Escuela Politécnica Superior
4
Necesidad del tratamiento de erroresNecesidad del tratamiento de errores• Posibilidad de errores
- En informática (entre varios ordenadores o en el interior de ellos) la información circula entre diferentes dispositivos y reposa en ciertos dispositivos
- Posibles errores: • Ruidos en las comunicaciones• Defectos en las superficies de los discos, etc.
- Los errores consisten en la modificación de la información desde que se emite (o almacena) hasta que se recibe (o se recupera)
• Cambio de valor de algunos bits (0 ⇔ 1)
Escuela Politécnica Superior
5
Necesidad del tratamiento de erroresNecesidad del tratamiento de errores• Tipos de errores
- Aislados: Bit afectado rodeado de bits correctos• Simples: 1 bit afectado • Múltiples: Más de 1 bit afectado
- Ráfagas de errores: Secuencia de bits contiguos con errores
Escuela Politécnica Superior
1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0
1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0
1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 0
Información de partida:
Error aislado simple:
Errores aislados triples:
Ráfaga de error:
6
Tipos de cTipos de cóódigosdigosde tratamientos de erroresde tratamientos de errores
• En lugar de manipular la información, se definen códigos en los que se incluye la información que permite detectar y/o corregir errores
• Códigos correctores de errores- Uso:
• Se recibe la información, si se detecta el error se corrige
- Situaciones:• Cuando no es conveniente retransmitir la información
Escuela Politécnica Superior
7
Tipos de cTipos de cóódigosdigosde tratamientos de erroresde tratamientos de errores
• Códigos detectores de errores- Uso:
• Se recibe la información, si se detecta el error se solicita la retransmisión
- Situaciones: • Suele ser más costoso corregir que detectar• Cuando es posible la retransmisión, se solicita
Escuela Politécnica Superior
8
Conceptos asociados a erroresConceptos asociados a errores
Escuela Politécnica Superior
• Distancia de Hamming entre dos palabras- Nº de bits que difieren dos palabras
- Ejemplo:
0 1 0 1 0 1 0 1
0 0 0 0 1 1 1 1 Distancia Hamming = 4
Se necesitan 4 errores para transformar una palabra en la otra
9
Conceptos asociados a erroresConceptos asociados a errores
Escuela Politécnica Superior
• Distancia de Hamming de un código- Distancia mínima entre las palabras que componen el código
- Ejemplo: {100, 111, 011}
mín{d(100, 111), d(100, 011), d(111, 011)} = mín{2, 3, 1} = 1
10
Conceptos asociados a erroresConceptos asociados a errores
Escuela Politécnica Superior
• Propiedades para la detección de errores- Para detectar d errores de un bit entre dos
palabras, es necesario un código con una distancia de
Hamming de al menos d+1
- De otra forma: Con una distancia de Hamming de d se
pueden detectar d-1 errores
- Ejemplo: C = {001, 010, 100}, d. Hamming = 2
• Un error aislado siempre se detecta - Un error en 001 ⇒ 101, 011, 000, ∉ C
• Dos errores aislados no se detectan- Dos errores en 001 ⇒ 111, 010, 100. Dos pertenecen a C
11
Conceptos asociados a erroresConceptos asociados a errores
Escuela Politécnica Superior
• Propiedades para la corrección de errores- Para corregir d errores de un bit entre dos
palabras es necesario un código con una distancia de
Hamming de al menos 2d+1
- De otra forma: Con una distancia de Hamming de d se
pueden corregir (d-1)/2 errores
- Ejemplo: C = {0000000000, 0000011111, 1111100000,
1111111111}, d. Hamming = 5
Se pueden detectar d-1 = 5-1 = 4 errores Se pueden corregir (d-1)/2 = 4/2 = 2 errores
12
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Comprobación de paridad
• Paridad vertical, longitudinal y cruzada
• Código i en n
• Códigos de redundancia cíclica (CRC) (Cyclic Redundancy Codes)
13
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Comprobación de paridad- VRC (Vertical Redundancy Checking)- La información se coloca en bloques de longitud fija
- A los bloques se les añade un bit llamado de paridad
y que, normalmente, precede a la información
- Criterios para la paridad• Bit de paridad par:
- Nº total de “1” par: Bit de paridad = 0- Nº total de “1” impar: Bit de paridad = 1
• Bit de paridad impar:- Nº total de “1” par: Bit de paridad = 1- Nº total de “1” impar: Bit de paridad = 0
14
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Comprobación de paridad- Ejemplo:
Información Criterio Código0 1 1 1 0 0 1
0 1 1 1 0 0 1
0 0 1 1 1 0 0 1
1 0 1 1 1 0 0 1
Paridad par
Paridad impar
15
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Comprobación de paridad- Ejercicio: Completar el bit de paridad con criterio
impar (1) y par (2)
Información1 21 0 0 0 0 0 10 1 0 1 1 1 11 1 0 1 0 0 01 1 1 0 1 1 11 0 1 0 0 0 10 1 1 1 1 1 10 1 1 1 0 0 10 0 0 1 1 0 1
16
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- La información se coloca en grupos de (m) bloques de longitud fija (k) como matriz kxm o mxk
1 2 k
12
m
17
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Cada bloque:
• 1 bit para VRC • 1 bit para la paridad
perpendicular o LRC(Longitudinal RedundancyChecking)
• 1 bit de paridad cruzadaque comprueba paridades
1 2 k
12
m
Bits de VRC
Bit de paridadcruzada
Bits de LRC
18
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo: Se quiere enviar la información “PAG” en
ASCII (7 bits):
50 41 4716
(101 0000 100 0001 100 0111) (k = 7, m = 3, matriz 7x3)
• Se añade:
- Bit para VRC criterio par (verde, primera fila)
- Bit para LRC criterio par (azul, última columna)
- Bit de paridad cruzada criterio par (rosa)
19
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 1:
0 0 0 01 1 1 10 0 0 01 0 0 10 0 0 00 0 1 10 0 1 10 1 1 0
Paridad cruzada
LRC
VRC
En hexadecimal se envía (columnas):
50 41 47 5616
20
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Evaluación del código
• Distancia Hamming del código: 4 - Las dos palabras del código más cercanas difieren en un bit de
datos - Un cambio en un bit de datos implica (para que la palabra sea
correcta):» Cambio en un bit de VRC» Cambio en un bit de LRC» Cambio en el bit de paridad cruzada
- ⇒ Un cambio mínimo implica 4 bits• Capacidad de detección y corrección:
- Detecta todos los errores simples, dobles y triples- Corrige todos los errores simples
21
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Evaluación del código
• Uso: - Emisión:
» Disposición de datos como matrices» Se añaden las paridades VRC, LRC y cruzada
- Recepción:» Comprobación de paridad cruzada (requisito)» Comprobación de VRC y LRC: Las posiciones de error
en VRC y LRC marcan filas y columnas en cuyas intersecciones puede haber error. Dependiendo del tipo de errores se pueden o no detectar y corregir.
22
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 2: Detección y no corrección de errores triples
• Error triple en el caso anterior (rojo) (se supone que no afectaa las paridades)
0 0 0 01 1 1 10 1 0 00 0 0 10 0 0 00 0 1 10 0 1 10 0 1 0
Errores
23
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 2: Detección y no corrección de errores triples
• Detección mediante errores en bits de paridad
0 0 0 01 1 1 10 1 0 00 0 0 10 0 0 00 0 1 10 0 1 10 0 1 0
VRC errónea
Cruzada correcta
LRC errónea
24
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 2: Detección y no corrección de errores triples
• Imposibilidad de corrección: Error en las posiciones sospechosas
0 0 0 01 1 1 10 1 0 00 0 0 10 0 0 00 0 1 10 0 1 10 0 1 0
Bitssospechosos
25
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 3: Detección y no corrección de errores dobles
• Error doble en el caso anterior (rojo) (se supone que no afecta a las paridades)
0 0 0 01 0 1 10 0 0 01 0 0 11 0 0 00 0 1 10 0 1 10 1 1 0
Errores
26
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 3: Detección y no corrección de errores dobles
• Detección mediante errores en bits de paridad
0 0 0 01 0 1 10 0 0 01 0 0 11 0 0 00 0 1 10 0 1 10 1 1 0
VRCerrónea
Cruzada correcta
LRCerrónea
27
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 3: Detección y no corrección de errores dobles
• Imposibilidad de corrección: No todas las posiciones sospechosas son erróneas
0 0 0 01 0 1 10 0 0 01 0 0 11 0 0 00 0 1 10 0 1 10 1 1 0
Bitssospechosos
28
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 4: Detección y corrección de error simple
• Error simple en el caso anterior (rojo) (se supone que no afecta a las paridades)
0 0 0 01 1 1 10 0 0 01 0 0 11 0 0 00 0 1 10 0 1 10 1 1 0
Error
29
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 4: Detección y corrección de error simple
• Detección mediante errores en bits de paridad
0 0 0 01 1 1 10 0 0 01 0 0 11 0 0 00 0 1 10 0 1 10 1 1 0
VRCerrónea
Cruzada correcta
LRCerrónea
30
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Paridad vertical, longitudinal y cruzada- Ejemplo 4: Detección y corrección de error simple
• La identificación inequívoca del bit erróneo permite su corrección
0 0 0 01 1 1 10 0 0 01 0 0 11 0 0 00 0 1 10 0 1 10 1 1 0
Bitsospechosoy erróneo
31
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos i en n- O códigos de verificación de cuenta fija- El código i en n está formado por las palabras binarias de n bits que tienen i bits igual a 1
- Observaciones:• Número de palabras posibles de n bits: Variaciones con
repetición de 2 elementos tomados de n en n: 2n
• Número de palabras del código: Permutaciones de n elementos. 1 se repite i veces y 0 n-i veces
n!
i! (n - i)!
32
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos i en n- Ejemplo: Código 4 en 8
• 4 en 8 está formado por palabras binarias de 8 bits con 4 bits igual a 1
0 0 0 0 1 1 1 10 0 0 1 0 1 1 1
0 0 0 1 1 0 1 1
0 0 0 1 1 1 0 1
…
1 1 1 1 0 0 0 0
0 0 0 1 1 1 1 0
0 0 1 0 1 1 1 0
33
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos i en n- Ejemplo: Código 4 en 8
• Sobre un total de 28 = 256, sólo permite 70: 8! = 70
4! 4!
- Evaluación del código• Su distancia de Hamming es 2: Un cambio mínimo de 1 bit
(0 ⇔ 1) obliga a cambiar otro para ajustar el número de bits igual a 1
• Sólo detecta errores simples que no es capaz de corregir
34
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Conceptos previos
• Es natural contar de forma cíclica
- LOS GRADOS: Supongamos que contamos un número de grados entero.El orden es:
0, 1, 2, ..., 45, ..., 180, ..., 357, 358, 359, 360=0, 1, etc.
90º
180º
270º
0º=360º
35
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Conceptos previos
- LOS GRADOS:Es fácil operar
» El siguiente a 359 es 0
» El anterior a 0 es 359
» Tres más que 358 es 1
» Cinco menos que 2 es 357
36
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Conceptos previos
- LAS HORAS DEL DÍA
El orden es
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,19, 20, 21, 22, 23, 0, 1, ...
6h
12h
18h
0h=24h
Y operar es como antes
37
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Conceptos previos
• El conjunto de los enteros módulo 2
- {0, 1}- Su orden cíclico
1 0
- Las operaciones pueden representarse con tablas
+ 0 10 0 11 1 0
- 0 10 0 11 1 0
* 0 10 0 01 0 1
1+1=00-1=1
38
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Conceptos previos
• Observaciones sobre los polinomios Q[x]- División de polinomios con coeficientes racionales (Q)
Ejemplo: D = 6x4 + 9x3 + 5x + 2 y d = 2x2 - 16x4 +9x3 +0x2 +5x +2 2x2 +0x -1
3x2 +(9/2)x +(3/2)6x4 +0x3 -3x2
0x4 +9x3 +3x2 +5x +9x3 +0x2 -(9/2)x
0x3 +3x2 +(19/2)x +2 +3x2 +0x -(3/2) 0x2 +(19/2)x +(7/2)
Se obtiene: q = 3x2 + (9/2)x + (3/2) y r = (19/2)x + (7/2)
39
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Conceptos previos
• Observaciones sobre los polinomios Q[x]Ejemplo: Se puede representar abreviadamente:
6 9 0 5 2 2 0 -1
3 9/2 3/26 0 -3 0 9 +3 5
9 0 -(9/2)
0 3 +(19/2) 2
3 0 -(3/2) 0 (19/2) +(7/2)
40
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Conceptos previos
• Polinomios con coeficientes enteros módulo 2- Se puede demostrar (no objeto de este curso) que esta división también es posible cuando los coeficientes son enteros módulo 2 siempre que las operaciones (resta, productos, etc.) sean definidas en ese conjunto- Ejemplo: D = x13 + x12 + x10 + x8 + x7 + x5 + x4 y d = x4 + x + 1
1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1
1 1 0 0 0 0 1 0 1 01 0 0 1 10 1 0 0 1 1
1 0 0 1 10 0 0 0 0 1 0 1 1 0
1 0 0 1 10 0 1 0 1 0 0
1 0 0 1 10 0 1 1 1 0
Resultado: q = x9 + x8 + x3 + x y r = x3 + x2 + x
41
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Presentación de la técnica • Se interpretan las cadenas de 1’s y 0’s como coeficientes
enteros módulo 2 de polinomios• Los k bits de cada mensaje se tratan como si fueran los
coeficientes de un polinomio M(x), de orden k-1, en el que las operaciones se hacen en módulo 2
• Si el mensaje fuese: 10010110el polinomio considerado sería:
M(x) = 1 • x7 + 0 • x6 + 0 • x5 + 1 • x4 + 0 • x3 + 1 • x2 + 1 • x1 + 0 • x0 == x7 + x4 + x2 + x
• Se utiliza un polinomio generador G(x) de grado r. Este polinomio está predeterminado, y es el mismo en el emisor y el receptor
42
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Presentación de la técnica • Operaciones en módulo 2:
0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 0 (sin acarreo)
0 – 0 = 00 – 1 = 1 (sin acarreo)1 – 0 = 11 – 1 = 0
43
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica
- Presentación de la técnica • Objetivo del procedimiento: Añadir r bits al mensaje de k bits,
de forma tal que el polinomio resultante, T(x), correspondiente
a los k+r bits, sea divisible por G(x)
• El receptor verifica si T(x) es divisible por G(x), y si no lo es
hay un error en la transmisión
44
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Uso de la técnica
• Emisor (algoritmo a seguir):- Añadir r bits 0 al extremo de menor orden del mensaje. El
polinomio correspondiente será xr • M(x)- Dividir (módulo 2) xr • M(x) entre G(x): xr • M(x) = C(x) + R(x)
G(x) G(x)
C(x) es el cociente y R(x) el resto
- Restar a xr • M(x) el valor del resto R(x) (esto es equivalente a añadir al mensaje original M(x) el resto R(x))
T(x) = xr • M(x) - R(x) - Se obtiene así T(x), cuyos coeficientes (unos o ceros)
sustituyen el mensaje a transmitir. T(x) es siempre divisible por G(x)
45
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Uso de la técnica
• Receptor:- Recibe el mensaje T’(x) del emisor- Divide T’(x) entre G(x)- Si el resto es cero, el mensaje ha llegado correctamente
(T’(x) = T(x))- Si el resto no es cero, el mensaje ha llegado con error y hay
que pedir una retransmisión (T’(x) ≠ T(x))
46
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- Ejemplo: Se requiere transmitir 10011011. Polinomio generador G(x) = x3 + 1
• Mensaje: 10011011• Polinomio generador: 1001 (r=3)• Se añaden 3 bits 0 al final del mensaje: 10011011000• Se divide x3 • M(x) entre G(x):
1 0 0 1 1 0 1 1 0 0 0 1 0 0 1
1 0 0 0 1 0 1 01 0 0 10 0 0 0 1 0 1 1
1 0 0 10 0 1 0 0 0
1 0 0 10 0 0 1 0
• Se transmite 10011011010 (4DA16)
47
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica- El polinomio generador
• La selección del polinomio generador es esencial si queremosdetectar la mayoría de los errores que ocurran
• Se puede demostrar (no objeto de este curso) que los polinomios generadores son más potentes con el primer y último bits a 1
• Ejemplos de polinomios generadores (estándares internacionales):
- CRC-12: x12 + x11 + x3 + x2 + x + 1- CRC-16: x16 + x15 + x2 + 1- CRC-CCITT: x16 + x12 + x5 + 1
» 100% errores simples» 100% errores dobles» 100% errores en un número impar de bits» 100% errores en ráfagas de igual a o menos de 16 bits» 99.997% errores de ráfagas de 17 bits» 99.998% de errores en ráfagas de 18 o más bits
48
CCóódigos para tratamiento de erroresdigos para tratamiento de errores
Escuela Politécnica Superior
• Códigos polinómicos o de redundancia cíclica
- Ejercicio: Utilizando el polinomio generador G = x3 + 1, determinar los valores hexadecimales que se transmitirán para mandar el mensaje binario 10110110
(Solución: 5B216)